Laplacian energy of diameter 3 trees

This article appeared in a journal published by Elsevier. The attached copy is furnished to the author for internal non-commercial research and education use, including for instruction at the authors institution and sharing with colleagues. Other uses, including reproduction and distribution, or selling or licensing copies, or posting to personal, institutional or third party websites are prohibited. In most cases authors are permitted to post their version of the article (e.g. in Word or Tex form) to their personal website or institutional repository. Authors requiring further information regarding Elsevier’s archiving and manuscript policies are encouraged to visit: http://www.elsevier.com/copyright

Author's personal copy Applied Mathematics Letters 24 (2011) 918–923

Contents lists available at ScienceDirect

Applied Mathematics Letters journal homepage: www.elsevier.com/locate/aml

Laplacian energy of diameter 3 trees✩ Vilmar Trevisan a,∗ , João B. Carvalho a , Renata R. Del Vecchio b , Cybele T.M. Vinagre b a

UFRGS - Instituto de Matemática, Porto Alegre, Brazil

b

UFF - Instituto de Matemática, Niterói, Brazil

article

info

Article history: Received 7 July 2010 Received in revised form 30 December 2010 Accepted 31 December 2010 Keywords: Laplacian energy Tree Algebraic connectivity

abstract Let Tn be the set of all trees of diameter 3 and n vertices. We show that the Laplacian energy of any tree in Tn is strictly between the Laplacian energy of the path Pn and the star Sn , partially proving the conjecture that this holds for any tree. We also give a total order by the Laplacian energy in Tn . Moreover, we show that this order depends only on the algebraic connectivity of the tree: the Laplacian energy increases as the algebraic connectivity decreases in Tn . © 2011 Elsevier Ltd. All rights reserved.

1. Introduction For a simple graph G with vertices v1 , . . . , vn and adjacency matrix A, the spectrum of G is the set of eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn of A. The energy of a graph G is defined by the quantity E (G) =

n −

|λi |.

(1)

i=1

Similarly, the Laplacian spectrum of G is the set of eigenvalues µ1 ≥ µ2 ≥ · · · ≥ µn of the Laplacian matrix of G, given by L = D − A, where A is the adjacency matrix and D is the diagonal matrix of vertex degrees. It is well known that if G is a connected graph then the second smallest eigenvalue µn−1 is positive and it is called the algebraic connectivity of G. Given any graph G with average degree d, the Laplacian energy of G, defined by Gutman and Zhou [1] is given by LE (G) =

n −

|µi − d|.

(2)

i=1

An important open problem in the area of spectral graph theory is to determine which graph G among all graphs with n vertices has the maximum energy E (G). This problem has been settled for a few classes of graphs (see, for example [2]). In particular, it is known since 1977, due to Gutman [3], that among all trees with n vertices, the path Pn has maximum energy, whereas the star Sn has minimum energy. For the Laplacian energy, few results are established, so that the extremal energy graphs are not known even for trees. In [4], Radenković and Gutman studied the correlation between the energy and the Laplacian energy of trees. In that paper, the energy and the Laplacian energy for all trees up to 14 vertices are computed. They found that the energy and the Laplacian energy of a tree are inversely proportional, and formulated the following:

✩ First author was partially supported by CNPq- Grants 309531/2009-08 and 473815/2010-9.

∗

Corresponding author. Fax: +55 51 33086173. E-mail address: [email protected] (V. Trevisan).

0893-9659/$ – see front matter © 2011 Elsevier Ltd. All rights reserved. doi:10.1016/j.aml.2010.12.050

Author's personal copy V. Trevisan et al. / Applied Mathematics Letters 24 (2011) 918–923

919

Conjecture 1. Let Tn be a tree on n vertices. Then LE (Pn ) ≤ LE (Tn ) ≤ LE (Sn ). If this conjecture is true then the extremal energy trees for the Laplacian energy are the opposite of the extremal energy trees, a somewhat unexpected result. Moreover it means that the structural factors that increase the energy of a tree, decrease the Laplacian energy and vice versa, a remarkable fact. Using the set of trees available in Brendan McKay’s web page http://cs.anu.edu.au/~bdm/data/trees.html, we computed the spectrum and the Laplacian spectrum of all trees with less than 19 vertices. These spectra were arranged in a data base that can be accessed in the site1 and several experiments may be performed using that data. In particular, it is possible to reproduce Radenković and Gutman’s experiment and verify that for all the trees in the data base, the path has minimum Laplacian energy and the star has maximum Laplacian energy. In this paper we prove that Conjecture 1 is true for trees of diameter 3. A tree of diameter 3 can be seen as two stars with an edge linking their centers. Throughout this note we will denote a diameter 3 tree with n vertices by T (a, b), where n = a + b + 2 is the number of vertices and a ≥ b ≥ 1 are the leaves at each end of T (a, b). We prove that LE (Pn ) < LE (T (a, b)) < LE (Sn ) for any T (a, b). We also give a total order in the set of all trees of diameter 3, by showing that the Laplacian energy of T (a, b) is strictly decreasing as a function of a. Moreover, we note that the order by Laplacian energy in this class of trees is solely dependent on the algebraic connectivity of T (a, b), more precisely, the Laplacian energy of T (a, b) increases as its algebraic connectivity decreases. 2. Preliminaries In a graph G, a pendant vertex is a vertex of degree 1. A neighbor is a vertex adjacent to a pendant vertex. The following is a result of Faria [5]. Lemma 1. Let p and q be the number of leaves and neighbors of G, respectively. Then 1 is a Laplacian eigenvalue of G of multiplicity at least p − q ≥ 0. The next result is due to Brouwer and Haemers [6]. Lemma 2. Let µ1 ≥ µ2 ≥ · · · ≥ µn be the Laplacian eigenvalues of a connected graph G. Then

µi ≥ d i − i + 2 ,

i = 1, . . . , n,

where d1 ≥ d2 ≥ · · · ≥ dn is the degree sequence of the vertices of G. Let T be a tree with n vertices. In order to compute the characteristic polynomial of trees, we refer to [7,8] where a method which operates directly on the tree was proposed. That algorithm can readily be adapted to compute the characteristic polynomial of the Laplacian matrix. For the sake of completeness we briefly describe the procedure. The algorithm works by associating, with each vertex v , a rational function a(v) = rs . Here r and s are members of the polynomial ring Q[λ]. These are computed bottom–up starting with the leaves which are assigned λ − 1 (the tree can be rooted in an arbitrary way). Once all children of v have been processed, v is assigned the function a(v) = λ − dv −

− 1 , a(c ) c ∈C

(3)

where C is the set of its children and dv is the degree of v . After all vertices have been processed, we compute the characteristic polynomial by taking the product of all functions a(v): p(λ) =

∏

a(v).

(4)

v∈V

Lemma 3. The Laplacian characteristic polynomial of T (a, b) is p(λ) = λ (λ − 1)n−4 [λ3 + (−4 − b − a)λ2 + (ab + 2 a + 5 + 2 b)λ − b − a − 2]. Proof. This is an application of the algorithm described above.



3. Ordering by the Laplacian energy Let T = T (a, b) be a tree with n = a + b + 2 vertices and diameter 3, with a ≥ b ≥ 1. We notice that for any tree, its 2(n−1) average degree d = n = 2 − 2n . Lemma 4. T (a, b) has exactly 2 eigenvalues greater than d = 2 − 2n . 1 http://www2.mat.ufrgs.br/graphenergy/.

Author's personal copy 920

V. Trevisan et al. / Applied Mathematics Letters 24 (2011) 918–923

Proof. By Lemma 1, we notice that the eigenvalue 1 has multiplicity at least a + b − 2 = n − 4. It is also well known that µn = 0, and that µn−1 (the algebraic connectivity) is smaller than 1. Therefore, there are at least n − 2 eigenvalues smaller than d. The fact that there are 2 eigenvalues greater than d follows from Lemma 2, since

µ1 ≥ d1 + 1 = a + 2 ≥ 3, µ2 ≥ d2 = b + 1 ≥ 2. We remark that this proof can also be obtained by examining the characteristic polynomial p(λ) of T (a, b), given by Lemma 3.  Consider now the n-vertex class of trees T (a + k, b − k), for k = 0, . . . , b − 1. Theorem 1. The Laplacian energy of T (a + k, b − k) is a strictly decreasing function of k, for k = 0, . . . , b − 1. Proof. Let T = T (a + k, b − k) and T ′ = T (a + ℓ, b − ℓ), with ℓ > k ≥ 0. Let us denote the eigenvalues of T and T ′ by µ1 ≥ µ2 ≥ · · · ≥ µn and µ′1 ≥ µ′2 ≥ · · · ≥ µ′n , respectively. According to Lemmas 4 and 3, we notice that µi = µ′i , for all i, except for i = 1, 2 and n − 1. Therefore LE (T ) − LE (T ′ ) = (d − µn−1 ) − (d − µ′n−1 ) + (µ1 − d) − (µ′1 − d) + (µ2 − d) − (µ′2 − d)

= (µ1 + µ2 ) − (µ′1 + µ′2 ) + (µ′n−1 − µn−1 ).

(5)

Using Lemma 3, we can compute the characteristic polynomials of T and T and also the degree 3 polynomials q(λ) and q′ (λ) whose roots are µ1 , µ2 , µn−1 and µ′1 , µ′2 , µ′n−1 , respectively. The coefficients of λ2 of q(λ) and q′ (λ) are −[(a + k) + (b − k) + 4] and −[(a + ℓ) + (b − ℓ) + 4], respectively. In any case they equal n + 2. Hence, we have ′

µ1 + µ2 + µn−1 = n + 2 = µ′1 + µ′2 + µ′n−1 , or

(µ1 + µ2 ) − (µ′1 + µ′2 ) + (µn−1 − µ′n−1 ) = 0.

(6)

Now inserting Eq. (6) into Eq. (5) we obtain LE (T ) − LE (T ′ ) = 2(µ′n−1 − µn−1 ). Following the result of Grone and Merris [9], it is known that µ′n−1 < µn−1 . Therefore, LE (T ) − LE (T ′ ) < 0 and the result follows.  Corollary 1. Let n > 3 be an integer. Among all trees T (a, b) of diameter 3 and n vertices, T (n − 2, 1) has minimum Laplacian energy, whereas T (⌈(n − 2)/2⌉ , ⌊(n − 2)/2⌋) has maximum Laplacian energy. We observe that the order of the Laplacian energy of the trees T (a, b) depends only on the algebraic connectivity of T (a, b). Theorem 2. Let T = T (a, b) and T ′ = T (a′ , b′ ) be two trees of diameter 3 and n > 3 vertices with Laplacian spectrum given by µi , and µ′i , respectively, for i = 1, . . . , n. The following are equivalent: (i) µn−1 > µ′n−1 ; (ii) LE (T ) < LE (T ′ ); (iii) a > a′ .

Proof. From the proof of Theorem 1, we notice that LE (T ) − LE (T ′ ) = 2(µ′n−1 − µn−1 ). This proves the equivalence (i) and (ii). The implication (iii) → (ii) is given by Theorem 1. The implication (ii) → (iii) can be proven by contradiction using the same argument of Theorem 1.  The above result says that the ordering of diameter 3 trees by the Laplacian energy solely depends on the algebraic connectivity. More precisely, the Laplacian energy increases as the algebraic connectivity decreases. 4. Extremal Laplacian energy trees The next result plays an important role to prove that the star bounds the Laplacian energy among all trees with n vertices and diameter 3. Lemma 5. The algebraic connectivity µn−1 of T (a, b) satisfies

µn−1 >

2 n

.

Proof. Clearly the algebraic connectivity of T (a, b) is the smallest root of the factor q(λ) = λ3 + (−4 − b − a)λ2 + (ab + 2 a + 5 + 2 b)λ − b − a − 2,

Author's personal copy V. Trevisan et al. / Applied Mathematics Letters 24 (2011) 918–923

921

of the characteristic polynomial given by Lemma 3. By Lemma 4 we know that q(x) has two roots greater than d and since q(0) = −b − a − 2 < 0, it suffices to prove that q(2/n) < 0. Now by direct computation we see that q(2/n) = q(2/(a + b + 2)) is equal to

−

−4 ab + 2 b2 + 2 a2 + 2 a2 b2 + 4 a2 b + 2 ab3 + 4 ab2 + 4 a3 + 4 b3 + b4 + 2 a3 b + a4 , (a + b + 2)3

which is clearly negative, since (for example), 4ab2 − 4ab ≥ 0 for b ≥ 1.



Theorem 3. Let Sn be the star on n vertices. Then LE (Sn ) > LE (T (a, b)). Proof. It is well known that the Laplacian spectrum of Sn is {0, 1n−2 , n}, hence LE (Sn ) = d + (d − 1)(n − 2) + (n − d). By Lemma 4, LE (T (a, b)) = d + (d − µn−1 ) + (d − 1)(n − 4) + (µ2 − d) + (µ1 − d).

(7)

Hence, LE (Sn ) − LE (T (a, b)) = (n − d) + 2(d − 1) − (µ1 − d) − (µ2 − d) − (d − µn−1 )

= n − 2 + 2d + µn−1 − µ2 − µ1 = n+2−

4 n

+ µn−1 − µ2 − µ1 .

Now, since µn−1 , µ2 and µ1 are the roots of q(λ) = λ3 + (−4 − b − a)λ2 + (ab + 2 a + 5 + 2 b)λ − b − a − 2, we see that

µn − 1 + µ2 + µ1 = a + b + 4 = n + 2 , and hence 4

LE (Sn ) − LE (T (a, b)) = 2µn−1 − By Lemma 5, µn−1 >

2 , n

n

.

and the result follows.



We now proceed to prove that the Laplacian energy of the path Pn on n vertices is smaller than the Laplacian energy of T (a, b). Lemma 6. Let n > 2. Then cos

πi n

>

1 n

,

for i = 1, . . . , ⌊n/2⌋. Proof. Since the cosine function is decreasing in the interval being considered, it suffices to show that cos πni > 1n , for the largest integral value of i < n/2. If n is even, such value is i = (n − 2)/2, whereas, if n is odd, then i = (n − 1)/2. 3 1 π Let n be odd. Then cos πn n− = sin 2n . Now, because sin(x) ≥ x − x3! , we see that 2

sin

π 2n

−

1 n

≥

n2 (24π − 48) − π 3 48n3

,

2 which is positive for n > 2. Similarly for n even, cos πn n− = sin πn and 2

sin

π n

−

1 n

≥

n2 (6π − 6) − π 3

is positive for n > 2.

6n3 

Lemma 7. Let Pn be the path on n vertices. Then LE (Pn ) = 2 + 4

⌊− n/2⌋ i=1

cos

πi n

+

1 n

 (−1)n − 1 .

Author's personal copy 922

V. Trevisan et al. / Applied Mathematics Letters 24 (2011) 918–923

Proof. It is well known that the Laplacian spectrum of the path Pn is given by

µi = 2 + 2 cos

πi n

,

i = 1, . . . , n − 1,

µn = 0.

Thus we may write LE (Pn ) = d +

  n −1  n −1  − −   1  d − 2 − 2 cos π i  = d + 2  + cos π i  .    n n n  i=1

i=1

Using the fact that cos πn i = − cos πn (n − i) and Lemma 6 we see that LE (Pn ) = d + 4

⌊− n/2⌋

cos

i=1

where ϵ =

2

if n is even

n 0

if n is odd

πi

+ ϵ,

n

. Observing now that d = 2 − 2n , the result follows.



Theorem 4. Let Pn be the path on n vertices. Then LE (Pn ) < LE (T (a, b)). Proof. Our experiments (and also those of Radenković and Gutman [4]) show that this result is true for all values of n ≤ 18. So we may assume that n > 18. Using Eq. (7), we see that LE (T (a, b)) = d + (d − µn−1 ) + (d − 1)(n − 4) + (µ2 − d) + (µ1 − d)

= (d − 1)(n − 4) − µn−1 + µ2 + µ1 . Using the fact that µn−1 + µ2 + µ1 = a + b + 4 = n + 2 and noticing that d = 2 − 2n , we conclude that LE (T (a, b)) = 2n +

8 n

− 4 − 2µn−1 .

(8)

Now, by using Riemann’s sum to approximate integrals, it is possible to prove that π

∫

2

sin x dx ≥

1= 0

From this we see that LE (Pn ) ≤ 2 + 4

⌊ 2n ⌋ π − n j =1

∑⌊ 2n ⌋ j =1

n

π

cos

cos πj

πj n

≤

n

n

π

. . Hence, using Lemma 7, we write

.

Thus, using Eq. (8), LE (Pn ) − LE (T (a, b)) ≤ n Because µn−1 < 1 and



4

π

 8 − 2 + 6 + 2µn−1 − . n

> 0, it follows that   4 LE (Pn ) − LE (T (a, b)) ≤ n − 2 + 8, π 8 n

which is negative since n > 18.



5. Conclusions We have shown that Laplacian energy of any tree of diameter 3 and n vertices is strictly between the Laplacian energy of the path Pn and the Laplacian energy of the star Sn , a step towards the proof of Conjecture 1. We also gave a total ordering by the Laplacian energy on the set of diameter 3 trees.

Author's personal copy V. Trevisan et al. / Applied Mathematics Letters 24 (2011) 918–923

923

Fig. 1. Laplacian spectrum of trees of seven vertices.

Our data base available at our site2 is a useful tool to study the spectra of trees and to formulate conjectures. As an example, we show in Fig. 1 the data for the Laplacian spectrum of all trees of seven vertices. The trees can be ordered by their Laplacian energy and other invariants, such as diameter. We noticed that at least 4 eigenvalues are smaller than the average degree. This seems to be the case for all n and we state the following: Conjecture 2. For a tree T with n vertices, the number of Laplacian eigenvalues smaller than the average degree d is at least ⌈n/2⌉. Remark. Lemma 4 proves this conjecture for diameter 3 trees. Moreover, if Tk is a tree with diameter D = k + 2, which is a path Pk with a pendant vertices in an extremity and b in the other, and if k ≤ ⌊n/2⌋, then the conjectures follows easily. In fact, it is sufficient to note that 1 is a Laplacian eigenvalue of Tk with multiplicity at least a + b − 2 (Lemma 1). Considering the algebraic connectivity and 0, there are at least a + b Laplacian eigenvalues smaller than d. Since in Tk we have n = a + b + k, a + b = n − k > ⌈n/2⌉.

∑k

The conjecture is also true if we have a caterpillar with n = k + i=1 ai vertices and diameter D = k + 2, where k ≤ ⌊n/4⌋ and the integers satisfy ai ≥ 1, for all 1 ≤ i ≤ k. The multiplicity of 1 as a Laplacian eigenvalue of this graph is at ∑k least i=1 ai − k = n − 2k, by Lemma 1. Computing 0 and the algebraic connectivity, we have at least n − 2k + 2 Laplacian eigenvalues smaller than d and n − 2k + 2 ≥ ⌈n/2⌉ + 2. References [1] I. Gutman, B. Zhou, Laplacian energy of a graph, Linear Algebra Appl. 414 (2006) 29–37. [2] I. Gutman, The energy of a graph: old and new results, in: A. Betten, A. Kohnert, R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer-Verlag, 2001, pp. 196–211. [3] I. Gutman, Acyclic system with extremal Hückel π -electron energy, Theor. Chim. Acta 45 (1977) 79–87. [4] S. Radenković, I. Gutman, Total π -electron energy and Laplacian energy: how far the analogy goes? J. Serb. Chem. Soc. 72 (12) (2007) 1343–1350. [5] I. Faria, Permanental roots and the star degree of a graph, Linear Algebra Appl. 64 (1985) 255–265. [6] A.E. Brouwer, W.H. Haemers, A lower bound for the Laplacian eigenvalues of a graph: proof of a conjecture by Guo, Linear Algebra Appl. 429 (2008) 2131–2135. [7] G.H. Fricke, S.T. Hedetniemi, D.P. Jacobs, V. Trevisan, Reducing the adjacency matrix of a tree, Electron. J. Linear Algebra 1 (1996) 34–43. [8] D.P. Jacobs, V. Trevisan, Constructing the characteristic polynomial of a tree’s adjacency matrix, Congr. Numer. 134 (1998) 139–145. [9] R. Grone, R. Merris, Ordering trees by algebraic connectivity, Graphs Combin. 6 (1990) 229–237.

2 http://www2.mat.ufrgs.br/graphenergy/.