一類獨立數為4圖的結構研究

周秀君

(廣東紡織職業技術學院基礎部，廣東 佛山 528041)

一類獨立數為4圖的結構研究

周秀君

(廣東紡織職業技術學院基礎部，廣東 佛山 528041)

圖論研究中一個很重要的方面是利用圖的各種參數來刻畫圖的結構。通過對圖的2個重要參數-獨立數和連通度的研究,給出獨立數4,而連通度不超過1圖的結構特征。

獨立數；連通度；完全圖；哈密頓圖

1 基本概念

僅考慮簡單圖,下面出現但未介紹的定義和圖論術語參看文獻[1,2]，G=(V(G),E(G)),V(G)表示G的頂點集，E(G)表示G的邊集。對?u∈V(G),NG(u)={v|uv∈E(G),v∈V(G)}。若H?G，則NH(u)={v|uv∈E(H),v∈V(H)}。α(G)和κ(G)分別表示G的獨立數和連通度。用A=B定義A就是B。如果圖G含一個生成圈，則稱G是哈密頓的。哈密頓路是圖生成圖，簡稱為哈路。(x,y)-哈路是圖中以x和y為2端點的生成路。若G=(V(G),E(G))，對?u,v∈V(G)，都有uv∈E(G),則稱G是完全圖。若H1和H2是圖G的2個導出子圖，則H1-H2和H1∪H2分別表示G中由V(H1)-V(H2)和V(H1)∪V(H2)的導出子圖。H1?H2定義為H1∪H2且V(H1)∩V(H2)=Φ。文獻[2-4]給出了圖的獨立數為1，2或3，而連通度任意取值時圖的結構特征。下面，筆者研究獨立數為4，而連通度不超過1圖的結構特征。

首先定義10類圖：

K={G:G是完全的}HH={G：G是哈密爾頓的}

G0={G=H1?H2,Hi∈K,i=1,2,α(G)=2}

G1={G=H1?H2?H3,Hi∈K,i=1,2,3,α(G)=3}

G2={G=H1?H2,H1∈K,H2∈HH,α(G)=3}

G4={G=H1?H2,H1∈K,H2∈G2,α(G)=4}

G5={G=H1?{x}?H2,H1∈K,H2∈HH,α(G)=4}

G6={G=H1?H2,α(H1)=α(H2)=2,α(G)=4}

G7={G=H1?H2,H1∈K,H2∈HH,α(G)=4}

2 相關引理

引理1[3]令G是一個階為n(n≥3)的圖，如果α(G)≤κ(G)，那么G是哈密頓的。

引理2{x1,x2}是G的一最小割點集，H是G-(x1,x2}一個連通分支，其中α(H)=κ(H)=2。令H′=G[V(H)∪{x1,x2}]，則下列結論至少有一個成立:

(1)H′中有(x1,x2)-哈路;

證明令{y1,y2}是H的一割點集，H-{y1,y2}有2個連通分支Hi,Hi∈K,i=1,2。不妨設min{|H1|,|H2|}≥2。由于α(H)=2，因此(N(y1)∪N(y2))∩V(Hj)?V(Hj),j=1,2。于是，G[V(Hi)∪{y1,y2}]有(y1,y2)哈路Pi,i=1,2。

先設G[V(Hi)∪{x1,x2}]有(x1,x2)-哈路，i∈{i,2}。易知H′中有(x1,x2)哈路，即(1)成立。

下考慮G[V(Hi)∪{x1,x2}]沒有(x1,x2)-哈路的情形，i=1,2。

引理3{x1,x2}是G的一最小割點集，H是G-{x1,x}一個連通分支，其中H∈G0,設H=H1?H2,H1含H的一割點x。則下面2個結論至少一個成立：

(1)G[V(H)∪{x1,x2}]有(x1,x2)-哈路；

(2)α(G[V(H)∪{xi}])=3,i∈{1,2},且G[V(H2)∪{x1,x2,x}]或G[V(H2)∪{x1,x2}]有(x1,x2)-哈路。

證明不妨設G[V(H2)∪{x,x2}]有(x,x2)-哈路P。若N(x1)∩V(H1)/{x}=，則G[V(H1)∪{x1}]有(x1,x)-哈路。它和P形成G[V(H)∪{x1,x2}]中(x1,x2)-哈路，此時(1)成立。

下設N(x1)∩V(H1)/{x}=Φ,則N(x2)∩V(H1)/{x}=Φ。于是，G[V(H1)∪{x2}]有(x,x2)-哈路Q。如果G[V(H2)∪{x,x1}]有(x,x1)-哈路，則它和Q形成G[V(H)∪{x1,x2}]中(x1,x2)-哈路，此時(1)成立。否則，N(x1)∩V(H2)=Φ或|(N(x1)∪N(x))∩V(G2)|=1。若N(x1)∩V(H2)=Φ，則N(x1)∩V(H1)={x}，故x1x和P形成G[V(H2)∪{x1,x2,x}]中(x1,x2)-哈路。若|(N(x1)∪N(x))∩V(H2)|=1，則G[V(H2)∪{x1,x2}]有(x1,x2)-哈路。選取u1∈V(H1)/{x},u2∈V(H2)/N(x1),使得{u1,u2,x1}是獨立集。因此α(G[V(H)∪{x1}]=3。此時(2)成立。故引理3成立。

3 主要結論的證明

定理1如果α(G)=2，則G∈HH∪G0。

證明若κ(G)≥2，根據引理1，則G∈H。下設κ(G)≤1。

先設κ(G)=1。令x是G的一割點，則G-x有2個連通分支H1和H2，這里H1和H2都是完全圖。由于α(G)=2，則Hi?{x}至少有一個完全圖，i=1,2。因此G=G|V(Hi)∪{x}]?H3-i∈G0。

再設κ(G)=0，則G有2個連通分支H1和H2，這里H1和H2都是完全圖。由于α(G)=2，則Hi至少有一個是完全圖，i=1,2。因此G=V(Hi)?H3-i∈G0。故定理1成立。

證明若κ(G)≥3,根據引理1,則G∈H。下設κ(G)≤2,分成3種情形討論。

情形1κ(G)=0。令G有t個連通分支H1,…,Ht,可知2≤t≤α(G)=3。若t=3，由于α(G)=3,則H1,H2,H3都是完全圖，則G∈G1。下設t=2。不妨設α(H1)≤α(H2)。由于α(G)=3,則α(H1)=1和α(H2)=2。根據定理1，H2∈H∪G0，故G∈G1∪G2。

情形2κ(G)=1。設x是G的一割點，G-x有t個連通分支H1,…,Ht,可知2≤t≤α(G)=3。若t=3，由于α(G)=3，因此α(Hi)=1,i=1,…,3,且?j∈{1,2,3}，使得Hj∪{x}∈K。故G∈G1。

證明令G有t個連通分支H1,…,Ht。可知2≤t≤α(G)=4。若t=4，由于α(G)=3,則H1,…,H4都是完全圖，則G∈G3。

下設t=3。不妨設α(H1)≤α(H2)≤α(H3)。可知α(H3)≤α(G)-α(H1)-α(H2)≤2。由于α(G)=4，則α(H1)=α(H2)=1和α(H3)=2。根據定理1，H3∈HH∪G0，故G∈G3∪G4。

證明設x是G的一割點，G-x有t個連通分支H1,…,Ht,可知2≤t≤α(G)=4。先設t=4,由于α(G)=4，因此α(Hi)=1,i=1,…,4，且存在j∈{1,2,3,4}，使得Hj∪{x}∈K,故G∈G3。

其次設t=3。不妨設α(H1)≤α(H2)≤α(H3),于是：

α(H3)≤α(G)-α(H1)-α(H2)≤4-1-1=2

先設α(H1)=1和α(H2)=2，由定理1知，H2∈HH∪G0。若H2∈HH,則G=H1?{x}?H2∈G5。若H2∈G0，則H2=H21?H22,H21和H22都是完全的。于是，G=H1?{x}?H21?H22∈G3。

[1]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:The Macmillan Press LTD,1976.

[2]Enomoto H.Long Cycles in Triangle-free Graphs with Prescribed Independece Number adn Connectivity[J].J Combinatorial Theory,Series B,2004,91:43-55.

[3]Chvátal V，Erd?s P.Anote on Hamiltonian circuits[J].Discrete Math,1972,2:111-113.

[4]吳亞平，馮麗珠.獨立數小于4圖的結構研究[J].長江大學學報(自然科學學報)：理工，2007,4(4):29-32.

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.03.001

O157.5

1673-1409(2011)03-0001-03