韓 靜,宋星星,李 玥

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

0 引言

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

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

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

一般的，我們通常從圖的參數(shù)角度去研究圖的性質(zhì)，例如：最小度，圖的獨立數(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}的連通圖.則它的頂點集合可以劃分成兩個子集X和Y使得以下三個結(jié)論成立：

1)G[X]和G[Y]都是團；

2)|X|≥|Y|；

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

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

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

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

接下來，我們首先斷言G[Y]是一個團.否則存在兩個頂點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).因此存在一個頂點x0∈X使得x0y1，x0y2∈E(G).注意到G[X]是G中的一個極大團，則|NG[X](y1)|≤|NG[X](y2)|<|X|.因此存在一個頂點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)≠?.

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

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

令y1和y2是Y中的兩個頂點.假設(shè)NG[X](y1)≠NG[X](y2)并且NG[X](y1)∪NG[X](y2)≠|(zhì)X|.則存在兩個頂點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成立.證畢.