Bulletin T.CXXVII de l’Académie Serbe des Sciences et des Arts - 2003 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 28

ON THE COEFFICIENTS OF THE LAPLACIAN CHARACTERISTIC POLYNOMIAL OF TREES

I. GUTMAN, LJILJANA PAVLOVIĆ

(Presented at the 1st Meeting, held on February 28, 2003)

A b s t r a c t. Let the Laplacian characteristic polynomial of an nvertex tree T be of the form ψ(T, λ) = ∑_{k=0}^{n}(−1)^{n−k} c_{k}(T) λ^{k}. Then, as well

known, c_{0}(T) = 0 and c_{1}(T) = n. If T differs from the star (S_{n}) and the path (P_{n}), which requires n ≥ 5 , then c_{2}(S_{n}) < c_{2}(T) < c_{2}(P_{n}) and c_{3}(S_{n}) < c_{3}(T) < c_{3}(P_{n}) . If n = 4 , then c_{3}(S_{n}) = c_{3}(P_{n}) .

AMS Mathematics Subject Classification (2000): 05C05, 05C12, 05C50 Key Words: Laplacian spectrum, Laplacian characteristic polynomial,

Trees, Distance (in graph), Wiener number

1. Introduction

Let G be a simple graph with vertex set V (G) = {v_{1}, v_{2}, …, v_{n}} and edge set E(G) = {e_{1}, e_{2}, …, e_{m}}. The adjacency matrix A(G) of G is a square matrix of order n whose (i, j)-entry is unity if the vertices v_{i} and v_{j} are adjacent, and is zero otherwise. The degree d_{i} of the vertex v_{i} is the number of first neighbors of this vertex. By D(G) we denote the square matrix of order n whose i-th diagonal element is equal to d_{i} and whose off–diagonal elements are zero. By I_{n} we denote the unit matrix of order n.

The Laplacian matrix of the graph G is L(G) = D(G) − A(G) . The characteristic polynomial of the Laplacian matrix, ψ(G, λ) = det(λI_{n} − L(G)) , is said to be the Laplacian characteristic polynomial of the graph G. In what follows we write it in the coefficient form as

ψ(G, λ) = ∑_{k=0}^{n}(−1)^{n−k} c_{k}(G) λ^{k} .

If so, then c_{k}(G) ≥ 0 for all k and for all G.

The connection between the coefficients of the Laplacian characteristic polynomial and the structure of the respective graph was established by Kel’mans long time ago [1, p. 38]:

c_{k}(G) = ∑_{F ∈F_{k}(G)} γ(F),  (1)

where F is a spanning forest and the summation goes over the set F_{k}(G) of all spanning forests of G, possessing exactly k components, and where γ(F) is the product of the number of vertices of the components of F .

Clearly, F_{0}(G) = ∅, which is consistent with the fact that c_{0}(G) = 0 for all graphs G.

In this work we are concerned with trees, i.e., connected and acyclic graphs. If T is an n-vertex tree, then for k ≥ 1 , the elements of F_{k}(T) are obtained by deleting k − 1 distinct edges from T . This, in particular, means that

|F_{k}(T)| = \binom{n − 1}{k − 1} .  (2)

Some immediate consequences of formulas (1) and (2) are:

c_{1}(T) = n  (3)
c_{n}(T) = 1  (4)
c_{n−1}(T) = 2(n − 1)  (5)

and [9]:

c_{n−2}(T) = 2 n^{2} − 5 n + 3 − \frac{1}{2} ∑_{i=1}^{n} d_{i}^{2}  (6)

c_{n−3}(T) = \frac{1}{3} [4 n^{3} − 18 n^{2} + 24 n − 10 + ∑_{i=1}^{n} d_{i}^{3} − 3(n − 2) ∑_{i=1}^{n} d_{i}^{2}] . (7)

The n-vertex star, denoted by S_{n}, is the n-vertex tree with maximum (= n − 2) number of vertices of degree one. The n-vertex path, denoted by P_{n} is the n-vertex tree with minimum (= 2) number of vertices of degree one.

Eqs. (3)–(5) imply that all n-vertex trees have equal Laplacian coefficients c_{1} , c_{n}, and c_{n−1} . In view of Eqs. (6) and (7), it is easy to verify that for any n-vertex tree, different from S_{n} and P_{n},

c_{n−2}(S_{n}) < c_{n−2}(T) < c_{n−2}(P_{n})  (8)
c_{n−3}(S_{n}) < c_{n−3}(T) < c_{n−3}(P_{n}) .  (9)

Recall that trees different from S_{n} and P_{n} exist only for n ≥ 5 .

In this work we show that among n-vertex trees, the star and the path are extremal also with respect to the Laplacian coefficients c_{2} and c_{3} . i.e., we demonstrate the validity of:

Theorem 1. Let T be an n-vertex tree, different from S_{n} and P_{n}. Then the inequalities

c_{2}(S_{n}) < c_{2}(T) < c_{2}(P_{n})  (a)

and

c_{3}(S_{n}) < c_{3}(T) < c_{3}(P_{n})  (b)

are obeyed for all T and all n ≥ 5 .

2. The Second Laplacian Coefficient and the Wiener Number

The Wiener number W (G) of a (connected) graph G is equal to the sum of distances between all pairs of vertices of G [2, 3]:

W (G) = ∑_{\{u,v\}⊆V (G)} d(u, v|G) = \frac{1}{2} ∑_{u∈V (G)} ∑_{v∈V (G)} d(u, v|G)  (10)

where d(u, v|G) denotes the distance (= number of edges in a shortest path) between the vertices u and v.

For the Wiener number of a tree T the following result is long known [10]:

W (T) = ∑_{e∈E(T)} n_{1}(e|T) n_{2}(e|T)  (11)

with n_{1}(e|T) and n_{2}(e|T) denoting the number of vertices of T , lying on the two sides of the edge e, and with summation going over all edges of T .

Now, n_{1}(e|T) and n_{2}(e|T) are just the number of vertices of the two components of the subgraph T − e, and T − e is just a spanning forest of T , possessing two components. In view of this, the product n_{1}(e|T) n_{2}(e|T) can be identified with γ(T − e) . Consequently, the right–hand side of Eq.

(11) can be identified with the the right–hand side of Eq. (1) for k = 2 , namely with ∑_{F ∈F_{2}(T)} γ(F) . We thus arrive at the noteworthy conclusion that

the second coefficient of the Laplacian characteristic polynomial (a linear– algebra–based quantity) coincides with the Wiener number (a metric–based quantity), i.e.,

c_{2}(T) = W (T) .  (12)

Relation (12) was known already to Merris, Mohar and McKay in the late 1980s [5, 6, 7, 8]. Combining it with the long–known inequalities [4]

W (S_{n}) ≤ W (T) ≤ W (P_{n})

we readily arrive at statement (a) of Theorem 1.

To these authors’ knowledge, until now part (a) of Theorem 1 has not been stated in the mathematical literature. Yet, it is a direct consequence of two previously known results, and thus cannot be considered as something new and original. Inequalities (a) have been included into Theorem 1 in order to stress their analogy to inequalities (b), and also to provide a motivation for the conjecture formulated at the end of this paper.

For completeness, we mention that

c_{2}(S_{n}) = W (S_{n}) = (n − 1)^{2} and c_{2}(P_{n}) = W (P_{n}) = \binom{n + 1}{3} . (13)

3. Proving Part (b) of Theorem 1

Preparations

Let G be a connected graph and u its vertex. Denote by d(u|G) the sum of the distances between u and all other vertices of G.

Lemma 2. If u is a terminal vertex of the path P_{n}, then d(u|P_{n}) = \binom{n}{2} .

P r o o f. The distances between u and the other vertices of P_{n} are 1, 2, …, n − 1 ._{□}

Lemma 3. Let e be an edge of the graph G, connecting the vertices r and s. If G is connected, but G − e disconnected, composed of components R and S, such that r ∈ V (R) and s ∈ V (S) (see Fig. 1) , then

W (G) = W (R) + W (S) + |R| d(s|S) + |S| d(r|R) + |R| |S|,

where |R| and |S| stand for the number of vertices of R and S, respectively.

P r o o f. Let x ∈ V (R) and y ∈ V (S) . Then d(x, y|G) = d(x, r|R) + d(s, y|S)+1 . Now, bearing in mind the definition (10) of the Wiener number, we obtain

W (G) = ∑_{{x,x′}⊆V (R)} d(x, x′|G) + ∑_{{y,y′}⊆V (S)} d(y, y′|G) + ∑_{x∈V (R)} ∑_{y∈V (S)} d(x, y|G)

= W (R) + W (S) + ∑_{x∈V (R)} ∑_{y∈V (S)}[d(x, r|R) + d(s, y|S) + 1]

= W (R) + W (S) + [ ∑_{x∈V (R)} d(x, r|R)] [ ∑_{y∈V (S)} 1]

+ [ ∑_{x∈V (R)} 1] [ ∑_{y∈V (S)} d(s, y|S)] + [ ∑_{x∈V (R)} 1] [ ∑_{y∈V (S)} 1] .

Lemma 3 follows now from

∑_{x∈V (R)} d(x, r|R) = d(r|R)

∑_{y∈V (S)} 1 = |S|

∑_{x∈V (R)} 1 = |R|

∑_{y∈V (S)} d(s, y) = d(s|S) . _{□}

Consider a special case of the graph G described in Lemma 3: Let S = P_{k} and let s be a terminal vertex of P_{k}. Denote this graph by R_{k}, see Fig. 1. Then by combining Lemmas 2 and 3, and bearing in mind that W (P_{k}) = \binom{k+1}{3} , we have

W (R_{k}) = W (R) + \binom{k + 1}{3} + |R| \binom{k}{2} + k [|R| + d(r|R)] .  (14)

Fig 1.

The structure and labeling of vertices and edges of graphs G and R_{k}, considered in Lemma 3 and Eq. (14), and of the trees T and T′, considered in Lemmas 4 and 5.

An Auxiliary Result

Let R be a tree on |R| vertices, |R| ≥ 2 . Let T and T′ be trees whose structure is depicted in Fig. 1. Hence, both T and T′ possess |R| + a + b + 1 vertices. If a = b, then T and T′ are isomorphic. Therefore, in what follows we shall assume that a ≠ b. Further, without loss of generality, we assume that a + 1 ≤ b.

Lemma 4. If T and T′ are the above specified trees (see Fig. 1), then for all a ≥ 0 and b ≥ 0 ,

c_{3}(T′) − c_{3}(T) = (b − a) [W (R) − d(r|R) + \frac{|R| − 1}{6} (b − a − 1)(b − a + 1)] .

(15)

P r o o f. According to Eq. (1), since T and T′ are trees,

c_{3}(T) = ∑_{f,g∈E(T)} γ(T −f −g)  and  c_{3}(T′) = ∑_{f′,g′∈E(T′)} γ(T′−f′−g′)

where f and g as well as f′ and g′ are distinct edges. In view of the structure of T and T′ (see Fig. 1), it is easily seen that for any pair of edges f, g one can find a pair of edges f′, g′, such that γ(T − f − g) = γ(T′ − f′ − g′) , except is one of the edges f, g coincides with edge e, and one of the edges f′, g′ coincides with edge e′, see Fig. 1. Bearing this in mind we have

c_{3}(T′) − c_{3}(T) = ∑_{f′∈E(T′)} γ(T′ − e′ − f′) − ∑_{f∈E(T)} γ(T − e − f) . (16)

Now, T − e consists of two components: P_{a+1} and R_{b}. Therefore, because the edge f belongs either to P_{a+1} or to R_{b},

∑_{f∈E(T)} γ(T − e − f) = ∑_{f∈E(P_{a+1})} γ(P_{a+1} − f ∪ R_{b}) + ∑_{f∈E(R_{b})} γ(P_{a+1} ∪ R_{b} − f)

= (|R| + b) ∑_{f∈E(P_{a+1})} γ(P_{a+1} − f) + (a + 1) ∑_{f∈E(R_{b})} γ(R_{b} − f)

which, in view of formula (11), results in

∑_{f∈E(T)} γ(T − e − f) = (|R| + b) W (P_{a+1}) + (a + 1) W (R_{b}) .

By an analogous reasoning,

∑_{f′∈E(T′)} γ(T′ − e′ − f′) = (|R| + a) W (P_{b+1}) + (b + 1) W (R_{a}) .

By substituting the above two expressions back into (16), and by taking into account Eq. (14), we obtain

c_{3}(T′) − c_{3}(T) = [(|R| + a) W (P_{b+1}) + (b + 1) W (R_{a})]
− [(|R| + b) W (P_{a+1}) + (a + 1) W (R_{b})]
= (|R| + a) \binom{b + 2}{3} − (|R| + a) \binom{a + 2}{3}

+ (b + 1) [W (R) + \binom{a + 1}{3} + |R| \binom{a}{2} + a [|R| + d(r|R)]]

− (a + 1) [W (R) + \binom{b + 1}{3} + |R| \binom{b}{2} + b [|R| + d(r|R)]] .

Lemma 4 follows now after a lengthy, but elementary, calculation. _{□}

Lemma 5. If T and T′ are the same trees as in Lemma 4, then c_{3}(T) = c_{3}(T′) if |R| = 2 and a = b − 1 . If either a + 1 < b or |R| > 2 or both, then c_{3}(T) < c_{3}(T′) .

P r o o f. Lemma 5 is an immediate consequence of Lemma 4. If |R| = 2 , then R = P_{2} and, consequently, W (R) = d(r|R) = 1 , i.e., W (R) − d(r|R) = 0 . If, in addition, b − a − 1 = 0 then the entire right–hand side of Eq. (15) is equal to zero.

If, however, |R| > 2 , then the Wiener number of R is necessarily greater than d(r|R) , implying that the right–hand side of (15) is positive–valued. Even if W (R) = d(r|R) , but a + 1 < b, the right–hand side of (15) is positive. _{□}

Completing the Proof

Let G be an n-vertex graph and F its spanning forest consisting of k components. Then γ(F) is equal to the product of k positive integers whose sum is equal to n. The smallest possible value of such a product is equal to n − k + 1 , namely when the respective k integers are n − k + 1 , 1 , 1 , …, 1 .

Now, if T is an n-vertex tree, then each of its k-component spanning forests is obtained by deleting from T a (k − 1)-tuple of distinct edges. In the case of the star S_{n} each of its k-component spanning forests consists of k isolated vertices and a copy of S_{n−k+1} . The γ-value of each of these spanning forests is minimal, equal to n − k + 1 . If k ≠ 1, n − 1, n, then any other n-vertex tree has a k-component spanning forest whose γ-value exceeds n − k + 1 . An exception is the 4-vertex path, considered below, cf. Eq. (17).

Bearing the above in mind, as well as Eqs. (1) and (2), we arrive at

Theorem 6. If T is an n-vertex tree, n ≥ 5 , different from S_{n}, then

c_{1}(T) = c_{1}(S_{n}) = n
c_{n−1}(T) = c_{n−1}(S_{n}) = 2(n − 1)
c_{n}(T) = c_{n}(S_{n}) = 1

whereas for 2 ≤ k ≤ n − 2 ,

c_{k}(T) > c_{k}(S_{n}) = \binom{n − 1}{k − 1}(n − k + 1) . _{□}

Clearly, the left–hand side inequalities (a) and (b) in Theorem 1 are special cases of Theorem 6.

In order to complete the proof of Theorem 1 we have to verify also the right–hand side of inequality (b). To do this consider the transformation T → T′ of the trees specified in Lemmas 4 and 5, see Fig. 1. If a + 1 ≤ b, then this transformation increases the third Laplacian coefficient, except when |R| = 2 and a + 1 = b, when the value of c_{3} remains the same.

Repeating the transformation T → T′ a + 1 times, the entire a-branch of T will be transferred to the b-branch and the degree of the vertex r diminished by one. Repeating such transformations sufficiently many times we will ultimately arrive at the path P_{n}. With a single exception (discussed below) such a multi–step transformation will necessarily increase the value of c_{3} , implying that for any n-vertex tree T , different from P_{n}, c_{3}(P_{n}) > c_{3}(T) .

The single exception is the case |R| = 2 , a = 0 , b = 1 . Then T = S_{4} and T′ = P_{4} . In this case, according to Lemma 5, the transformation T → T′ does not increase the value of the third Laplacian coefficient, and we thus have

c_{3}(S_{4}) = c_{3}(P_{4}) .  (17)

Because S_{4} and P_{4} are the only 4-vertex trees, the exception (17) does not effect the validity of the right–hand side inequality (b).

Thus we demonstrated that for n ≥ 5 the path P_{n} has maximum c_{3}-value among all n-vertex trees.

This proves the right–hand side of inequality (b).

The proof of Theorem 1 has thus been completed. _{□}

By the above considerations we also proved

Theorem 7. Among n-vertex trees, n ≥ 1 , n ≠ 4 , the unique tree with minimum third Laplacian coefficient is the star S_{n}, and the unique tree with maximum third Laplacian coefficient is the path P_{n}. Exceptionally, for n = 4 , S_{n} ≠ P_{n}, but c_{3}(S_{n}) = c_{3}(P_{n}) . _{□}

In analogy to Eq. (13),

c_{3}(S_{n}) = \frac{1}{2} (n − 1)(n − 2)^{2}  and  c_{3}(P_{n}) = \binom{n + 2}{5} .

4. Conclusion: A Conjecture

Summarizing Theorem 1 and Eqs. (3), (4), (5), (8), and (9), we see that the inequalities

c_{k}(S_{n}) ≤ c_{k}(T) ≤ c_{k}(P_{n})  (18)

hold for all values of n, and for all n-vertex trees T , provided k = 1, 2, 3, n− 3, n − 2, n − 1 , and n.

Conjecture. The inequalities (18) hold for all values of n , n ≥ 1 , for all n-vertex trees T , and for all values of k , 1 ≤ k ≤ n.

REFERENCES

[1] D. Cvetković, M. Doob, H. Sachs, Spectra of graphs — theory and application, Barth, Heidelberg, 1995.

[2] A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001), 211–249.

[3] A. A. Dobrynin, I. Gutman, S. Klavžar, P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002), 247–294.

[4] R. C. Entringer, D. E. Jackson, D. A. Snyder, Distance in graphs, Czech. Math. J. 26 (1976), 283–296.

[5] R. Merris, An edge version of the matrix–tree theorem and the Wiener index, Lin. Multilin. Algebra 25 (1989), 291–296.

[6] R. Merris, The distance spectrum of a tree, J. Graph Theory 14 (1990), 365–369.

[7] B. Mohar, The Laplacian spectrum of graphs, in: Y. Alavi, G. Chartrand, O. R. Ollermann, A. J. Schwenk (Eds.), Graph theory, combinatorics, and applications, Wiley, New York, 1991, pp. 871–898.

[8] B. Mohar, Eigenvalues, diameter, and mean distance in graphs, Graphs Combin. 7 (1991), 53–64.

[9] C. S. Oliveira, N. M. M. de Abreu, S. Jurkewicz, The characteristic polynomial of the Laplacian of graphs in (a, b)-linear classes, Lin. Algebra Appl. 356 (2002), 113–121.

[10] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), 17–20.

Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia and Montenegro