# On the Number of Spanning Trees of Graphs

Authors: Ş. Burcu Bozkurt; Durmuş Bozkurt
Journal: The Scientific World Journal
 (2014)

---

## Abstract

We establish some bounds for the number of spanning trees of connected graphs in terms of the number of vertices(n), the number of edges (m), maximum vertex degree (Δ1), minimum vertex degree (δ), first Zagreb index (M1), and Randić index (R-1).


---

## Body

## 1. Introduction

LetG be a simple connected graph with n vertices and m edges. Let V(G)={v1,v2,…,vn} be the vertex set and E(G)={e1,e2,…,em} the edge set of G. If any two vertices vi and vj of G are adjacent, that is, vivj∈E(G), then we use the notation vi~vj. For vi∈V(G), the degree of the vertex vi, denoted by di, is the number of the vertices adjacent to vi. Let Δ1, Δ2, and δ be the maximum, the second maximum, and the minimum vertex degree of G, respectively.LetM1=M1(G)=∑i=1n‍di2 be the first Zagreb index [1] and Rα=Rα(G)=∑vi~vj‍(didj)α the general Randić index [2] of the graph G, where α≠0 is a fixed real number. Note that the Randić index R-1=R-1(G)=∑vi~vj‍1/didj is also well studied in the literature. For more details on R-1, see [3, 4].LetKn, Kp,q(p+q=n), and Sn denote the complete graph, the complete bipartite graph, and the star graph of order n, respectively. Let G-e be the graph obtained by deleting the edge e from the graph G and let G¯ be the complement of G. Let G1∪G2 be the vertex-disjoint union of the graphs G1 and G2. The graph G1∨G2 is obtained from G1∪G2 by adding all possible edges from vertices of G1 to vertices of G2; that is, G1∨G2=G1¯∪G2¯¯ [5].The Laplacian matrix of the graphG is the matrix L(G)=D(G)-A(G), where A(G) and D(G) are the (0,1)-adjacency matrix and the diagonal matrix of the vertex degrees of G, respectively. The normalized Laplacian matrix of G is defined as L=D(G)-1/2L(G)D(G)-1/2, where D(G)-1/2 is the matrix which is obtained by taking (-1/2) power of each entry of D(G). The Laplacian eigenvalues and the normalized Laplacian eigenvalues of G are the eigenvalues of L(G) and L, respectively. Let μ1≥μ2≥⋯≥μn be the Laplacian eigenvalues and λ1≥λ2≥⋯≥λn the normalized Laplacian eigenvalues of G. Note that μn=0, λn=0, and the multiplicities of these zero eigenvalues are equal to the number of connected components of G; see [6, 7]. For more details on Laplacian and normalized Laplacian eigenvalues, see [6, 8–10].The number of spanning trees,t(G), of the graph G is equal to the total number of distinct spanning subgraphs of G that are trees. This quantity is also known as the complexity of G and given by the following formula in terms of the Laplacian eigenvalues [5]:
(1)t(G)=1n∏i=1n-1‍μi.It is well known that the number of spanning trees ofG is also expressed by the normalized Laplacian eigenvalues as [5, 6]
(2)t(G)=(∏i=1n‍di2m)∏i=1n-1‍λi.Now, we give some known upper bounds ont(G):(1)
Grimmett [11]:
(3)t(G)≤1n(2mn-1)n-1,(2)
Grone and Merris [12]:
(4)t(G)≤(nn-1)n-1(∏i=1n‍di2m),(3)
Nosal [13]: for r-regular graphs,
(5)t(G)≤nn-2(rn-1)n-1,(4)
Cvetković et al. (see [5, page 222]):
(6)t(G)≤nn-2(1-2n)m¯,
where m¯ is the number of edges of G¯,(5)
Das [14]:
(7)t(G)≤(2m-Δ1-1n-2)n-2,(6)
Zhang [15]:
(8)t(G)≤(1+(n-2)a)(1-a)n-21n(2mn-1)n-1,
where a=((n(n-1)-2m)/2mn(n-2))1/2,(7)
Feng et al. [16]:
(9)t(G)≤(Δ1+1n)(2m-Δ1-1n-2)n-2,(10)t(G)≤(M1+2m-(Δ1+1)2n-2)(n-2)/2,(8)
Li et al. [17]:
(11)t(G)≤δ(2m-Δ1-1-δn-3)n-3,(9)
Bozkurt [18]:
(12)t(G)≤(1+(n-2)b)(1-b)n-2(nn-1)n-1(∏i=1n‍di2m),
where b=((n-1-Δ1)/n(n-2)Δ1)1/2,(10)
Das et al. [19]:
(13)t(G)≤12mΔ1δ(2m-Δ1-δn-2)n-2(nn-1)n-1,t(G)<14n(n-3)n-3(Δ1+Δ2+1)2(2m-Δ1-Δ2-1)n-3,t(G)≤1n[4m2-(M1+2m)(n-1)(n-2)](n-1)/2.In [11] Grimmet points out that (3) generalizes (5). Grone and Merris [12] observed that, by the application of arithmetic-geometric mean inequality, (4) leads to (3). Das [14] stated that (7) is sharp for Sn or Kn, but (3), (4), (5), and (6) are sharp for only Kn. In [17] Li et al. indicated that (11) is sharp for Sn, Kn, G≅K1∨(K1∪Kn-2) or Kn-e, but (3) is sharp for only Kn and (7) and (9) are sharp for Sn or Kn. However, Das et al. [19] proved that (11) is not true for Kn. In [15, 16, 18] the authors showed that (8) is better than (3), (9) is better than (7) and (10), and (12) is better than (4). For more bounds and the relations between the number of spanning trees and the structural parameters of graphs such as connectivity, chromatic number, independence number, and clique number, see [17, 19].We organize this paper in the following way. In Section2, we give some previously known results which will be needed later. In Section 3, we obtain some bounds for the number of spanning trees of connected graphs in terms of the number of vertices (n), the number of edges (m), maximum vertex degree (Δ1), minimum vertex degree (δ), first Zagreb index (M1), and Randić index (R-1). We also showed that some of our results on connected bipartite graphs improve the bounds (9) and (10) for these graphs.


## 2. Lemmas

In this section, we give some useful lemmas which will be used later. Firstly, we introduce an auxiliary quantity for a graphG as
(14)α=12[Δ1+δ+(Δ1-δ)2+4Δ1],
where Δ1 and δ are the maximum and the minimum vertex degree of G, respectively.The result in the following lemma is also known as Kober’s inequality.Lemma 1 (see [20]).
Letx1,x2,…,xN be nonnegative numbers and let
(15)β=1N∑i=1N‍xi,γ=(∏i=1N‍xi)1/N
be their arithmetic and geometric means, respectively. Then
(16)1N(N-1)∑i<j‍(xi-xj)2≤β-γ≤1N∑i<j‍(xi-xj)2.
Moreover, equality in (16) holds if and only if x1=x2=⋯=xN.Lemma 2 (see [21]).
LetG be a graph with n vertices and normalized Laplacian matrix L without isolated vertices. Then
(17)∑i=1n‍λi=tr⁡(L)=n,∑i=1n‍λi2=tr⁡(L2)=n+2∑vi~vj‍1didj.Lemma 3 (see [8]).
LetG be a graph with n vertices and without isolated vertices. Then λ1=λ2=⋯=λn-1 if and only if G is a complete graph Kn.Lemma 4 (see [8]).
LetG be a connected graph with n>2 vertices. Then λ2=λ3=⋯=λn-1 if and only if G≅Kn or G≅Kp,q.Note that, the Laplacian eigenvalues of a bipartite graphG coincide with its signless Laplacian eigenvalues, that is, eigenvalues of the signless Laplacian matrix D(G)+A(G) [9, 10, 22]. Thus, one can arrive at the following result.Lemma 5 (see [23, 24]).
LetG be a connected bipartite graph with n≥3 vertices and let Δ1 be the maximum vertex degree of G. Then
(18)μ1≥α≥Δ1+1
with either equalities if and only if G is a star graph Sn.Lemma 6 (see [9]).
LetG be a graph with n vertices. Then μ1≤n, with equality if and only if G¯ is disconnected.Lemma 7 (see [14]).
LetG be a connected graph with n≥3 vertices. Then μ2=μ3=⋯=μn-1 if and only if G≅Kn or G≅Sn or G≅KΔ1,Δ1.


## 3. Main Results

Recently, Das et al. [19] established upper and lower bounds on t(G) applying Kober’s inequality to Laplacian eigenvalues of a connected graph G. We now consider Kober’s inequality for the normalized Laplacian eigenvalues of G in order to present some bounds on t(G).Theorem 8.
LetG be a connected graph with n vertices, m edges, and Randić index R-1. Then
(19)t(G)≤(∏i=1n‍di2m)×[1(n-1)(n-2)(n2-(n+2R-1))](n-1)/2,(20)t(G)≥(∏i=1n‍di2m)×[1(n-1)(n2-(n-2)(n+2R-1))](n-1)/2.
Moreover, equalities in (19) and (20) hold if and only if G≅Kn.Proof.
TakingN=n-1, xi=λi2, and i=1,2,…,n-1 in Lemma 1, we get
(21)∑i<j‍(λi-λj)2(n-1)(n-2)≤∑i=1n-1λi2n-1-(∏i=1n-1‍λi)2/(n-1)≤∑i<j‍(λi-λj)2n-1.
By the proof of Theorem 7 in [19] and Lemma 2, we have
(22)∑i<j‍(λi-λj)2=(n-1)∑i=1n-1‍λi2-(∑i=1n-1‍λi)2=(n-1)(n+2∑vi~vj‍1didj)-n2=(n-1)(n+2R-1)-n2.
Then, combining (21) with this and (2), we get
(23)(n-1)(n+2R-1)-n2(n-1)(n-2)≤n+2R-1n-1-(2mt(G)∏i=1n‍di)2/(n-1)≤(n-1)(n+2R-1)-n2n-1.
This implies that(24)(2mt(G)∏i=1n‍di)2/(n-1)≤1(n-1)(n-2)(n2-(n+2R-1)),(2mt(G)∏i=1n‍di)2/(n-1)≥n2n-1-(n-2n-1)(n+2R-1).
Hence we obtain the first part of the theorem. Now we suppose that the equalities in (19) and (20) hold. Then, by Lemma 1, we have λ1=λ2=⋯=λn-1. Therefore, from Lemma 3, we get that G≅Kn.
Conversely, we can easily see that the equalities in (19) and (20) hold for the complete graph Kn.We now consider the above theorem for connected bipartite graphs.Theorem 9.
LetG be a connected bipartite graph with n>2 vertices, m edges, and Randić index R-1. Then
(25)t(G)≤(∏i=1n‍dim)×[1(n-2)(n-3)((n-2)2-(n+2R-1-4))](n-2)/2,t(G)≥(∏i=1n‍dim)×[(n-2)-(n-3n-2)(n+2R-1-4)](n-2)/2.
Moreover, equalities in (25) hold if and only if G≅Kp,q.Proof.
TakingN=n-2, xi=λi2, and i=2,…,n-1 in Lemma 1, we have
(26)∑2≤i<j≤n-1‍(λi-λj)2(n-2)(n-3)≤∑i=2n-1λi2n-2-(∏i=2n-1‍λi)2/(n-2)≤∑2≤i<j≤n-1‍(λi-λj)2n-2.
SinceG is bipartite, we also have λ1=2 [6]. Then, by Lemma 2, we get
(27)∑2≤i<j≤n-1‍(λi-λj)2=(n-2)∑i=2n-1‍λi2-(∑i=2n-1‍λi)2=(n-2)(n+2∑vi~vj‍1didj-4)-(n-2)2=(n-2)(n+2R-1-4)-(n-2)2.
Therefore, combining (26) with this and (2), we arrive at
(28)(n-2)(n+2R-1-4)-(n-2)2(n-2)(n-3)≤n+2R-1-4n-2-(mt(G)∏i=1n‍di)2/(n-2)≤(n-2)(n+2R-1-4)-(n-2)2n-2.
This implies that(29)(mt(G)∏i=1n‍di)2/(n-2)≤1(n-2)(n-3)((n-2)2-(n+2R-1-4)),(mt(G)∏i=1n‍di)2/(n-2)≥(n-2)-(n-3n-2)(n+2R-1-4).
Hence we get the inequalities (25). Now we suppose that the equalities in (25) hold. Then, by Lemma 1, we have λ2=λ3=⋯=λn-1. Therefore, by Lemma 4, we conclude that G≅Kp,q.
Conversely, we can easily see that the equalities in (25) hold for the complete bipartite graph Kp,q.We now present the improvement of the results obtained in [16] for bipartite graphs.Theorem 10.
LetG be a connected bipartite graph with n≥3 vertices and m edges and let α be given by (14). Then
(30)t(G)≤(αn)(2m-αn-2)n-2
with equality if and only if G≅Sn.Proof.
From (1) and Lemmas 5–7, one can prove (30) in a similar way to the proof of Theorem 1.1 in [16].Remark 11.
From Lemma5, we have μ1≥α≥Δ1+1. Then by the proof of Theorem 1.1 in [16], one may conclude that (30) improves (9) for bipartite graphs.Theorem 12.
LetG be a connected bipartite graph with n≥3 vertices, m edges, and first Zagreb index M1 and let α be given by (14). Then
(31)t(G)≤(M1+2m-α2n-2)(n-2)/2
with equality if and only if G≅Sn.Proof.
From (1) and Lemmas 5–7, the proof of (31) can be easily given in a similar way to the proof of Theorem 1.2 in [16].Remark 13.
From Lemma5, we have μ1≥α≥Δ1+1. Then by the proof of Theorem 1.2 in [16], one may conclude that (31) improves (10) for bipartite graphs.Remark 14.
By using the similar manner in [16], one can easily show that (30) is better than (31). Moreover, if we can obtain a new bound μ1≥α′≥α≥Δ1+1, then we can improve the bounds (30) and (31).Example 15.
LetG be a graph with vertex set V(G)={v1,v2,v3,v4,v5} and edge set
(32)E(G)={e1=v1v2,e2=v1v3,e3=v2v4,e4=v2v5,e5=v4v5}.
For this graph,t(G) is equal to 3. At rounded three decimal places, the bounds (8), (9), (11), (12), (13), and (19) give t(G)≤5.659, t(G)≤6.400, t(G)≤6.250, t(G)≤5.224, t(G)≤5.859, t(G)≤7.200, t(G)≤6.422, and t(G)≤5.104, respectively. This shows that the bound (19) is the best among the mentioned upper bounds for t(G). But in general sense, they are not comparable.



---

*Source: 294038-2014-02-10.xml*