曾德炎，饒 陽(yáng)，張勇軍

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南海口570228)

本文討論的圖都是簡(jiǎn)單圖.設(shè)G是一個(gè)圖，x V(G)且y V(G)，則d(x，y)表示G中x，y 2點(diǎn)之間的距離.設(shè)X?V(G)且Y?V(G)，則NX(Y)表示Y在X中的鄰集，G［X］表示X在G中的導(dǎo)出子圖.G中有 Kt-minor表示 G 可以通過(guò)收縮邊，刪除邊和頂點(diǎn)得到 Kt.設(shè) G1［x1，x2，…，xt］=Kt，G2［y1，y2，…，yt］=Kt且G是由G1和G2通過(guò)Kt相粘得到，表示G是通過(guò)將G1中的xi與G2中的yi重合而成，其中1≤i≤t，使得 G1?G，G2?G.

圖G是k樹(shù)當(dāng)且僅當(dāng)G=Kk+1或者G中存在一個(gè)度為k的頂點(diǎn)v使得與v相鄰的k個(gè)點(diǎn)構(gòu)成了一個(gè)團(tuán)，且G-v為k樹(shù)，且v是k樹(shù)G的一個(gè)耳朵.當(dāng)k=1時(shí)G是1樹(shù)，也就是通常所說(shuō)的樹(shù).關(guān)于1樹(shù)有以下結(jié)論，G是1樹(shù)當(dāng)且僅當(dāng)G中沒(méi)有K3-minor，且G是1連通圖.關(guān)于k樹(shù)的研究，BODLAENDER等人做了一系列工作，詳細(xì)參考文獻(xiàn)［1-7］.

1 主要定理及其證明

Menger定理［8］設(shè)u和v是圖G的不鄰接的2個(gè)頂點(diǎn)，則u-v分離集中定點(diǎn)的最小個(gè)數(shù)等于G中內(nèi)部不相交u-v路的最大個(gè)數(shù).

為了證明2樹(shù)的刻畫(huà)，先介紹2樹(shù)的一些性質(zhì).

性質(zhì)1［9-10］對(duì)于每一個(gè)頂點(diǎn)數(shù)為n的2樹(shù)T都有如下性質(zhì)

(1)T中沒(méi)有K4-minor;

(2)T中沒(méi)有長(zhǎng)度大于3的無(wú)弦圈;

(3)T是2連通圖;

(4)2個(gè)2樹(shù)通過(guò)一條邊相粘形成的圖形仍是2樹(shù).

定理1 設(shè)G是頂點(diǎn)數(shù)為n的圖.當(dāng)且僅當(dāng)G滿足下列條件，則G是一個(gè)2樹(shù)

(1)G中沒(méi)有K4-minor;

(2)G中沒(méi)有長(zhǎng)度大于3的無(wú)弦圈;

(3)G是2連通圖.

證明 由性質(zhì)1可知必要性顯然成立，只需要證明其充分性即可.

對(duì)n用歸納法.當(dāng)n=3時(shí)，顯然成立.假設(shè)3＜n＜k時(shí)，定理1也成立.只需證n=k時(shí)也成立即可.由于G中沒(méi)有K4-minor，所以G不是完全圖.則存在2點(diǎn)u，v G，使得d(u，v)≥2.又G是2連通圖，根據(jù)Menger定理，u，v間至少有2條內(nèi)部不相交的路.設(shè)P1=ux1x2…xi0v，P2=uy1y2…yj0v為u，v之間的2條內(nèi)部不相交且長(zhǎng)度之和為最小的路.顯然P1，P2組成了一個(gè)長(zhǎng)度大于3的圈.設(shè)X={x1，…，xj0}，Y={y1，…，yj0}，X0=NX(Y)，Y0=NY(X). 因此 X0≠?，Y0≠?. 現(xiàn)取 xiX，yiY 使得 xiyiE(G)，且i+j達(dá)到最小.此時(shí)ux1…xiyj…y1u構(gòu)成了一個(gè)無(wú)弦圈，其長(zhǎng)度為i+j+1.因此i+j=2，即x1與y1相鄰.在 G-{x1，y1}中 u，v 2 點(diǎn)不連通，否則 G 中存在 K4-minor.設(shè) H1，H2，…，Ht為 G-{x1，y1}的 t個(gè)連通分支，此時(shí)G［V(H1)∪{x1，y1}］，G［V(H2)∪{x1，y1}］，…，G［V(Ht)∪{x1，y1}］均滿足定理 1 中的條件(1)、(2)和(3)，即都是2樹(shù)，分別設(shè)為T1，T2，…，Tt.顯然G是由t個(gè)2樹(shù)通過(guò)邊x1y1粘在一起而形成.由性質(zhì)1可知G是2樹(shù).

定理1證畢.

為了證明3樹(shù)的刻畫(huà)，先證明下面的引理.

引理1 T1和T2為任意2個(gè)3樹(shù)，G是由T1和T2通過(guò)一個(gè)K3相粘形成，則G也是3樹(shù).

證明 設(shè)|T1|=s，|T2|=t，V(K3)={x，y，z}.對(duì)s，t進(jìn)行歸納證明.由3樹(shù)的定義可知，當(dāng)s=4或t=4時(shí)引理1顯然成立.假設(shè)當(dāng)4＜s＜m，4＜t＜n時(shí)引理1也成立.只需證當(dāng)s=m，t=n時(shí)也成立即可.對(duì)于每一個(gè)頂點(diǎn)數(shù)大于4的3樹(shù)，至少有2個(gè)耳朵，且耳朵互不相鄰.也就是說(shuō)T1中至少有一個(gè)耳朵 u{x，y，z}，T2中至少有一個(gè)耳朵v{x，y，z}.由假設(shè)可知G-{u，v}為3樹(shù).顯然可通過(guò)在圖G-{u，v}的基礎(chǔ)上加耳朵u，v產(chǎn)生G.故G也是3樹(shù).

定理2 設(shè)G是頂點(diǎn)數(shù)為n的圖，當(dāng)且僅當(dāng)G滿足下列條件，則G是一個(gè)3-樹(shù)

(1)G中沒(méi)有K5-minor;

(2)G中沒(méi)有長(zhǎng)度大于3的無(wú)弦圈;

(3)G是3連通圖.

證明 必要性

(1)對(duì)n進(jìn)行歸納證明.對(duì)于n=4的3樹(shù)G顯然沒(méi)有K5-minor.假設(shè)當(dāng)n＜k時(shí)也成立，只需證n=k時(shí)成立即可.設(shè)u為G的一個(gè)耳朵且T1=G-u.由假設(shè)可知T1中沒(méi)有K5-minor.若G中有K5-minor，G通過(guò)收縮邊，刪除邊和頂點(diǎn)得到K5，則一定有u V(K5).從而dG(u)≥4，矛盾.故G也沒(méi)有K5-minor.

(2)當(dāng)n=4時(shí)，G中顯然沒(méi)有長(zhǎng)度大于3的無(wú)弦圈.假設(shè)當(dāng)n＜k也成立，只需證當(dāng)n=k成立即可.由于T1中沒(méi)有長(zhǎng)度大于3的無(wú)弦圈，若G中有長(zhǎng)度大于3的無(wú)弦圈，設(shè)為C，則必有u V(C).而在G中只有3個(gè)無(wú)弦圈含有u點(diǎn)，且圈長(zhǎng)均為3.故G中沒(méi)有長(zhǎng)度大于3的無(wú)弦圈.

(3)當(dāng)n=4時(shí)，G為3連通圖.假設(shè)當(dāng)n＜k也成立，只需證當(dāng)n=k成立即可.由于T1為3連通圖，且dT1(u)=3，所以G也是3連通圖.

充分性 對(duì)n用歸納法.當(dāng)n=4時(shí)，顯然成立.假設(shè)4＜n＜k時(shí)，定理2也成立.只需證n=k時(shí)也成立即可.由于G中沒(méi)有K5-minor，所以G不是完全圖.則存在2點(diǎn)u，v V(G)，使得d(u，v)≥2.又G是3連通圖，所以u(píng)，v之間至少有3條內(nèi)部不相交的路.設(shè)P1=ux1x2…xi0v，P2=uy1y2…yj0v，P3=uz1z2…zs0v為u，v之間的3條內(nèi)部不相交且長(zhǎng)度之和為最小的路.設(shè) X={x1，…，xi0}，Y={y1，…，yj0}，X0=NX(Y)，Y0=NY(X)，顯然P1和P2組成了一個(gè)長(zhǎng)度大于3的圈.因此X0≠?，Y0≠?.現(xiàn)取xiX，yiY使得xiyiE(G)，且i+j達(dá)到最小.此時(shí)ux1…xiyj…y1u構(gòu)成了一個(gè)無(wú)弦圈，其長(zhǎng)度為i+j+1.因此i+j=2，即x1與y1相鄰.同理可證x1與z1相鄰，y1與z1相鄰.在G-{x1，y1，z1}中u，v2點(diǎn)不連通，否則G中有K5-minor.設(shè) H1，H2，…，Ht為 G-{x1，y1，z1}的 t個(gè)連通分支. 此時(shí) G［V(H1)∪{x1，y1，z1}］，G［V(H2)∪{x1，y1，z1}］，…，G［V(Ht)∪{x1，y1，z1}］均滿足定理 2 中的條件(1)、(2)和(3)，即都是 3 樹(shù)，分別設(shè)為T1，T2，…，Tt.顯然G是由t個(gè)3樹(shù)通過(guò)頂點(diǎn)x1，y1，z1組成的K3粘在一起形成，由引理1可知G是3樹(shù).

定理2證畢.

［1］BODLAENDER H L.A partial k-arboretum of graphs with bounded treewidth［J］.Theoret Comput Sci. ，1998，209(1/2):1-45.

［2］REED B A，SALES C L.Recent Advanced in Algorithms and Combinatorics［M］.New York:Springer，2003.

［3］DUKE R A，WINKLER P M.Degree sets of k-trees:Small k［J］.Israel J Math.，1987，40(3/4):296-306.

［4］DUKE R A，WINKLER P M.Realizability of almost all degree sets by k trees:proceedings of the 13th Southeastern Conference on Combinatorics Graph Theory and Computing，Boca Raton，F(xiàn)ebruary 15-18，1982［C］.Manitoba:Utilitas Mathematica，1982.

［5］DUKE R A，WINKLER P M.Degree sets of k-trees:Small degrees［J］.Utilitas Math.，1983，23:177-200.

［6］KAPPOR S F，POLIMENI A D，WALL C E.Degree sets for graphs［J］.Fund Math.，1977，97:183-194.

［7］LI D Y，MAO J Z.Degree sequences of maximal outerplanar graphs［J］.Central China Normal Univ Natur Sci.，1992，26(3):270-273.

［8］范益政.圖論導(dǎo)引［M］.北京:人民郵電出版社，2007.

［9］BOSE P，DUJMOVIC＇V，KRIZANC D，et al.A characterization of the degree sequences of 2-trees［J］.Journal of Graph Theory Graphs.，2008，58:191-209.

［10］CAI Lei-zhen.On spanning 2-trees in a graph［J］.Discrete Applied Mathematics，1997，74:203-216.