曾德炎，饒 陽，張勇軍

(海南大學信息科學技術學院，海南?？?70228)

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

圖G是k樹當且僅當G=Kk+1或者G中存在一個度為k的頂點v使得與v相鄰的k個點構成了一個團，且G-v為k樹，且v是k樹G的一個耳朵.當k=1時G是1樹，也就是通常所說的樹.關于1樹有以下結論，G是1樹當且僅當G中沒有K3-minor，且G是1連通圖.關于k樹的研究，BODLAENDER等人做了一系列工作，詳細參考文獻［1-7］.

1 主要定理及其證明

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

為了證明2樹的刻畫，先介紹2樹的一些性質.

性質1［9-10］對于每一個頂點數為n的2樹T都有如下性質

(1)T中沒有K4-minor;

(2)T中沒有長度大于3的無弦圈;

(3)T是2連通圖;

(4)2個2樹通過一條邊相粘形成的圖形仍是2樹.

定理1 設G是頂點數為n的圖.當且僅當G滿足下列條件，則G是一個2樹

(1)G中沒有K4-minor;

(2)G中沒有長度大于3的無弦圈;

(3)G是2連通圖.

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

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

定理1證畢.

為了證明3樹的刻畫，先證明下面的引理.

引理1 T1和T2為任意2個3樹，G是由T1和T2通過一個K3相粘形成，則G也是3樹.

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

定理2 設G是頂點數為n的圖，當且僅當G滿足下列條件，則G是一個3-樹

(1)G中沒有K5-minor;

(2)G中沒有長度大于3的無弦圈;

(3)G是3連通圖.

證明 必要性

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

(2)當n=4時，G中顯然沒有長度大于3的無弦圈.假設當n＜k也成立，只需證當n=k成立即可.由于T1中沒有長度大于3的無弦圈，若G中有長度大于3的無弦圈，設為C，則必有u V(C).而在G中只有3個無弦圈含有u點，且圈長均為3.故G中沒有長度大于3的無弦圈.

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

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

定理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］范益政.圖論導引［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.