關于2樹子圖的一些性質

曾德炎，翟冬陽

(三亞學院 理工學院，海南 三亞 572022)

1 2樹子圖

用Km，Km,n，Pk分別表示頂點數為m的完全圖，m×n階完全二部圖，頂點數為k的路。設v∈V(G),X?V(G)，用G[X]和NX(v)分別表示在G中由點集X誘導的子圖和頂點v在點集X中的所有鄰點構成的集合。記G-v=G[V(G)/v]，G-X=G[V(G)/X]。文中未定義的標記參見文獻[1]。

圖1 7階2樹星圖T(7)Fig.1 7 vertices 2-tree star map T(7)

若n≥3，定義F(n)是在F(n-1)的基礎上增加一個新的點xn，并且連接xn-2xn,xn-1xn。顯然F(n)也是一個n個頂點的2樹，可以稱它為2路。圖2是F(7)。

圖2 7階2樹F(7)Fig.2 7 vertices 2-tree F(7)

主要證明了下面兩個定理：

定理1：設G是一個頂點數為n的2樹，設X?V(G)，其中|X|=k，3≤k≤n-1，則G中由頂點集X誘導的子圖是某個頂點數為k的2樹G1的子圖。

對于k=n-1的情形，不僅證明了G1的存在性，并且找出了G1。

定理2： 設G是一個頂點數為n的2樹，設xy∈C(G)，其中xy被s個耳朵z,z1,…,zs-1粘貼。若n≥6，則G中由頂點集V(G)/{x,y,z}誘導的子圖是某個頂點數為n-3的2樹的生成子圖。若n≥8，則G中由頂點集V(G)/{x,y,z}誘導的子圖是某個頂點數為n-3的2樹T的生成子圖，并且T≠T(n-3)。

2 證明

為證明定理1和定理2，用到以下已知結論：

定理3[2]：設G是一個頂點數為n的2樹。則：

(1)G中至少有兩個耳朵；

(2)G中度為2的頂點是G的耳朵；

(3)G中不存在兩個耳朵相鄰，除非G=K3；

(4)G中不包含長度至少為4的無弦圈；

(5)G是一個2連通圖。

定理4[3]：G中的每一條邊都可作為基礎，通過反復粘貼耳朵將G構造。

通過定理4，能很快構造出4個頂點2樹且只有K4-e，也就是T(4)，如圖3。

圖3 唯一的4階2樹K4-eFig.3 Only 4 vertices 2-tree K4-e

5個頂點2樹只有兩個，分別是K5-K3和K5-P4。由于K5-K3=T(5)，因此K5-P4是唯一一個非星圖的5階2樹。圖4是K5-K3，圖5是K5-P4。

圖4 5階2樹K5-K3Fig.4 5 vertices 2-tree K5-K3

圖5 5階2樹K5-P4Fig.5 5 vertices 2-tree K5-P4

同樣的方法，構造出6個頂點的2樹有5個，7個頂點的2樹有12個。對于7個頂點的2樹，有一些很易證明的性質:設G的一個頂點數為7的2樹，則在G中能找到兩個點x,y，使得G-{x,y}是P5的子圖；在G中能找到兩個點u,v，使得G-{u,v}是K3∪P2的子圖;若G不是7個頂點的星圖T(7)，則在G中能找到一個頂點z，使得G-z是6個頂點的2路F(6)的子圖。

為證明定理1和定理2，先證明下列會用到的引理：

引理1：設G是一個頂點數為n的2樹，其中n≥4，設v∈V(G)，則G-v是某個n-1階2樹的生成子圖。

證明：對n用歸納假設法。當n=4時，由于三個頂點的2樹只有一個K3，G-v顯然是這個唯一的三階2樹K3的子圖。也就是說當n=4時，引理1成立。假設n≠4，也就是n≧5。若v是G的一個耳朵，則顯然G-v是一個頂點數為n-1的2樹，因此G-v是某個n-1階2樹的生成子圖。現在假設v不是G的耳朵，設u是G的一個耳朵。若v∈NG(u)，記G1=G-u，則G1是一個頂點數為n-1的2樹，并且G-v是G1的一個生成子圖，從而G-v是某個n-1階2樹的生成子圖。若v不屬于點集NG(u)，由于G-u是一個頂點數為n-1的2樹，根據歸納假設可知G-{u,v}是某個頂點數為n-2的2樹G2的生成子圖。顯然NG(u)是V(G2)的子集，并且NG(u)在G2中的誘導子圖為K2。現在在G2的基礎上增加一個新的頂點u，使得u與NG(u)中的每一個頂點都連邊，得到的新圖記為G3。顯然G3是一個頂點數為n-1的2樹，并且G3包含G-v作為子圖。也就是說G-v是n-1階2樹G3的生成子圖。引理得證。

引理2：設G是一個頂點數為n的2樹，其中n≥5，設V′?V(G)，其中|V′|=s≤n-3。則G-V′是某個n-s階2樹的生成子圖。

證明：對s用歸納假設法。由引理1可知，當s=1時，定理2成立。假設2≤s≤3，設v∈V′。根據歸納假設可知G-(V′-v)是某個頂點數為n-(s-1)的2樹G1的生成子圖。由引理1可知，G1-v是某個頂點數為n-s的2樹的生成子圖。因為G-V′是G1-v的一個生成子圖，所以G-V′也是某個頂點數為n-s的2樹的生成子圖。引理得證。

定理1的證明：設G是一個頂點數為n的2樹，設X?V(G)，其中|X|=k，其中k≧3。由引理1可知，定理1對于k=n-1的情形是成立的(令X=V(G)-{v}即可)，證明了G中由頂點集X誘導的子圖是某個頂點數為k的2樹G1的子圖。由引理2可知，定理1對于4≤k≤n-2的情形是成立的(令X=V(G)-V′即可)。證畢。

引理3：設G是一個頂點數為n的2樹，其中n≥6，G≠T(n)。設B(G)是G中所有耳朵構成的點集，C(G)={e(u)|u∈B(G)}，則|C(G)|≥2。

證明：若|C(G)|=1，不妨設C(G)={xy}，則G中所有的耳朵都粘貼在xy上，即B(G)中所有的點都粘貼在xy上。因此G=T(n)，矛盾。設G′=G-B(G)，由于G≠T(n)，有G′中的頂點個數大于等于3，并且G′是一個2樹使得V(G′)-{x,y}中的每一個頂點的度均大于等于3，因此G′≠K3(2樹K3中有3個2度點)。由定理3(1)可知，G′中至少有兩個耳朵，即兩個度為2的頂點，因此x,y是G′中有且僅有的兩個耳朵，由定理3(3)可知，G′中的耳朵互不相鄰，這與xy∈C(G)(若xy∈C(G)，則xy是G中的一條邊)矛盾。因此|C(G)|≥2。引理得證。

引理4：設G是一個頂點數為n的2樹，其中n≥6，設xy∈C(G)，其中xy被s個耳朵z,z1,…,zs-1粘貼，則G-{x,y,z}是某個頂點數為n-3的2樹的生成子圖。

證明：設G≠T(n)，設G′=G-{z,z1,…,zs-1}。則G′是一個頂點數為n-s的2樹。由C(G)中至少有兩條邊(引理3的結論|C(G)|≥2)，有n-s≥4。根據定理4可知，G′可以在xy的基礎上通過反復增加新的頂點，并且讓這些新的頂點與圖中的某條邊的兩個端點相連構造而成。在由xy構造G′的過程中，設y′是第一個頂點，讓y′粘貼到xy上。因為xy在G′中沒有被耳朵粘貼，所有y′在G′中的度大于2。因此xy′或yy′必須被至少一個新的頂點粘貼。設x′是第一個粘貼到xy′或yy′上的新頂點。不是一般性，設x′粘貼到了xy′上。設{x1,…,xt}是V(G′)的子集，其中x1,…,xt均粘貼到了xx′上。設{y1,…,yt′}也是V(G′)的子集，其中y1,…,yt′均粘貼到了yy′上。記

在G″中定義頂點x為頂點x′，定義頂點y為頂點y′，并且粘貼z,z1,…,zs-1到x′y′上，重新得到的圖記為G?。此時，G?就是一個頂點數為n-3的2樹，并且G-{x,y,z}是頂點數為n-3的2樹G?的一個生成子圖。

若G=T(n)，則G-{x,y,z}是一個頂點數為n-3的獨立集。顯然，此時G-{x,y,z}是任意一個頂點數為n-3的2樹的生成子圖。引理得證。

引理5：設G是一個頂點數為n的2樹，其中n≥8，設xy∈C(G)，其中xy被s個耳朵z,z1,…,zs-1粘貼。則G-{x,y,z}是某個頂點數為n-3的2樹T的生成子圖，并且T≠T(n-3)。

證明：記H=G-{x,y,z}。若s≥2，則G-z1是一個頂點數為n-1的2樹，根據引理4，(G-z1)-{x,y,z}是某個頂點數為n-4的2樹T′的生成子圖。可以在T′的基礎上新增一個頂點z1，讓其粘貼到一條合適的邊上得到一個頂點數為n-3的新2樹T，使得T≠T(n-3)。顯然，H是T的一個生成子圖。因此，對于C(G)中的任意一條邊xy均只被一個耳朵粘貼。對于這種情形，用反證法證明，即假設包含H作為生成子圖的n-3個頂點的2樹只能是T(n-3)。

設V(T(n-3))={u,v,w1,…,wn-5}，其中uv∈C(T(n-3))，并且uv被n-5個耳朵w1,…,wn-5粘貼。若存在1≤p≤n-5，使得wpu?E(H)。則H是n-3個頂點的2樹T=T(n-3)-wpu+wpwq(1≤q≤n-5,q≠p)的生成子圖。顯然T≠T(n-3)，矛盾。

因此對于任意1≤p≤n-5，均有wpu∈E(H)。同理可得，對于任意1≤p≤n-5，均有wpv∈E(H)。因此，若uv∈E(H)，則H=T(n-3)；若uv?E(H)，則H=K2,n-5。

如果H=T(n-3)，|E(G)|=2n-3和|E(H)|=2(n-3)-3=2n-9，把G中由頂點集{x,y}與頂點集V(H)之間連接的邊的數量記作eG({x,y},V(H))，則eG({x,y},V(H))=(2k-3)-(2k-9)-3=3。若|NH(x)|=3或|NH(y)|=3，則G顯然不是一個2連通圖，這與定理3(5)矛盾(即與G是2連通圖矛盾)。因此|NH(x)|≤2，|NH(y)|≤2。記W={w1,…,wn-5}。設|NH(x)|=2或|NH(y)|=2，不失一般性，不妨設|NH(x)|=2，設wix和wjx是G中的兩條邊，則xwiuwjx在G中是一個長度為4的無弦圈，這與定理3(4)矛盾(即與G中不含長度大于等于4的無弦圈矛盾)。若|NH(x)|=|NH(y)|=1，設wrx和wty是G中的兩條邊，則xwruwtyx在G中是一個長度為5的圈。因為eG({x,y},V(H))=3，所以圈xwruwtyx中至多有一條弦，因此G中至少存在一個長度為4的無弦圈，這與定理3(4)矛盾(即與G中不含長度大于等于4的無弦圈矛盾)。若|NH(x)|+|NH(y)|≤1，則uv∈C(G)并且uv被粘貼n-5-1≥2個耳朵，這與C(G)中的任意一條邊均只被一個耳朵粘貼矛盾。

若H=K2,n-5，則H中存在長度為4的無弦圈，從而G中存在長度為4的無弦圈，這與定理3(4)矛盾(即與G中不含長度大于等于4的無弦圈矛盾)。

因此，假設不成立，也就是說G-{x,y,z}是某個頂點數為n-3的2樹T的生成子圖，并且T≠T(n-3)。引理得證。

定理2的證明：設G是一個頂點數為n的2樹，設xy∈C(G)，其中xy被s個耳朵z,z1,…,zs-1粘貼。引理4證明了：若n≥6，則G中由頂點集V(G)/{x,y,z}誘導的子圖是某個頂點數為n-3的2樹的生成子圖。引理5進一步證明了：若n≥8，則G中由頂點集V(G)/{x,y,z}誘導的子圖是某個頂點數為n-3的2樹T的生成子圖，并且T≠T(n-3)。證畢。