曾德炎，翟冬陽(yáng)

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

1 2樹(shù)子圖

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

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

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

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

主要證明了下面兩個(gè)定理：

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

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

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

2 證明

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

定理3[2]：設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的2樹(shù)。則：

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

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

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

(4)G中不包含長(zhǎng)度至少為4的無(wú)弦圈；

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

定理4[3]：G中的每一條邊都可作為基礎(chǔ)，通過(guò)反復(fù)粘貼耳朵將G構(gòu)造。

通過(guò)定理4，能很快構(gòu)造出4個(gè)頂點(diǎn)2樹(shù)且只有K4-e，也就是T(4)，如圖3。

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

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

圖4 5階2樹(shù)K5-K3Fig.4 5 vertices 2-tree K5-K3

圖5 5階2樹(shù)K5-P4Fig.5 5 vertices 2-tree K5-P4

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

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

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

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

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

證明：對(duì)s用歸納假設(shè)法。由引理1可知，當(dāng)s=1時(shí)，定理2成立。假設(shè)2≤s≤3，設(shè)v∈V′。根據(jù)歸納假設(shè)可知G-(V′-v)是某個(gè)頂點(diǎn)數(shù)為n-(s-1)的2樹(shù)G1的生成子圖。由引理1可知，G1-v是某個(gè)頂點(diǎn)數(shù)為n-s的2樹(shù)的生成子圖。因?yàn)镚-V′是G1-v的一個(gè)生成子圖，所以G-V′也是某個(gè)頂點(diǎn)數(shù)為n-s的2樹(shù)的生成子圖。引理得證。

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

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

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

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

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

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

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

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

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

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

因此對(duì)于任意1≤p≤n-5，均有wpu∈E(H)。同理可得，對(duì)于任意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中由頂點(diǎn)集{x,y}與頂點(diǎn)集V(H)之間連接的邊的數(shù)量記作eG({x,y},V(H))，則eG({x,y},V(H))=(2k-3)-(2k-9)-3=3。若|NH(x)|=3或|NH(y)|=3，則G顯然不是一個(gè)2連通圖，這與定理3(5)矛盾(即與G是2連通圖矛盾)。因此|NH(x)|≤2，|NH(y)|≤2。記W={w1,…,wn-5}。設(shè)|NH(x)|=2或|NH(y)|=2，不失一般性，不妨設(shè)|NH(x)|=2，設(shè)wix和wjx是G中的兩條邊，則xwiuwjx在G中是一個(gè)長(zhǎng)度為4的無(wú)弦圈，這與定理3(4)矛盾(即與G中不含長(zhǎng)度大于等于4的無(wú)弦圈矛盾)。若|NH(x)|=|NH(y)|=1，設(shè)wrx和wty是G中的兩條邊，則xwruwtyx在G中是一個(gè)長(zhǎng)度為5的圈。因?yàn)閑G({x,y},V(H))=3，所以圈xwruwtyx中至多有一條弦，因此G中至少存在一個(gè)長(zhǎng)度為4的無(wú)弦圈，這與定理3(4)矛盾(即與G中不含長(zhǎng)度大于等于4的無(wú)弦圈矛盾)。若|NH(x)|+|NH(y)|≤1，則uv∈C(G)并且uv被粘貼n-5-1≥2個(gè)耳朵，這與C(G)中的任意一條邊均只被一個(gè)耳朵粘貼矛盾。

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

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

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