齒輪圖的孤立斷裂度

張明瑜，王世英

（1.山西大同大學數(shù)學與計算機科學學院，山西大同037009；2.山西大學數(shù)學科學學院，山西太原030006）

齒輪圖的孤立斷裂度

張明瑜1，王世英2

（1.山西大同大學數(shù)學與計算機科學學院，山西大同037009；2.山西大學數(shù)學科學學院，山西太原030006）

本文給出了齒輪圖和它的補圖的孤立斷裂度。

可靠性；二部圖；孤立斷裂度

本文僅考慮簡單圖。設圖G=(V(G),E(G))，其中V(G)和E(G)分別為圖G的頂點集和邊集。若|V(G)|=1，則稱G為平凡圖。設S?V(G)，當G是完全圖時，若G-S是平凡圖，稱S是G的一個點割。當G是非完全連通圖時，若G-S是不連通的，則稱S是G的一個點割。G的點割集：C(G)={S：S是G的一個點割}。二部圖又稱為偶圖，如果圖G的頂點集可以分為兩個非空子集X和Y，使得每一條邊都有一個端點在X中，另一個端點在Y中。設V'是V的一個非空子集，以V'為頂點集，以兩端點均在V'中V的邊的全體為邊集所組成的子圖稱為G的由V'導出的子圖，記為G[V']。G的孤立頂點數(shù)用i(G)表示。V(G)的一個子集S稱為一個穩(wěn)定集,若S中任意兩個頂點在G中都不相鄰。G的最大穩(wěn)定集的頂點數(shù)稱為G的穩(wěn)定數(shù)，記為α(G)。其它未給出的定義見文獻[1]。

輪圖Wn是由一個n-圈和一個孤立點u組成，并且圈上所有點都和此孤立點相鄰，圈上的點和此孤立點之間的邊稱為輪輻。設Wn是輪圖且V(Wn)={v1,v2,…,vn,u} ，其中u是中心點，若Wn的n-圈上的每條邊被剖分，則得到的新圖稱為齒輪圖，記為Gn，每條邊剖分時新加入的點構成的集合記為{u1,u2,…,un} ，顯然v(Gn)=2n+1，ε(Gn)=3n。

定義1[2]設G是一個連通圖。圖G的孤立斷裂度

設S*是G的一個點割，若i(G-S*)-|S*|=isc(G)，則稱S*為一個孤立斷裂度集。

引理1[2]若G是一個階為n的連通圖,則

引理2[2]設G是一個連通二部圖，那么isc(G)≥0。

定理1設Gn是一個齒輪圖，那么isc(Gn)=1。

證明因為v(G)=2n+1，α(Gn)=n+1,則由引理1，有

另一方面，設S是Gn的一個使|S|為最大的孤立斷裂度集，V1是Gn-S的孤立點集。假設。那么令G1是Gn-S-V1的一個分支，S1是G1的一個孤立斷裂度集，由于齒輪圖是一個二部圖，而二部圖的任意導出子圖也是二部圖，所以G1是一個二部圖。此外，由引理1，isc(G1)≥0。令。由于，所以有

Gn-S*不連通。因此

上式取等式，故S*也是一個孤立斷裂度集且滿足，與S的最大性矛盾。從而，進而。因為,

所以,

定理2設n是齒輪圖Gn的補圖，那么

證明因為齒輪圖Gn是一個二部圖，所以圖n有兩個完全圖作為它的子圖，記為Kn1，Kn2。

其中u和Kn1中的每個點都不相鄰，u1,u2,…,un中的每個點都和Kn1中的n-2個點相鄰。設S是的一個點割，則|S|≥n。否則，設|S|≤n-1。如果|S|=n-1時,S不是點割,那么|S|≤n-2時，S也不是點割。因此，設。再設則

情況1u∈S。

情況2u?S。

在這種情況下，在u1,u2,…,un中，存在i+1個點不在S中。如果i≥2，在情況1中已經(jīng)討論過，-S連 通 ，所 以 設i=1 。 這 時|。當≥3時，由于V(Kn2)中的點u1,u2,…,un每個點都和v1,v2,…,vn中的n-2個點相鄰，所以存在中的點在n-S中是相鄰到中的點，n-S仍然連通。因此下面討論i=1和n=3。在圖1中，容易驗證-S連通。

圖1 ˉ3

因為Kn1，Kn2是的子圖且，所以設有。再設且，則有設。因為Kn1，Kn2是的子圖，，所 以。 取S=則S是點割且,因此

[1]Bondy J A,Murty U S R.Graph Theory[M].New York:Springer,2007.

[2]王世英，楊玉星，林上為，等.圖的孤立斷裂度[J].數(shù)學學報,2011,54(5):861-874.

〔責任編輯 高海〕

The Isolated Scattering Number of the Graph with Shape of the Gear

ZHANG Ming-yu1,WANG Shi-ying2
（1.School of Mathematics and Computer Science,Shanxi Datong University,Datong Shanxi,037009;2.School of Mathematical Sciences,Shanxi University,Taiyuan Shanxi,030006）

In this paper,we present the isolated scattering number of the graph with shape of the gear and its complement graph.

vulnerability;bipartite graph;isolated scattering number

O157.5

A

1674-0874(2015)03-0009-02

2015-03-24

張明瑜（1983-）,女，山西應縣人，碩士，講師，研究方向：圖論及其應用。