nach oben

Journal of Inequalities and Applications

Erschienen in:

Open Access 01.12.2013 | Research

The number of spanning trees of a graph

verfasst von: Kinkar C Das, Ahmet S Cevik, Ismail N Cangul

Erschienen in: Journal of Inequalities and Applications | Ausgabe 1/2013

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

Let G be a simple connected graph of order n, m edges, maximum degree

Δ_{1}

and minimum degree δ. Li et al. (Appl. Math. Lett. 23:286-290, 2010) gave an upper bound on number of spanning trees of a graph in terms of n, m,

Δ_{1}

and δ:

t (G) \leq δ {(\frac{2 m - Δ_{1} - δ - 1}{n - 3})}^{n - 3} .

The equality holds if and only if

G ≅ K_{1, n - 1}

G ≅ K_{n}

G ≅ K_{1} \lor (K_{1} \cup K_{n - 2})

G ≅ K_{n} - e

, where e is any edge of

K_{n}

. Unfortunately, this upper bound is erroneous. In particular, we show that this upper bound is not true for complete graph

K_{n}

In this paper we obtain some upper bounds on the number of spanning trees of graph G in terms of its structural parameters such as the number of vertices (n), the number of edges (m), maximum degree (

Δ_{1}

), second maximum degree (

Δ_{2}

), minimum degree (δ), independence number (α), clique number (ω). Moreover, we give the Nordhaus-Gaddum-type result for number of spanning trees.

MSC:05C50, 15A18.

Authors’ original file for figure 1

Electronic supplementary material

The online version of this article (doi:10.1186/1029-242X-2013-395) contains supplementary material, which is available to authorized users.

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

All authors completed the paper together. All authors read and approved the final manuscript.

Dedication

Dedicated to Professor Hari M Srivastava

1 Introduction

Let

G = (V, E)

be a simple connected graph with a vertex set

V (G) = {v_{1}, v_{2}, \dots, v_{n}}

and an edge set

E (G)

. Its order is

| V (G) |

, denoted by n, and its size is

| E (G) |

, denoted by m. For

v_{i} \in V (G)

, the degree (= number of the first neighbors) of the vertex

v_{i}

is denoted by

d_{i}

. The maximum vertex degree is denoted by

Δ_{1}

, the second maximum by

Δ_{2}

, and the minimum vertex degree δ. The number of spanning trees of G, denoted by

t (G)

, is the total number of distinct spanning subgraphs of G that are trees.

The Laplacian matrix of a graph G is

L (G) = D (G) - A (G)

, where

D (G)

is the diagonal matrix of vertex degrees, and

A (G)

is the

(0, 1)

-adjacency matrix of graph G. Let

λ_{1} \geq λ_{2} \geq \dots \geq λ_{n} = 0

denote the eigenvalues of

L (G)

. They are usually called the Laplacian eigenvalues of G. When more than one graph is under discussion, we may write

λ_{i} (G)

instead of

λ_{i}

. For a connected graph of order n, it has been proven [1] that

t (G) = \frac{1}{n} \prod_{i = 1}^{n - 1} λ_{i} .

(1)

The normalized Laplacian matrix of G is denoted by ℒ and defined to be

L = D {(G)}^{- \frac{1}{2}} L (G) D {(G)}^{- \frac{1}{2}},

where

L (G)

is the Laplacian matrix and

D (G)

is the diagonal matrix of vertex degrees of graph G. The eigenvalues of ℒ are non-negative, we label them so that

0 = ρ_{n} \leq ρ_{n - 1} \leq \dots \leq ρ_{2} \leq ρ_{1}

. For a connected graph of order n, it has been proven [2] that

t (G) = \frac{1}{2 m} \prod_{i = 1}^{n} d_{i} \prod_{i = 1}^{n - 1} ρ_{i} .

(2)

We now give some known popular upper bounds on

t (G)

Grimmett [3].

t (G) \leq \frac{1}{n} {(\frac{2 m}{n - 1})}^{n - 1} .

(3)

Grone and Merris [4].

t (G) \leq {(\frac{n}{n - 1})}^{n - 1} (\frac{\prod_{i = 1}^{n} d_{i}}{2 m}) .

(4)

Nosal [5].

t (G) \leq n^{n - 2} {(\frac{r}{n - 1})}^{n - 1} .

(5)

Kelmans [[6], p.222].

t (G) \leq n^{n - 2} {(1 - \frac{2}{n})}^{m} .

(6)

Das [7].

t (G) \leq {(\frac{2 m - Δ_{1} - 1}{n - 2})}^{n - 2} .

(7)

The third bound only applies to regular graphs of degree r. The first three bounds are sharp for complete graphs only. The fifth bound is sharp for star or complete graph. Moreover, the bound in (5) was also obtained by McKay [8]. Chung et al. [9] studied the number of spanning trees for regular graphs. As usual,

K_{n}

K_{p, q}

(

p + q = n

) and

K_{1, n - 1}

denote, respectively, the complete graph, the complete bipartite graph and the star on n vertices.

The paper is organized as follows. In Section 2, we give a list of some previously known results. In Section 3, we obtain some upper bounds on the number of spanning trees. In Section 4, we obtain Nordhaus-Gaddum-type result for the number of spanning trees of graph G.

2 Lemmas

In this section, we shall list some previously known results that will be needed in the next two sections. The next lemma is firstly obtained in Theorem 2.6 [7].

Lemma 1 ([7])

Let G be a connected graph of order n. Then

λ_{1} = λ_{2} = \dots = λ_{n - 1}

if and only if

G ≅ K_{n}

We now give a lower bound on the sum of the largest two Laplacian eigenvalues of graph G.

Lemma 2 ([10])

Let G be a connected graph of order

n > 2

. Then

λ_{1} + λ_{2} \geq Δ_{1} + Δ_{2} + 1

Lemma 3 ([10])

Let G be a graph on n vertices, which has at least one edge. Then

λ_{1} \geq Δ_{1} + 1 .

(8)

Moreover, if G is connected, then the equality in (8) holds if and only if

Δ_{1} = n - 1

A well-known theorem in an algebraic graph theory is the interlacing of the Laplacian spectrum in Theorem 13.6.2 [1].

Lemma 4 ([1])

Let G be a graph of n vertices, and let H be a subgraph of G obtained by deleting an edge in G. Then

λ_{1} (G) \geq λ_{1} (H) \geq λ_{2} (G) \geq λ_{2} (H) \geq \dots \geq λ_{n - 1} (G) \geq λ_{n - 1} (H) \geq λ_{n} (G) \geq λ_{n} (H) = 0,

where

λ_{i} (G)

is the ith largest Laplacian eigenvalue of G, and

λ_{i} (H)

is the ith largest Laplacian eigenvalue of H.

Lemma 5 ([11])

Let G be a simple graph with the Laplacian spectrum

{0 = λ_{n}, λ_{n - 1}, \dots, λ_{2}, λ_{1}} .

Then the Laplacian spectrum of

\bar{G}

{0, n - λ_{1}, n - λ_{2}, \dots, n - λ_{n - 2}, n - λ_{n - 1}}

, where

\bar{G}

is the complement graph of G.

We also have the following result, which is obtained in [12].

Lemma 6 ([12])

Let G be a graph of order n without isolated vertices. Then

ρ_{1} = ρ_{2} = ρ_{3} = \dots = ρ_{n - 1}

if and only if

G ≅ K_{n}

The result is the following lemma, known as Kober’s inequality.

Lemma 7 ([13])

Let

x_{1}, x_{2}, \dots, x_{n}

be non negative numbers, and also let

α = \frac{1}{n} \sum_{i = 1}^{n} x_{i} and γ = {(\prod_{i = 1}^{n} x_{i})}^{1 / n}

be their arithmetic and geometric means. Then

\frac{1}{n (n - 1)} \sum_{i < j} {(\sqrt{x_{i}} - \sqrt{x_{j}})}^{2} \leq α - γ \leq \frac{1}{n} \sum_{i < j} {(\sqrt{x_{i}} - \sqrt{x_{j}})}^{2} .

Moreover, the equality holds if and only if

x_{1} = x_{2} = \dots = x_{n}

3 Bounds on the number of spanning trees

In [14], an upper bound for

t (G)

is obtained as follows.

Theorem 1 ([14])

Let G be a connected graph of order n (

n > 3

) with m edges, maximum degree

Δ_{1}

and minimum degree δ. Then

t (G) \leq δ {(\frac{2 m - Δ_{1} - δ - 1}{n - 3})}^{n - 3} .

The equality holds if and only if

G ≅ K_{1, n - 1}

G ≅ K_{n}

G ≅ K_{1} \lor (K_{1} \cup K_{n - 2})

G ≅ K_{n} - e

, where e is any edge of

K_{n}

Here we show that Theorem 1 is not true for complete graph

K_{n}

. For this, we need the following lemma.

Lemma 8 For positive integer

a > 0

{(1 + \frac{1}{a (a + 3)})}^{a} < 1 + \frac{1}{a + 2} .

(9)

Proof We have

\begin{aligned} {(1 + \frac{1}{a (a + 3)})}^{a} \\ = 1 + \frac{1}{a + 3} + (\begin{matrix} a \\ 2 \end{matrix}) \frac{1}{a^{2} {(a + 3)}^{2}} + (\begin{matrix} a \\ 3 \end{matrix}) \frac{1}{a^{3} {(a + 3)}^{3}} + \dots + (\begin{matrix} a \\ a \end{matrix}) \frac{1}{a^{a} {(a + 3)}^{a}} . \end{aligned}

(10)

In fact, this satisfies

\begin{array}{rcl} < & 1 + \frac{1}{a + 3} + \frac{1}{2! {(a + 3)}^{2}} + \frac{1}{3! {(a + 3)}^{3}} + \frac{1}{4! {(a + 3)}^{4}} + \dots + \frac{1}{a! {(a + 3)}^{a}} \\ < & 1 + \frac{1}{a + 3} + \frac{1}{a + 3} (\frac{1}{2 (a + 3)} + \frac{1}{2^{2} {(a + 3)}^{2}} + \frac{1}{2^{3} {(a + 3)}^{3}} + \dots + \frac{1}{2^{a - 1} {(a + 3)}^{a - 1}}) \\ = & 1 + \frac{1}{a + 3} + \frac{1}{2 {(a + 3)}^{2}} \frac{1 - \frac{1}{2^{a - 1} {(a + 3)}^{a - 1}}}{1 - \frac{1}{2 (a + 3)}} . \end{array}

Now, we have to show that

\frac{1}{a + 3} + \frac{1}{2 {(a + 3)}^{2}} \cdot \frac{1 - \frac{1}{2^{a - 1} {(a + 3)}^{a - 1}}}{1 - \frac{1}{2 (a + 3)}} < \frac{1}{a + 2},

that is,

2^{a - 1} {(a + 3)}^{a} > - (a + 2),

which is always true, as a is a positive integer. This completes the proof. □

Upper bound of

t (G)

in Theorem 1 is not true for

K_{n}

(

n > 3

). It is well known that

t (K_{n}) = n^{n - 2}

. Here, we have to show that

(n - 1) {(\frac{n (n - 3) + 1}{n - 3})}^{n - 3} < t (K_{n}) = n^{n - 2} .

(11)

Now, putting

a = n - 3

in (9), we get

{(1 + \frac{1}{n (n - 3)})}^{n - 3} < 1 + \frac{1}{n - 1},

which gives result (11).

Hence the correct statement is as follows.

Theorem 2 ([14])

Let G (

\neq K_{n}

) be a connected graph of order n (

n > 3

) with m edges, maximum degree

Δ_{1}

and minimum degree δ. Then

t (G) \leq δ {(\frac{2 m - Δ_{1} - δ - 1}{n - 3})}^{n - 3}

(12)

with the equality holding in (12) if and only if

G ≅ K_{1, n - 1}

G ≅ K_{1} \lor (K_{1} \cup K_{n - 2})

G ≅ K_{n} - e

, where e is any edge of

K_{n}

Proof Since

G ≇ K_{n}

, we have

μ_{n - 1} \leq δ

, where δ is the minimum degree in G. The remaining part of the proof is same as in Theorem 3.1 [14]. □

We now give an upper bound on the number of spanning trees

t (G)

in terms of n, m,

Δ_{1}

and δ.

Theorem 3 Let G be a connected graph on n vertices with m edges, maximum degree

Δ_{1}

and minimum degree δ. Then

t (G) \leq \frac{1}{2 m} Δ_{1} δ {(\frac{2 m - Δ_{1} - δ}{n - 2})}^{n - 2} {(\frac{n}{n - 1})}^{n - 1}

(13)

with the equality holding in (13) if and only if

G ≅ K_{n}

Proof By the arithmetic-geometric mean inequality, we have

\prod_{i = 2}^{n - 1} d_{i} \leq {(\frac{2 m - Δ_{1} - δ}{n - 2})}^{n - 2} as 2 m = \sum_{i = 1}^{n} d_{i}

and

\prod_{i = 2}^{n - 1} ρ_{i} \leq {(\frac{n - ρ_{1}}{n - 2})}^{n - 2} as n = \sum_{i = 1}^{n - 1} ρ_{i} .

Using the above results in (2), we get

t (G) \leq \frac{1}{2 m} Δ_{1} δ {(\frac{2 m - Δ_{1} - δ}{n - 2})}^{n - 2} ρ_{1} {(\frac{n - ρ_{1}}{n - 2})}^{n - 2} .

(14)

Let us consider the function

f (x) = x {(n - x)}^{n - 2}, 0 \leq x \leq 2 .

Then we have

f^{'} (x) = {(n - x)}^{n - 3} [n - (n - 1) x], 0 \leq x \leq 2 .

Thus,

f (x)

is an increasing function on

[0, \frac{n}{n - 1}]

and a decreasing function on

[\frac{n}{n - 1}, 2]

. Hence the maximum value of

f (x)

{(\frac{n}{n - 1})}^{n - 1} {(n - 2)}^{n - 2} .

Using (14), we get the required result in (13). Thus, the first part of the proof is done.

Now, we suppose that the equality holds in (13). Then all inequalities in the argument above must be equalities. Thus, we have

ρ_{1} = \frac{n}{n - 1}

. From the equality in (14), we get

d_{2} = d_{3} = \dots = d_{n - 1}

and

ρ_{2} = ρ_{3} = \dots = ρ_{n - 1} = \frac{n}{n - 1}

. Therefore,

ρ_{1} = ρ_{2} = ρ_{3} = \dots = ρ_{n - 1}

. By Lemma 6,

G ≅ K_{n}

Conversely, one can easily see that the equality holds in (13) for complete graph

K_{n}

. □

Here, we give an upper bound on the number of spanning trees

t (G)

in terms of n, m,

Δ_{1}

and

Δ_{2}

Theorem 4 Let G be a connected graph on n vertices, m edges with maximum degree

Δ_{1}

and second maximum degree

Δ_{2}

. Then

t (G) < \frac{1}{4 n {(n - 3)}^{n - 3}} {(Δ_{1} + Δ_{2} + 1)}^{2} {(2 m - Δ_{1} - Δ_{2} - 1)}^{n - 3} .

(15)

Proof By the arithmetic-geometric mean inequality, we have

λ_{1} λ_{2} \leq {(\frac{λ_{1} + λ_{2}}{2})}^{2}

and

\prod_{i = 3}^{n - 1} λ_{i} \leq {(\frac{2 m - λ_{1} - λ_{2}}{n - 3})}^{n - 3} as 2 m = \sum_{i = 1}^{n - 1} λ_{i} .

Using the above results in (1), we get

t (G) \leq \frac{1}{n} {(\frac{λ_{1} + λ_{2}}{2})}^{2} \cdot {(\frac{2 m - λ_{1} - λ_{2}}{n - 3})}^{n - 3} .

(16)

Let us consider a function

f (x) = x^{2} {(2 m - x)}^{n - 3} .

We, thus, have

f^{'} (x) = x {(2 m - x)}^{n - 4} (4 m - (n - 1) x) .

For

x = λ_{1} + λ_{2}

, we have

f^{'} (x) \leq 0

(n - 1) x \geq 4 m = 2 \sum_{i = 1}^{n - 1} λ_{i}

. Thus,

f (x)

is a decreasing function and

λ_{1} + λ_{2} \geq Δ_{1} + Δ_{2} + 1

, by Lemma 2, and hence

t (G) \leq \frac{1}{4 n {(n - 3)}^{n - 3}} {(Δ_{1} + Δ_{2} + 1)}^{2} {(2 m - Δ_{1} - Δ_{2} - 1)}^{n - 3} .

(17)

By contradiction, we will show that the inequality in (17) is strict. Suppose that the equality holds in (17). Then all the inequalities in the argument above must be equalities. Thus, we have

λ_{1} + λ_{2} = Δ_{1} + Δ_{2} + 1

. From equality in (16), we get

λ_{1} = λ_{2}

and

λ_{3} = λ_{4} = \dots = λ_{n - 1}

. By Lemma 3, we have

Δ_{1} + Δ_{2} + 1 = λ_{1} + λ_{2} = 2 λ_{1} \geq 2 (Δ_{1} + 1) \geq Δ_{1} + Δ_{2} + 2

, a contradiction.

This completes the proof. □

For

1 \leq α \leq n - 1

, let

CI (n, α)

be a split graph on n vertices consisting of a

{\bar{K}}_{α}

(complement of the complete graph on α vertices) and a

K_{n - α}

(complete graph on the remaining

n - α

vertices), in which each vertex of the

{\bar{K}}_{α}

is adjacent to each vertex of the

K_{n - α}

. Therefore,

CI (n, α) = K_{n - α} \lor {\bar{K}}_{α} .

We now give another upper bound on the number of spanning trees in terms of n and α.

Theorem 5 Let G be a simple connected graph of order n with an independence number α. Then

t (G) \leq n^{n - α - 1} {(n - α)}^{α - 1}

(18)

with the equality holding in (18) if and only if

G ≅ CI (n, α)

Proof By Lemma 4, we have

λ_{i} (G + e) \geq λ_{i} (G), i = 1, 2, \dots, n,

where e is an edge. So if we add one by one edges in G such that independence number α is fixed of the resultant graph, then finally, we obtain a split graph

CI (n, α)

. One can easily see that

t (G) \leq t (CI (n, α)) = n^{n - α - 1} {(n - α)}^{α - 1}

as Laplacian spectrum of

\bar{CI} (n, α)

https://static-content.springer.com/image/art%3A10.1186%2F1029-242X-2013-395/MediaObjects/13660_2012_Article_845_IEq69_HTML.gif

, that is, Laplacian spectrum of

CI (n, α)

https://static-content.springer.com/image/art%3A10.1186%2F1029-242X-2013-395/MediaObjects/13660_2012_Article_845_IEq70_HTML.gif

, by Lemma 5.

Since G is connected, one can easily see that

t (G + e) > t (G) .

This completes the proof of this theorem. □

We now give another upper bound on

t (G)

in terms of n, m and ω.

Theorem 6 Let G be a connected graph of order n, m edges and clique number ω. Then

t (G) \leq \frac{ω^{ω - 2} {(2 m - ω (ω - 2))}^{n - ω + 1}}{n {(n - ω + 1)}^{n - ω + 1}}

(19)

with the equality holding if and only if

G ≅ K_{n}

Proof By the arithmetic-geometric mean inequality, we have

\prod_{i = 1}^{ω - 2} λ_{i} \leq {(\frac{\sum_{i = 1}^{ω - 2} λ_{i}}{ω - 2})}^{ω - 2} and \prod_{i = ω - 1}^{n - 1} λ_{i} \leq {(\frac{\sum_{i = ω - 1}^{n - 1} λ_{i}}{n - ω + 1})}^{n - ω + 1} .

Since ω is the clique number of G, by using (1), we get

\begin{array}{rcl} t (G) & = & \frac{1}{n} \prod_{i = 1}^{ω - 2} λ_{i} \prod_{i = ω - 1}^{n - 1} λ_{i} \leq \frac{1}{n} {(\frac{\sum_{i = 1}^{ω - 2} λ_{i}}{ω - 2})}^{ω - 2} \times {(\frac{\sum_{i = ω - 1}^{n - 1} λ_{i}}{n - ω + 1})}^{n - ω + 1} \\ = & \frac{1}{n {(ω - 2)}^{ω - 2} {(n - ω + 1)}^{n - ω + 1}} A^{ω - 2} {(2 m - A)}^{n - ω + 1}, \\ where A = \sum_{i = 1}^{ω - 2} λ_{i} . \end{array}

(20)

Let us consider a function

f (x) = x^{ω - 2} {(2 m - x)}^{n - ω + 1} .

Then, we have

f^{'} (x) = x^{ω - 3} {(2 m - x)}^{n - ω} (2 m (ω - 2) - (n - 1) x) .

Since

λ_{1} \geq λ_{2} \geq \dots \geq λ_{n - 1}

, we have

(n - ω + 1) \sum_{i = 1}^{ω - 2} λ_{i} \geq (n - ω + 1) (ω - 2) λ_{ω - 2} \geq (ω - 2) \sum_{i = ω - 1}^{n - 1} λ_{i},

that is,

(n - 1) A = (n - 1) \sum_{i = 1}^{ω - 2} λ_{i} \geq (ω - 2) \sum_{i = 1}^{n - 1} λ_{i} = 2 m (ω - 2) .

By using this inequality above, we conclude that

f (x)

is a decreasing function, as

f^{'} (x) \leq 0

. Since ω is a clique number of G, we must have

λ_{i} \geq ω

i = 1, 2, \dots, ω - 1

, and hence

A = \sum_{i = 1}^{ω - 2} λ_{i} \geq ω (ω - 2)

. Thus, we have

f (x) \leq ω^{ω - 2} {(ω - 2)}^{ω - 2} {(2 m - ω (ω - 2))}^{n - ω + 1} .

Using the above result with (20), we get the required result (19). The first part of the proof is done.

Now, we suppose that the equality holds in (19). Then all the inequalities in the argument above must be equalities. Thus, we have

λ_{1} = λ_{2} = \dots = λ_{ω - 2} = ω

and

λ_{ω - 1} = λ_{ω} = \dots = λ_{n - 1} = ω

. Hence

λ_{i} = ω

i = 1, 2, \dots, n - 1

. By Lemma 1,

G ≅ K_{n}

Conversely, one can easily see that the equality holds in (19) for complete graph

K_{n}

. □

The first Zagreb index

M_{1} (G)

is defined as follows:

M_{1} (G) = \sum_{i = 1}^{n} d_{i}^{2} .

The first Zagreb index

M_{1} (G)

was introduced in [15] and elaborated in [16]. The main properties of

M_{1} (G)

were summarized in [17]. Some recent results on the first Zagreb index are reported in [18‐21]. Now, we are ready to give some lower and upper bounds on the number of spanning trees.

Theorem 7 Let G be a connected graph of order n with m edges and first Zagreb index

M_{1} (G)

. Then

t (G) \geq \frac{1}{n} {[\frac{4 m^{2} - (n - 2) (M_{1} (G) + 2 m)}{n - 1}]}^{\frac{n - 1}{2}}

(21)

with the equality holding in (21) if and only if

G ≅ K_{n}

. Moreover,

t (G) \leq \frac{1}{n} {[\frac{4 m^{2} - M_{1} (G) + 2 m}{(n - 1) (n - 2)}]}^{\frac{n - 1}{2}}

(22)

with the equality holding in (22) if and only if

G ≅ K_{n}

Proof We have

\begin{array}{rcl} \sum_{i < j} {(λ_{i} - λ_{j})}^{2} & = & \frac{1}{2} \sum_{i = 1}^{n - 1} \sum_{j = 1}^{n - 1} (λ_{i}^{2} + λ_{j}^{2} - 2 λ_{i} λ_{j}) \\ = & \frac{1}{2} [(n - 1) \sum_{i = 1}^{n - 1} λ_{i}^{2} + (n - 1) \sum_{j = 1}^{n - 1} λ_{j}^{2} - 2 \sum_{i = 1}^{n - 1} λ_{i} \sum_{j = 1}^{n - 1} λ_{j}] \\ = & (n - 1) \sum_{i = 1}^{n - 1} λ_{i}^{2} - {(\sum_{i = 1}^{n - 1} λ_{i})}^{2} = (n - 1) \sum_{i = 1}^{n} d_{i} (d_{i} + 1) - {(\sum_{i = 1}^{n} d_{i})}^{2} \\ as \sum_{i = 1}^{n - 1} λ_{i}^{2} = \sum_{i = 1}^{n} d_{i} (d_{i} + 1) and \sum_{i = 1}^{n - 1} λ_{i} = \sum_{i = 1}^{n} d_{i} \\ = & (n - 1) (M_{1} (G) + 2 m) - 4 m^{2} as \sum_{i = 1}^{n} d_{i} = 2 m . \end{array}

(23)

Since G is connected,

λ_{n - 1} > 0

. Now, by setting

x_{i} = λ_{i}^{2}

i = 1, 2, \dots, n - 1

and by Lemma 7, we obtain

\frac{\sum_{i = 1}^{n - 1} λ_{i}^{2}}{n - 1} - {(\prod_{i = 1}^{n - 1} λ_{i}^{2})}^{1 / n - 1} \leq M_{1} (G) + 2 m - \frac{4 m^{2}}{n - 1}, by (23)

that is, by considering (1),

\frac{\sum_{i = 1}^{n} d_{i} (d_{i} + 1)}{n - 1} - {(n t (G))}^{2 / n - 1} \leq M_{1} (G) + 2 m - \frac{4 m^{2}}{n - 1}

since

\sum_{i = 1}^{n - 1} λ_{i}^{2} = \sum_{i = 1}^{n} d_{i} (d_{i} + 1)

. From this last inequality, we then get

{(n t (G))}^{2 / n - 1} \geq \frac{4 m^{2}}{n - 1} - (\frac{n - 2}{n - 1}) (M_{1} (G) + 2 m), as M_{1} (G) = \sum_{i = 1}^{n} d_{i}^{2},

which gives the required result (21). Similarly, by Lemma 7, we obtain

{(n t (G))}^{2 / n - 1} \leq \frac{1}{(n - 1) (n - 2)} (4 m^{2} - M_{1} (G) + 2 m),

as required in (22). Hence the first part of the proof is completed.

Now, we suppose that the equality holds in (21) or (22). Then all the inequalities in the argument above must be equalities. By Lemma 7, we have

λ_{1} = λ_{2} = λ_{3} = \dots = λ_{n - 1}

. By Lemma 1, we get

G ≅ K_{n}

Conversely, one can easily see that the equalities in (21) and (22) hold for complete graphs

K_{n}

. □

Example 1 For the three graphs

G_{1}

G_{2}

and

G_{3}

in Figure 1,

t (G_{1})

t (G_{2})

and

t (G_{3})

are 3, 8 and 9, respectively. The numerical results related to the bounds (that were mentioned above) are listed in the following. At this point, we should note that these results are presenting as rounded the one decimal place.

\begin{array}{cccccccccccc} t (G) & (3) & (4) & (7) & (12) & (13) & (15) & (18) & (19) & (22) \\ G_{1} & 3 & 7.8 & 3.9 & 4.6 & 4 & 4.5 & 5.5 & 20 & 7.6 & 9.8 \\ G_{2} & 8 & 16.2 & 9.8 & 12.7 & 9 & 10.3 & 12.8 & 20 & 16.2 & 20.7 \\ G_{3} & 9 & 16.2 & 13 & 12.7 & 12.5 & 13 & 20 & 75 & 16.2 & 21.4 \end{array}

4 Nordhaus-Gaddum-type results for the number of spanning trees of a graph

For a graph G , the chromatic number

χ (G)

is the minimum number of colors needed to color the vertices of G in such a way that no two adjacent vertices are assigned the same color. In 1956, Nordhaus and Gaddum [22] gave bounds involving the chromatic number

χ (G)

of a graph G and its complement

\bar{G}

2 \sqrt{n} \leq χ (G) + χ (\bar{G}) \leq n + 1 .

Motivated by the results above, we now obtain analogous conclusions for the number of spanning trees.

Theorem 8 Let G be a connected graph on

n \geq 4

vertices and m edges with a connected complement

\bar{G}

. Then

\begin{aligned} t (G) + t (\bar{G}) \\ \leq \frac{1}{n {(n - 2)}^{n - 2}} \\ \times [(Δ_{1} + 1) {(2 m - Δ_{1} - 1)}^{n - 2} + (n - Δ_{1} - 1) {(n (n - 2) - 2 m + Δ_{1} + 1)}^{n - 2}], \end{aligned}

(24)

where

Δ_{1}

is the maximum degree in G.

Proof By Lemma 5, from (1), we have

\begin{array}{rcl} t (G) + t (\bar{G}) & = & \frac{1}{n} \prod_{i = 1}^{n - 1} λ_{i} + \frac{1}{n} \prod_{i = 1}^{n - 1} (n - λ_{i}) \\ \leq & \frac{1}{n} [λ_{1} {(\frac{2 m - λ_{1}}{n - 2})}^{n - 2} + (n - λ_{1}) {(\frac{n (n - 2) - 2 m + λ_{1}}{n - 2})}^{n - 2}] \\ by the arithmetic-geometric mean inequality \\ = & \frac{1}{n {(n - 2)}^{n - 2}} [λ_{1} {(2 m - λ_{1})}^{n - 2} + (n - λ_{1}) {(n (n - 2) - 2 m + λ_{1})}^{n - 2}] . \end{array}

(25)

Let us consider a function

f (x) = x {(2 m - x)}^{n - 2} + (n - x) {(n (n - 2) - 2 m + x)}^{n - 2} for Δ_{1} + 1 \leq x \leq n .

We have

\begin{array}{rcl} f^{'} (x) & = & {(2 m - x)}^{n - 3} (2 m - (n - 1) x) - {(n (n - 2) - 2 m + x)}^{n - 3} ((n - 1) x - 2 m) \\ = & - ((n - 1) x - 2 m) [{(2 m - x)}^{n - 3} + {(n (n - 2) - 2 m + x)}^{n - 3}] < 0 . \end{array}

Thus,

f (x)

is a decreasing function on

Δ_{1} + 1 \leq x \leq n

. Using the result above in (25), we obtain the required result (24). □

The next result presents another upper bound for

t (G) + t (\bar{G})

. In fact, the proof of it is clear by considering Theorem 7.

Theorem 9 Let G be a graph on n vertices and m edges. Then

\begin{aligned} t (G) + t (\bar{G}) \\ \leq \frac{1}{n {(n - 1)}^{(n - 1) / 2} {(n - 2)}^{(n - 1) / 2}} [{(4 m^{2} - M_{1} (G) + 2 m)}^{(n - 1) / 2} \\ + {(n (n - 1) (n^{2} - 2 n + 2) + 2 m (2 m - 2 {(n - 1)}^{2} - 1) - M_{1} (G))}^{(n - 1) / 2}], \end{aligned}

(26)

where

M_{1} (G)

is the first Zagreb index of graph G. Moreover, the equality in (26) holds if and only if

G ≅ K_{n}

\bar{G} ≅ K_{n}

Acknowledgements

The authors are grateful to the referees for their valuable comments, which lead to an improvement of the original manuscript. This paper was prepared during the first author’s visit in Selcuk and Uludag Universities. Moreover, we are thankful to Mr. SA Mojallal for computing the values in Example 1. The first author is supported by the Faculty research Fund, Sungkyunkwan University, 2012 and the National Research Foundation funded by the Korean government with the grant no. 2013R1A1A2009341. The second and the third authors are both partially supported by the Research Project Offices of Selcuk and Uludag Universities, and TUBITAK (The Scientific and Technological Research Council of Turkey).

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License ( https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

All authors completed the paper together. All authors read and approved the final manuscript.

Vorheriger Artikel On the norms of an r-circulant matrix with the generalized k-Horadam numbers

Nächster Artikel Some properties of the generalized Fibonacci and Lucas sequences related to the extended Hecke groups

Authors’ original submitted files for images

Below are the links to the authors’ original submitted files for images.

Authors’ original file for figure 1

Godsil C, Royle G Graduate Texts in Mathematics 207. In Algebraic Graph Theory. Springer, Berlin; 2001.CrossRef

Chung FRK: Spectral Graph Theory. Am. Math. Soc., Providence; 1997.

Grimmett GR: An upper bound for the number of spanning trees of a graph. Discrete Math. 1976, 16: 323–324. 10.1016/S0012-365X(76)80005-2MathSciNetCrossRef

Grone R, Merris R: A bound for the complexity of a simple graph. Discrete Math. 1988, 69: 97–99. 10.1016/0012-365X(88)90182-3MathSciNetCrossRef

Nosal, E: Eigenvalues of Graphs. Master thesis, University of Calgary (1970)

Cvetković DM, Doob M, Sachs H Pure and Applied Mathematics 87. In Spectra of Graphs. Academic press, San Diego; 1980.

Das KC: A sharp upper bound for the number of spanning trees of a graph. Graphs Comb. 2007, 23: 625–632. 10.1007/s00373-007-0758-4CrossRef

McKay BD: Spanning trees in regular graphs. Eur. J. Comb. 1983, 4: 149–160. 10.1016/S0195-6698(83)80045-6MathSciNetCrossRef

Chung F, Yau S-T: Coverings, heat kernels and spanning trees. Electron. J. Comb. 1999., 6: Article ID R12

10.

Grone R, Merris R: The Laplacian spectrum of a graph II. SIAM J. Discrete Math. 1994, 7(2):221–229. 10.1137/S0895480191222653MathSciNetCrossRef

11.

Merris R: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 1994, 197(198):143–176.MathSciNetCrossRef

12.

Das KC, Maden AD, Cevik AS: Sharp upper bounds on the spectral radius of the Signless Laplacian matrix of a graph. Appl. Math. Comput. 2013, 219(10):5025–5032. 10.1016/j.amc.2012.11.039MathSciNetCrossRef

13.

Kober H: On the arithmetic and geometric means and on Holder’s inequality. Proc. Am. Math. Soc. 1958, 59: 452–459.MathSciNet

14.

Li J, Shiu WC, Chang A: The number of spanning trees of a graph. Appl. Math. Lett. 2010, 23: 286–290. 10.1016/j.aml.2009.10.006MathSciNetCrossRef

15.

Gutman I, Trinajstić N: Graph theory and molecular orbitals. Total π -electron energy of alternant hydrocarbons. Chem. Phys. Lett. 1972, 17: 535–538. 10.1016/0009-2614(72)85099-1CrossRef

16.

Gutman I, Ruščić B, Trinajstić N, Wilcox CF: Graph theory and molecular orbitals. XII. Acyclic polyenes. J. Chem. Phys. 1975, 62: 3399–3405. 10.1063/1.430994CrossRef

17.

Nikolić S, Kovačević G, Milićević A, Trinajstić N: The Zagreb indices 30 years after. Croat. Chem. Acta 2003, 76: 113–124.

18.

Das KC: Maximizing the sum of the squares of the degrees of a graph. Discrete Math. 2004, 285: 57–66. 10.1016/j.disc.2004.04.007MathSciNetCrossRef

19.

Das KC, Gutman I: Some properties of the second Zagreb index. MATCH Commun. Math. Comput. Chem. 2004, 52: 103–112.MathSciNet

20.

Das KC: On comparing Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem. 2010, 63(2):433–440.MathSciNet

21.

Das KC, Gutman I, Zhou B: New upper bounds on Zagreb indices. J. Math. Chem. 2009, 46(2):514–521. 10.1007/s10910-008-9475-3MathSciNetCrossRef

22.

Nordhaus EA, Gaddum JW: On complementary graphs. Am. Math. Mon. 1956, 63: 175–177. 10.2307/2306658MathSciNetCrossRef

Titel: The number of spanning trees of a graph
verfasst von: Kinkar C Das
Ahmet S Cevik
Ismail N Cangul
Publikationsdatum: 01.12.2013
Verlag: Springer International Publishing
Erschienen in: Journal of Inequalities and Applications / Ausgabe 1/2013
Elektronische ISSN: 1029-242X
DOI: https://doi.org/10.1186/1029-242X-2013-395

Springer Professional

The number of spanning trees of a graph

Abstract

Electronic supplementary material

Competing interests

Authors’ contributions

Dedication

1 Introduction

2 Lemmas

3 Bounds on the number of spanning trees

4 Nordhaus-Gaddum-type results for the number of spanning trees of a graph

Acknowledgements

Competing interests

Authors’ contributions

Authors’ original submitted files for images

Premium Partner

Springer Professional

Abstract

Electronic supplementary material

Competing interests

Authors’ contributions

Dedication

1 Introduction

2 Lemmas

3 Bounds on the number of spanning trees

4 Nordhaus-Gaddum-type results for the number of spanning trees of a graph

Acknowledgements

Competing interests

Authors’ contributions

Authors’ original submitted files for images

Weitere Artikel der Ausgabe 1/2013

The modified general iterative methods for asymptotically nonexpansive semigroups in Banach spaces

A new characterization of Mathieu-groups by the order and one irreducible character degree

On the convergence of hybrid projection algorithms for total quasi-asymptotically pseudo-contractive mapping

Mazur-Ulam theorem under weaker conditions in the framework of 2-fuzzy 2-normed linear spaces

Coefficient estimates for new subclasses of Ma-Minda bi-univalent functions

Almost increasing sequences and their new applications

Premium Partner