对于2树和3树的一个刻画

曾德炎，饶 阳，张勇军

(海南大学信息科学技术学院，海南海口570228)

本文讨论的图都是简单图.设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≠Ø. 现取 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≠Ø.现取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，February 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.