图中生成树数目的一个上界

吴仁芳,何守伟

(湖南师范大学 数学与计算机科学学院，湖南 长沙，410081)



图中生成树数目的一个上界

吴仁芳,何守伟

(湖南师范大学 数学与计算机科学学院，湖南 长沙，410081)

图论中一个重要的极值问题是刻画具有最大生成树数目的某些图类的特征。利用图中割点数或割边数目,给出了连通图中生成树数目的上界。

生成树;割点;割边

本文所涉及的图均指无向简单的连通图,连通的无圈图称为树。若G的一个子图本身是一棵树,且与G有相同的顶点集合,则称它为G的生成树；G中生成树的总数目用t(G)表示。图论中一个重要的极值问题是刻画具有最大生成树数目的某些图类的特征,它既有数学上的理论意义,又有一些重要的实际应用,其中之一就是实验设计中的应用[1]；另一个是通信网络可靠性分析中的应用[2]。目前,已有许多文献[3-9]研究了在给定顶点数目和边数的图类中,刻画了具有最大生成树数目的极图特征。尽管这个极值问题一般是比较难的,但是研究某些图类中具有最大生成树数目的特征不是平凡的也不是完全不可能的。本文,我们研究了在给定割点数或割边数的图类中刻画了具有最大生成树数目的极图特征,并利用图中割点数或割边数给出了连通图中生成树数目的上界。

1 几个引理

设G=(V,E)是一个顶点集为V=V(G),边集为E=E(G)的图。若G去掉一个顶点v导致G的连通分支个数的增加,则称v为图G的一个割点。图G的无割点的极大连通子图称为G的块。

先证明下列引理。

引理1 在所有具有n个顶点和k个割顶点的图中,若图G具有最大的生成树数目,则G的每个块是完全图,且G的每个割顶点包含在恰好两个块中。

证明 设G是在所有n个顶点和k个割顶点的图中一个具有最大生成树数目的图。若G有一个块B不是完全图,则在B中一对不相邻的顶点之间添加一条边e,得到一个新图G+e,它与G具有相同的顶点数和割点数,但t(G)

类似地,可以证明下面引理2。

引理2 在所有具有n个顶点和k条割边e1,e2,…,ek的图中,若图G具有最大的生成树数目,则G-{e1,e2,…,ek}的每个连通分支是完全图。

引理3 [10](Cayley公式)在具有n个顶点的完全图Kn中,生成树个数为t(Kn)=nn-2。

2 主要结论

下面的定理4刻画了给定顶点数和割点数的图类中具有最大生成树数目的图特征。

定理4 设G是一个具有n个顶点和k个割顶点的图,则t(G)≤(n-k)n-k-2,等号成立当且仅当G有k个块K2和一个块Kn-k,且G的每个割顶点包含在恰好两个块中。

注意到,对于2≤a≤b,有aa-2bb-2≤(a+b-2)a-2(a+b-2)b-2=(a+b-2)a+b-4,等号成立当且仅当a=2。从而

(n0+n1+…+nk-2k)n0+n1+…+nk-2k-2=

(n-k)n-k-2,

等号成立当且仅当n0=n1=…=nk-1=2和nk=n-k,即G有k个块K2和一个块Kn-k。

下面的定理5刻画了给定顶点数和割点数的图类中具有最大生成树数目的图特征。

定理5 设G是一个具有n个顶点和k条割边的图,n-k≥3。则t(G)≤(n-k)n-k-2，等号成立当且仅当G有k个块K2和一个块Kn-k。

注意到,对于1≤x≤y,有xx-2yy-2≤(x+y-1)x-2(x+y-1)y-2≤(x+y-1)x+y-3，等号成立当且仅当x=1。从而

(n0+n1+…+nk-k)n0+n1+…+nk-k-2=

(n-k)n-k-2。

等号成立当且仅当n0=n1=…=nk-1=1和nk=n-k,即G有k个块K2和一个块Kn-k。

定理4和定理5说明了在所有具有n个顶点和k个割顶点的图中与所有具有n个顶点和k条割边的图中,生成树数目的最大值是相同的。

[1]C.Cheng.Maximizing the total number of spanning trees in a graph:two related problems in graph theory and optimization design theory[J].J.Combin.Theory(B),1981,31:240-248.

[2]F.Boesch,X.Li,C.Suffel.On the existence of uniformly most reliable networks[J].Networks,1991,21:181-194.

[3]B.Gilbert,W.Myrvold.Maximizing spanning trees in almost complete graphs[J].Networks,1997,30:23-30.

[4]A.Kelmans.On graphs with the maximum number of spanning trees[J].Random Struct.Algorithms,1996,9:177-92.

[5]A.Kelmans,V.Chelnokov.A certain polynomial of a graph and graphs with an extremal number of trees[J].J.Combin.Theory(B),1974,16:197-214.

[6]B.Bresar,S.Klavzar,D.F.Rall.Domination game played on trees and spanning subgraphs[J].Discrete Mathematics,2013,313:915-923.

[7]G.Fan,Y.Hong,Q.Liu.Ore’s condition for completely independent spanning trees[J].Discrete Applied Mathematics,2014,177:95-100.

[8]W.Yan.On the number of spanning trees of some irregular line graphs[J].J.Combin.Theory(A),2013,120:1642-1648.

[9]P.Bonsma,F.Zickfeld.Improved bounds for spanning trees with many leaves[J].Discrete Mathematics,2012,312:1178-1194.

[10]A.Cayley.A theorem on trees[J].Quart.J.Math.1889,23:376-378.

An upper bound for the number of spanning trees in a graph

WU Renfang,HE Shouwei

(College of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China)

Characterizing the graph with the maximal number of spanning trees is one of the important problems in the extremal graph theory.In this paper,we give an upper bound for the number of spanning trees of a connected graph in terms of its number of cut vertices or cut edges.

spanning tree; cut vertex; cut edge

1672-7010(2016)03-0025-03

2016-01-20

国家自然科学基金资助项目(11401192)

吴仁芳(1975-)，湖南汨罗人，博士生，副教授，从事图论及应用研究通信作者：何守伟(1988-)，河南信阳人，硕士生，从事图论及应用研究；E-mail:995036982@qq.com

O157.5

A