一類特殊連通圖的性質(zhì)

韓 靜,宋星星,李 玥

(1.山西大學(xué)商務(wù)學(xué)院 數(shù)學(xué)教學(xué)研究部，山西 太原 030031；2.山西大學(xué)商務(wù)學(xué)院 會計(jì)學(xué)院，山西 太原 030031)

0 引言

文中討論的內(nèi)容只涉及簡單圖，在簡單圖中一些基本定義詳見[1,2].

設(shè)G是一個圖，用V(G)表示其頂點(diǎn)集，E(G)表示其邊集.頂點(diǎn)u∈V(G)在圖G中的度是指定點(diǎn)u與圖G中頂點(diǎn)集合相鄰接的頂點(diǎn)的個集，記為dG(u)，不混淆時(shí)下角標(biāo)G可省略，簡記成d(u).我們記Δ(G)為圖G中頂點(diǎn)度數(shù)的最大值，稱為圖G的最大度.令圖G=(V(G)，E(G))，如果V′?V(G)并且E′?E(G),那么圖H=(V′,E′)是圖G的一個子圖.對于頂點(diǎn)集V(G)的任意非空子集S，那么稱以S為頂點(diǎn)集合，以兩個端點(diǎn)都在集合S中的所有的邊的集合構(gòu)成的子圖為G的由S導(dǎo)出的子圖，極為G[S]，稱集合NG(v)={uV(G)；uvE(G)}為點(diǎn)v在圖G中的鄰域.

我們稱完全二部圖K1,3為爪.令H是一個給定的圖，如果G不包含H的導(dǎo)出子圖，則圖G被稱為無H的.那么H被稱為G的一個禁用子圖.對于一個圖類，如果對于每一個H∈，G都是無H的，那么圖G被稱為無的.

一般的，我們通常從圖的參數(shù)角度去研究圖的性質(zhì)，例如：最小度，圖的獨(dú)立數(shù)，連通度等，詳見[3-6].除此之外，從圖的結(jié)構(gòu)上去研究圖的性質(zhì)也是非常有意義的，通常我們考慮禁用某些特定的子圖.最常見的禁用子圖之一是K1,3，稱不包含K1,3作為導(dǎo)出子圖的那些圖為無爪圖，詳見[7,8].

1 主要結(jié)論

我們主要研究了一類無{K1，3，P4}連通圖的性質(zhì).這個問題的研究對我們研究不連通禁用子圖對的刻畫能帶來一些幫助.

定理1令G是一類無{K1，3，P4}的連通圖.則它的頂點(diǎn)集合可以劃分成兩個子集X和Y使得以下三個結(jié)論成立：

1)G[X]和G[Y]都是團(tuán)；

2)|X|≥|Y|；

3)對于任意的兩個頂點(diǎn)y1,y2∈Y，要么NG[X](y1)=NG[X](y2)，要么NG[X](y1)∪NG[X](y2)=|X|. 證明 如果Δ(G)<3，那么G是一條路或者是一個圈，因?yàn)镚是無P4的，所以G是P1，P2，P3，C3或C4中的一個 (G∈{P1，P2，P3，C3，C4}).注意到K2也是一個團(tuán)，因此我們很容易驗(yàn)證這些圖都是滿足定理中的三個結(jié)論.

如果Δ(G)≥3，那么G中包含K3做為一個導(dǎo)出子圖，則我們一定能從G中找到一個極大團(tuán)，設(shè)為C.令X=V(C)并且Y=V(G)X.則|X|≥3.注意到當(dāng)|Y|<2時(shí)，定理成立.所以我們只需要考慮當(dāng)|Y|≥2時(shí)的情形即可.

斷言1對于任意的頂點(diǎn)y∈Y，NG[X](y)≠?都成立.

證明 如果存在一個頂點(diǎn)y∈Y使得，NG[X](y)=?，那么存在一個頂點(diǎn)y0∈Y使得d(y0,X)=2.令P=y0y1x1是y0與X之間的最短路.則x1∈X并且y1∈Y.注意到G[X]是G中的一個極大團(tuán).則存在一個頂點(diǎn)x0∈X使得x0y1?E(G).因此G[{x0，x1，y1，y0}]≌P4，矛盾.

接下來，我們首先斷言G[Y]是一個團(tuán).否則存在兩個頂點(diǎn)y1,y2∈Y使得y1y2?E(G).因此我們分以下兩種情形：

情形1要么NG[X](y1)NG[X](y2)=?，要么NG[X](y1)NG[X](y2)=?.

不失一般性，我們假設(shè)NG[X](y1)NG[X](y2)=?.這意味著NG[X](y1)?NG[X](y2).因此存在一個頂點(diǎn)x0∈X使得x0y1，x0y2∈E(G).注意到G[X]是G中的一個極大團(tuán)，則|NG[X](y1)|≤|NG[X](y2)|<|X|.因此存在一個頂點(diǎn)x1∈X使得x1y1，x1y2?E(G).則G[{x0，x1，y1，y2}]?K1,3,矛盾.

情形2NG[X](y1)NG[X](y2)≠?并且NG[X](y1)NG[X](y2)≠?.

這意味著有兩個頂點(diǎn)x1，x2∈X使得x1y1，x2y2∈E(G)并且x1y2，x2y1?E(G).因此，G[{y1，x1，x2，y2}]?P4，矛盾.

接下來，因?yàn)镚[X]是G中的一個極大團(tuán)，所以|X|≥|Y|.最后，我們來證明結(jié)論3).

令y1和y2是Y中的兩個頂點(diǎn).假設(shè)NG[X](y1)≠NG[X](y2)并且NG[X](y1)∪NG[X](y2)≠|(zhì)X|.則存在兩個頂點(diǎn)x0，x1∈X使得x0y1，x0y2?E(G)并且要么x1∈NG[X](y1)NG[X](y2)要么x1∈NG[X](y2)NG[X](y1).不失一般性，我們假設(shè)x1∈NG[X](y1)NG[X](y2).這意味著x1y1∈E(G)并x1y2?E(G).這說明G[{x0，x1，y1，y2}]?P4，矛盾.

因此，定理1成立.證畢.