吳仁芳,何守偉

(湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖南 長(zhǎng)沙，410081)

?

圖中生成樹數(shù)目的一個(gè)上界

吳仁芳,何守偉

(湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖南 長(zhǎng)沙，410081)

圖論中一個(gè)重要的極值問題是刻畫具有最大生成樹數(shù)目的某些圖類的特征。利用圖中割點(diǎn)數(shù)或割邊數(shù)目,給出了連通圖中生成樹數(shù)目的上界。

生成樹;割點(diǎn);割邊

本文所涉及的圖均指無向簡(jiǎn)單的連通圖,連通的無圈圖稱為樹。若G的一個(gè)子圖本身是一棵樹,且與G有相同的頂點(diǎn)集合,則稱它為G的生成樹；G中生成樹的總數(shù)目用t(G)表示。圖論中一個(gè)重要的極值問題是刻畫具有最大生成樹數(shù)目的某些圖類的特征,它既有數(shù)學(xué)上的理論意義,又有一些重要的實(shí)際應(yīng)用,其中之一就是實(shí)驗(yàn)設(shè)計(jì)中的應(yīng)用[1]；另一個(gè)是通信網(wǎng)絡(luò)可靠性分析中的應(yīng)用[2]。目前,已有許多文獻(xiàn)[3-9]研究了在給定頂點(diǎn)數(shù)目和邊數(shù)的圖類中,刻畫了具有最大生成樹數(shù)目的極圖特征。盡管這個(gè)極值問題一般是比較難的,但是研究某些圖類中具有最大生成樹數(shù)目的特征不是平凡的也不是完全不可能的。本文,我們研究了在給定割點(diǎn)數(shù)或割邊數(shù)的圖類中刻畫了具有最大生成樹數(shù)目的極圖特征,并利用圖中割點(diǎn)數(shù)或割邊數(shù)給出了連通圖中生成樹數(shù)目的上界。

1 幾個(gè)引理

設(shè)G=(V,E)是一個(gè)頂點(diǎn)集為V=V(G),邊集為E=E(G)的圖。若G去掉一個(gè)頂點(diǎn)v導(dǎo)致G的連通分支個(gè)數(shù)的增加,則稱v為圖G的一個(gè)割點(diǎn)。圖G的無割點(diǎn)的極大連通子圖稱為G的塊。

先證明下列引理。

引理1 在所有具有n個(gè)頂點(diǎn)和k個(gè)割頂點(diǎn)的圖中,若圖G具有最大的生成樹數(shù)目,則G的每個(gè)塊是完全圖,且G的每個(gè)割頂點(diǎn)包含在恰好兩個(gè)塊中。

證明 設(shè)G是在所有n個(gè)頂點(diǎn)和k個(gè)割頂點(diǎn)的圖中一個(gè)具有最大生成樹數(shù)目的圖。若G有一個(gè)塊B不是完全圖,則在B中一對(duì)不相鄰的頂點(diǎn)之間添加一條邊e,得到一個(gè)新圖G+e,它與G具有相同的頂點(diǎn)數(shù)和割點(diǎn)數(shù),但t(G)

類似地,可以證明下面引理2。

引理2 在所有具有n個(gè)頂點(diǎn)和k條割邊e1,e2,…,ek的圖中,若圖G具有最大的生成樹數(shù)目,則G-{e1,e2,…,ek}的每個(gè)連通分支是完全圖。

引理3 [10](Cayley公式)在具有n個(gè)頂點(diǎn)的完全圖Kn中,生成樹個(gè)數(shù)為t(Kn)=nn-2。

2 主要結(jié)論

下面的定理4刻畫了給定頂點(diǎn)數(shù)和割點(diǎn)數(shù)的圖類中具有最大生成樹數(shù)目的圖特征。

定理4 設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)和k個(gè)割頂點(diǎn)的圖,則t(G)≤(n-k)n-k-2,等號(hào)成立當(dāng)且僅當(dāng)G有k個(gè)塊K2和一個(gè)塊Kn-k,且G的每個(gè)割頂點(diǎn)包含在恰好兩個(gè)塊中。

注意到,對(duì)于2≤a≤b,有aa-2bb-2≤(a+b-2)a-2(a+b-2)b-2=(a+b-2)a+b-4,等號(hào)成立當(dāng)且僅當(dāng)a=2。從而

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

(n-k)n-k-2,

等號(hào)成立當(dāng)且僅當(dāng)n0=n1=…=nk-1=2和nk=n-k,即G有k個(gè)塊K2和一個(gè)塊Kn-k。

下面的定理5刻畫了給定頂點(diǎn)數(shù)和割點(diǎn)數(shù)的圖類中具有最大生成樹數(shù)目的圖特征。

定理5 設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)和k條割邊的圖,n-k≥3。則t(G)≤(n-k)n-k-2，等號(hào)成立當(dāng)且僅當(dāng)G有k個(gè)塊K2和一個(gè)塊Kn-k。

注意到,對(duì)于1≤x≤y,有xx-2yy-2≤(x+y-1)x-2(x+y-1)y-2≤(x+y-1)x+y-3，等號(hào)成立當(dāng)且僅當(dāng)x=1。從而

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

(n-k)n-k-2。

等號(hào)成立當(dāng)且僅當(dāng)n0=n1=…=nk-1=1和nk=n-k,即G有k個(gè)塊K2和一個(gè)塊Kn-k。

定理4和定理5說明了在所有具有n個(gè)頂點(diǎn)和k個(gè)割頂點(diǎn)的圖中與所有具有n個(gè)頂點(diǎn)和k條割邊的圖中,生成樹數(shù)目的最大值是相同的。

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(11401192)

吳仁芳(1975-)，湖南汨羅人，博士生，副教授，從事圖論及應(yīng)用研究通信作者：何守偉(1988-)，河南信陽人，碩士生，從事圖論及應(yīng)用研究；E-mail:995036982@qq.com

O157.5

A