Bulletin T.CXXXVII de l’Académie serbe des sciences et des arts − 2008 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 33

NOTE ON LAPLACIAN ENERGY OF GRAPHS

G. H. FATH–TABAR, A. R. ASHRAFI, I. GUTMAN

(Presented at the 7th Meeting, held on October 26, 2007)

A b s t r a c t. Let G be an (n, m)-graph and μ_{1}, μ_{2}, …, μ_{n} its Laplacian

eigenvalues. The Laplacian energy LE of G is defined as ∑_{i=1}^{n} |μ_{i} − 2m/n|.

Some new bounds for LE are presented, and some results from the paper B. Zhou, I. Gutman, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) 134 (2007) 1–11 are improved and extended.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: Laplacian spectrum (of graph), Laplacian energy (of graph)

1. Introduction

Throughout this paper we are concerned with finite graphs. Let G be a graph of order (= number of vertices) n and size (= number of edges) m. We say that G is an (n, m)-graph. In some cases, the number of vertices of the graph G will be denoted as |G|.

As usual, the vertex and edge sets of G are denoted by V (G) and E(G) , respectively. Let V (G) = {v_{1}, v_{2}, …, v_{n}}. The adjacency matrix A(G) = [a_{ij}] of G is a square matrix of order n whose (i, j)-entry is equal to the number of edges between the vertices v_{i} and v_{j} . In this paper, we consider only simple graphs, i.e., graphs without multiple edges and loops. In this case, the adjacency matrix A(G) is a (0,1)-matrix. The spectrum of the graph G is the set of eigenvalues of A(G) , together with their multiplicities [1]. The energy of G is defined as the sum of absolute values of the eigenvalues of G. This quantity, introduced long time ago by one of the present authors [4], has noteworthy chemical applications [6, 9] and interesting mathematical properties [5].

Let D(G) = [d_{ij}] be the diagonal matrix associated with the graph G, defined so that d_{ii} is the degree of the vertex v_{i} and d_{ij} = 0 if i ≠ j. Then L(G) = D(G) − A(G) is the Laplacian matrix and its eigenvalues μ_{1}, μ_{2} …, μ_{n} the Laplacian eigenvalues of the graph G, forming its Laplacian spectrum. For details of the theory of Laplacian spectra see [15, 16, 17].

The Laplacian polynomial ψ(G, λ) of the graph G is the characteristic polynomial of its Laplacian matrix. Then the Laplacian eigenvalues are the zeros of ψ(G, λ) .

In what follows we assume that μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n}.

It is well known that for all graphs, μ_{n} = 0 , and that the multiplicity of 0 in the Laplacian spectrum of G is equal to the number of (connected) components of G.

The Laplacian energy is a recently conceived graph invariant [10], defined as

LE = LE(G) = ∑_{i=1}^{n} |μ_{i} − \frac{2m}{n}| .

The Laplacian energy is a proper extension of the graph–energy concept. The few, hitherto communicated, results on LE are found in the papers [2, 8, 10, 14, 20, 21].

The complement of the graph G is denoted by \overline{G}.

Suppose that G_{1} and G_{2} are two graphs with disjoint vertex and edge sets. Their disjoint union G_{1} ∪ G_{2} has the vertex set V (G_{1}) ∪ V (G_{2}) and edge set E(G_{1}) ∪ E(G_{2}) . Their Cartesian product G_{1} × G_{2} has the vertex set V (G_{1}) × V (G_{2}) and (a, x)(b, y) is an edge of G_{1} × G_{2} if a = b and xy ∈ E(H) , or ab ∈ E(G) and x = y. The product G_{1} × G_{2} × ⋯ × G_{k} is

defined analogously and in what follows will be denoted by ∏_{i=1}^{k} G_{i}.

The join G_{1} + G_{2} of the graphs G_{1} and G_{2} is obtained from G_{1} ∪ G_{2} , by connecting all vertices of G_{1} with all vertices of G_{2} . If G = G_{1}+G_{2}+⋯+G_{k}, then we write G = ∑_{i=1}^{k} G_{i}. In the case that G_{1} ≅ G_{2} ≅ ⋯ ≅ G_{k} ≅ H, we

denote G by k H.

2. Bounds for the Laplacian energy

Proposition 1. If G is an (n, m)-graph and ψ(G, λ) its Laplacian characteristic polynomial, then

LE(G) ≥ n |ψ (G, \frac{2m}{n})|^{1/n}  (1)

with equality if and only if G is a disjoint union of the empty graph \overline{K_{p}} and (n − p)/2 copies of K_{2} , 0 ≤ p ≤ n.

P r o o f. By the inequality between the geometric and arithmetic means,

\frac{LE(G)}{n} = \frac{1}{n} ∑_{i=1}^{n} |μ_{i} − \frac{2m}{n}| ≥ (∏_{i=1}^{n} |μ_{i} − \frac{2m}{n}|)^{1/n} = |∏_{i=1}^{n} (\frac{2m}{n} − μ_{i})|^{1/n}

and (1) follows from the fact that

ψ(G, λ) = ∏_{i=1}^{n}(λ − μ_{i}) .

Equality in (1) occurs if and only if for every i, j , 1 ≤ i, j ≤ n, the equality |μ_{i} − 2m/n| = |μ_{j} − 2m/n| is obeyed. This requires that either μ_{i} = 0 or μ_{i} = 4m/n, which happens if and only if the degree of every vertex of G is not greater than unity. □

Proposition 1 can be somewhat enhanced. Consider LE(G)^{2} :

LE(G)^{2} = ∑_{i=1}^{n} ∑_{j=1}^{n} |μ_{i} − \frac{2m}{n}| · |μ_{j} − \frac{2m}{n}|

= ∑_{i=1}^{n} (μ_{i} − \frac{2m}{n})^{2} + ∑_{i≠j} |μ_{i} − \frac{2m}{n}| · |μ_{j} − \frac{2m}{n}| .

By direct calculation we obtain

∑_{i=1}^{n} (μ_{i} − \frac{2m}{n})^{2} = Zg − 2m (\frac{2m}{n} − 1)

where Zg is the sum of squares of vertex degrees (often referred to as the Zagreb index [7, 18, 19]). By the geometric–arithmetic mean inequality,

∑_{i≠j} |μ_{i} − \frac{2m}{n}| · |μ_{j} − \frac{2m}{n}| ≥ n(n − 1) [∏_{i≠j} |μ_{i} − \frac{2m}{n}| · |μ_{j} − \frac{2m}{n}|]^{1/n(n−1)}

= n(n − 1) [∏_{i=1}^{n} |μ_{i} − \frac{2m}{n}|^{2(n−1)}]^{1/n(n−1)} = |∏_{i=1}^{n} (μ_{i} − \frac{2m}{n})|^{2/n}

= |∏_{i=1}^{n} (\frac{2m}{n} − μ_{i})|^{2/n} = |ψ (G, \frac{2m}{n})|^{2/n} .

Combining these two results we get

LE(G)^{2} ≥ Zg − 2m (\frac{2m}{n} − 1) + |ψ (G, \frac{2m}{n})|^{2/n}

i.e.,

LE(G) ≥ \sqrt{Zg − 2m (\frac{2m}{n} − 1) + |ψ (G, \frac{2m}{n})|^{2/n}} .

Proposition 2. If G is an (n, m)-graph, and \overline{G} is its complement, then

LE(G) − \frac{4m}{n} < LE(\overline{G}) ≤ LE(G) + 2(n − 1) − \frac{4m}{n} .  (2)

Moreover, equality on the right–hand side of (2) is attained if and only if G is the empty graph.

P r o o f. Clearly, L(G)+L(\overline{G}) = n I_{n}−J_{n}, where J_{n} is the square matrix of order n whose all entries are equal to unity. Because L(G) J_{n} = 0 = J_{n} L(G) , the matrix L(G) commutes with L(\overline{G}) . It follows that if μ_{1}(G) ≥ μ_{2}(G) ≥ ⋯ ≥ μ_{n}(G) then μ_{n}(\overline{G}) = 0 and μ_{n−i}(\overline{G}) = n − μ_{i}(G) , 1 ≤ i ≤ n − 1 . Thus \overline{m} + m = n(n − 1)/2 and so 2\overline{m}/n = n − 1 − 2m/n. Therefore,

LE(\overline{G}) = ∑_{i=1}^{n} |μ_{i}(\overline{G}) − \frac{2\overline{m}}{n}|

= ∑_{i=1}^{n−1} |n − μ_{i}(G) − (n − 1 − \frac{2m}{n})| + |0 − (n − 1 − \frac{2m}{n})|

= ∑_{i=1}^{n−1} |μ_{i}(G) − \frac{2m}{n} − 1| + |n − 1 − \frac{2m}{n}|

≤ ∑_{i=1}^{n−1} (|μ_{i}(G) − \frac{2m}{n}| + 1) + n − 1 − \frac{2m}{n}

= ∑_{i=1}^{n−1} |μ_{i}(G) − \frac{2m}{n}| + 2(n − 1) − \frac{2m}{n}

= LE(G) − \frac{2m}{n} + 2(n − 1) − \frac{2m}{n}

which directly implies the right–hand side inequality in (2).

In order to prove the left–hand side inequality in (2), notice that

LE(\overline{G}) = ∑_{i=1}^{n−1} |n − μ_{i}(G) − \frac{2\overline{m}}{n}| + \frac{2\overline{m}}{n}

= ∑_{i=1}^{n−1} |n − μ_{i}(G) − n + 1 + \frac{2m}{n}| + n − 1 − \frac{2m}{n}
= ∑_{i=1}^{n−1} |μ_{i}(G) − \frac{2m}{n} − 1| + n − 1 − \frac{2m}{n}

≥ ∑_{i=1}^{n−1} (|μ_{i}(G) − \frac{2m}{n}| − 1) + n − 1 − \frac{2m}{n}

= ∑_{i=1}^{n−1} |μ_{i}(G) − \frac{2m}{n}| − (n − 1) + n − 1 − \frac{2m}{n}

= ∑_{i=1}^{n} |μ_{i}(G) − \frac{2m}{n}| − \frac{2m}{n} − \frac{2m}{n}

= LE(G) − \frac{4m}{n} .

In order to complete the proof, assume that G is an empty graph. Then LE(G) = 0 and so LE(\overline{G}) = 2(n − 1) = LE(G) + 2(n − 1) − 4m/n.

We now suppose that LE(\overline{G}) = LE(G) + 2(n − 1) − 4m/n. Then in the inequality (2) it must be

∑_{i=1}^{n−1} |μ_{i}(G) − \frac{2m}{n} − 1|+|n − 1 − \frac{2m}{n}| = ∑_{i=1}^{n−1} (|μ_{i}(G) − \frac{2m}{n}| + 1)+n−1−\frac{2m}{n} .

Hence,

∑_{i=1}^{n−1} |μ_{i}(G) − \frac{2m}{n} − 1| = ∑_{i=1}^{n−1} (|μ_{i}(G) − \frac{2m}{n}| + 1)

which implies that

|μ_{i}(G) − \frac{2m}{n} − 1| = |μ_{i}(G) − \frac{2m}{n}| + 1

holds for every i. Therefore μ_{i}(G) ≤ 2m/n and so G is an empty graph. □

The inequalities (2) can be written also as

\frac{4m}{n} − 2(n − 1) ≤ LE(G) − LE(\overline{G}) < \frac{4m}{n}

which should be compared with the inequalities obtained in [21]:

2(n − 1) ≤ LE(G) + LE(\overline{G}) < n \sqrt{n^{2} − 1} .

By Proposition 2, one can see that

|LE(\overline{G}) − \frac{2\overline{m}}{n}| − |LE(G) − \frac{2m}{n}| ≤ n − 1 .

Proposition 3. Let G be a regular (n, m)-graph of degree r , r ≥ 2 , and L(G) its line graph. Then LE(G) ≤ LE(L(G)) < LE(G) + 2n(r − 2) .

P r o o f. By a result of Kel’mans [13], ψ(L(G), x) = (x−2r)^{m−n} ψ(G, x) . Therefore the Laplacian eigenvalues of L(G) are 2r (m − n times) and μ_{i}(G) , 1, 2, …, n. Clearly, |μ_{i}(G) − (2r − 2)| ≤ |μ_{i}(G) − r| + |r − 2| and so LE(G) ≤ LE(L(G)) ≤ LE(G) + 2n(r − 2) . In order to complete the proof, we must show that LE(L(G)) ≠ LE(G) + 2n(r − 2) . Otherwise, |μ_{i} − (2r − 2)| = |μ_{i} − r − (r − 2)| = |μ_{i} − r| + |r − 2| and so μ_{i} ≤ r, which is impossible. □

In the case r = 2 , Proposition 3 yields LE(L(G)) = LE(G) , which is trivially true since then L(G) ≅ G.

3. Laplacian energy of graph products

In [21] it was shown that for the Cartesian product G_{1}×G_{2} of two graphs G_{1} and G_{2} of the same size n,

LE(G_{1} × G_{2}) ≤ n LE(G_{1}) + n LE(G_{2}) .

We now obtain a generalization of this result:

Proposition 4. Let G_{1}, G_{2}, …, G_{k} be graphs with disjoint vertex sets. Then

LE (∏_{i=1}^{k} G_{i}) ≤ (∏_{i=1}^{k} |G_{i}|) ∑_{i=1}^{k} \frac{LE(G_{i})}{|G_{i}|}  (3)

with equality if and only if at most one of the graphs G_{i} is non-empty.

P r o o f. Suppose that G_{i} is an (n_{i}, m_{i})-graph, i = 1, 2, …, k, and that

G = ∏_{i=1}^{k} G_{i} = G_{1} × G_{2} × ⋯ × G_{k} is an (n, m)-graph. Then it is easy to see

that 2m/n = ∑_{i=1}^{k} 2m_{i}/n_{i}. On the other hand, by a result of Fiedler [3], the

Laplacian eigenvalues of ∏_{i=1}^{k} G_{i} are of the form ∑_{i=1}^{k} μ_{j_{i}} (G_{i}) , 1 ≤ j_{i} ≤ n_{i}.

Therefore,

LE(G) = ∑_{j_{1},j_{2},...,j_{k}} |∑_{i=1}^{k} μ_{j_{i}}(G_{i}) − \frac{2m}{n}| = ∑_{j_{1},j_{2},...,j_{k}} |∑_{i=1}^{k} μ_{j_{i}}(G_{i}) − ∑_{i=1}^{k} \frac{2m_{i}}{n_{i}} |

= ∑_{j_{1},j_{2},...,j_{k}} |∑_{i=1}^{k} (μ_{j_{i}}(G_{i}) − \frac{2m_{i}}{n_{i}} )| ≤ ∑_{j_{1},j_{2},...,j_{k}} ∑_{i=1}^{k} |μ_{j_{i}}(G_{i}) − \frac{2m_{i}}{n_{i}} |

= ∑_{i=1}^{k} ( ∏_{j=1,j≠i}^{k} |G_{j}|) LE(G_{i}) .

This implies (3).

For the second part of the proposition, we notice that LE = 0 for an empty graph, and so if all G_{i}’s are empty, then the equality in (3) holds. On the other hand, if one of the graphs G_{i} is non-empty and all other graphs are empty, then

LE (∏_{j=1}^{n} G_{j}) = LE (G_{i} × ∏_{j≠i} G_{j}) = \frac{n}{n_{i}} LE(G_{i}) = (∏_{i=1}^{k} n_{i}) ∑_{i=1}^{k} \frac{LE(G_{i})}{n_{i}}

and (3) holds again.

We now assume that the equality is satisfied. If so, then

|∑_{i=1}^{k} μ_{j_{i}} − \frac{2 m_{i}}{n_{i}} | = ∑_{i=1}^{k} |μ_{j_{i}} − \frac{2 m_{i}}{n_{i}} |

and if μ_{j_{t}} = 0 , then μ_{j_{i}} −2 m_{i}/n_{i} ≤ 0 for i ≠ t. Therefore, μ_{j_{i}} ≤ 2 m_{i}/n_{i} ≤ 0 and G_{i} is an empty graph for i ≠ t.

By this the proof has been completed. □

In [21] it was shown that if G_{1} and G_{2} are both (n, m)-graphs, and G_{1} + G_{2} is their joint, then

LE(G_{1} + G_{2}) = LE(G_{1}) + LE(G_{2}) + 2n − \frac{4m}{n} .

In what follows we state, without proof, the straightforward extension of this result:

Proposition 5.If all the graphs G_{1}, G_{2}, …, G_{k} are (n, m)-graphs, then

LE (∑_{i=1}^{k} G_{i}) = ∑_{i=1}^{k} LE(G_{i}) + 2(k − 1) (n − \frac{2m}{n}) .

Corollary 5.1. LE(k G) = k LE(G) + 2(k − 1)(n − 2m/n) .

Corollary 5.2. LE(K_{n}) = 2(n − 1) and LE(K\underbrace{n, n, …, n}_{k times}) = 2n(k − 1) .

Acknowledgment. One of us (A. R. A.) was partially supported by a grant from IUT (CEAMA). This work was also partially supported by the Serbian Ministry of Science and Environmental Protection through Grant no. 144015G.

REFERENCES

[1] D. C v e t k o v i ć, M. D o o b, H. S a c h s, Spectra of Graphs – Theory and Application, Barth, Heidelberg, 1995.

[2] N. M. M. d e A b r e u, C. T. M. V i n a g r e, A. S. B o n i f á c i o, I. G u t m a n, The Laplacian energy of some Laplacian integral graphs, MATCH Commun. Math. Comput. Chem. 60 (2008), 447–460.

[3] M. F i e d l e r, Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298–305.

[4] I. G u t m a n, The energy of a graph, Ber. Math.-Statist. Sekt. Forschungsz. Graz. 103 (1978), 1–22.

[5] I. G u t m a n, 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, Berlin, 2001, pp. 196–211.

[6] I. G u t m a n, Topology and stability of conjugated hydrocarbons. The dependence of total π-electron energy on molecular topology, J. Serb. Chem. Soc. 70 (2005), 441–456.

[7] I. G u t m a n, K. C. D a s, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004), 83–92.

[8] I. G u t m a n, N. M. M. d e A b r e u, C. T. M. V i n a g r e, A. S. B o n i f á - c i o, S. R a d e n k o v i ć, Relation between energy and Laplacian energy, MATCH Commun. Math. Comput. Chem. 59 (2008), 343–354.

[9] I. G u t m a n, O. E. P o l a n s k y, Mathematical Concepts in Organic Chemistry, Springer–Verlag, Berlin, 1986, chapter 8.

[10] I. G u t m a n, B. Z h o u, Laplacian energy of a graph, Lin. Algebra Appl. 414 (2006), 29–37.

[11] A. K. K e l’ m a n s, The number of trees in a graph I , Automat. Remote Control 26 (1965), 2118-2129.

[12] A. K. K e l’ m a n s, The number of trees in a graph II , Automat. Remote Control 27 (1966), 233-241.

[13] A. K. K e l’ m a n s, Properties of the characteristic polynomial of a graph, Kibernetiky na sluzhbu komunizmu 4 (1967) 27–41 (in Russian).

[14] J. L i u, B. L i u, A Laplacian–energy–like invariant of a graph, MATCH Commun. Math. Comput. Chem. 59 (2008), 355–372.

[15] R. M e r r i s, Laplacian matrices of graphs: A survey, Lin. Algebra Appl. 197–198 (1994), 143–176.

[16] R. M e r r i s, A survey of graph Laplacians, Lin. Multilin. Algebra 39 (1995), 19–31.

[17] B. M o h a r, The Laplacian spectrum of graphs, in: Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk (Eds.), Graph Theory, Combinatorics, and Applications, Wiley, New York, 1991, pp. 871–898.

[18] S. N i k o l i ć, G. K o v a č e v i ć, A. M i l i č e v i ć, N. T r i n a j s t i ć, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003), 113–124.

[19] B. Z h o u, Zagreb indices, MATCH Commun. Math. Comput. Chem. 52 (2004), 113–118.

[20] B. Z h o u, I. G u t m a n, On Laplacian energy of graphs, MATCH Commun. Math. Comput. Chem. 57 (2007), 211–220.

[21] B. Z h o u, I. G u t m a n, Nordhaus–Gaddum–type relations for the energy and Laplacian energy of graphs, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) 134 (2007), 1–11.

Department of Mathematics Faculty of Science University of Kashan Kashan 87317–51167 I. R. Iran Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia