/^creative ^commor ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 11 (2016) 403-413 New bounds for the sum of powers of normalized Laplacian eigenvalues of graphs* Gian Paolo Clemente, Alessandra Cornaro Catholic University, Department of Mathematics, Finance and Econometrics, Milan, Italy Received 5 May 2015, accepted 26 May 2016, published online 25 August 2016 Abstract For a simple and connected graph, a new graph invariant s*a(G), defined as the sum of a powers of the eigenvalues of the normalized Laplacian matrix, has been introduced by Bozkurt and Bozkurt (2012). Lower and upper bounds for this index have been proposed by the authors. In this paper, we localize the eigenvalues of the normalized Laplacian matrix by adapting a theoretical method, proposed in Bianchi and Torriero (2000), based on majorization techniques. Through this approach we derive upper and lower bounds of s*a(G). Some numerical examples show how sharper results can be obtained with respect to those existing in literature. Keywords: Graphs, majorization, topological indices, bounds. Math. Subj. Class.: 05C35, 05C05, 05C50 1 Introduction Among the various indices in Mathematical Chemistry, a whole new family of descriptors s*a(G), defined as the sum of a powers of the eigenvalues of the normalized Laplacian matrix, has been proposed by Bozkurt and Bozkurt in [7]. These authors found a number of bounds for arbitrary a and particularly for a = -1, which is the case of the degree Kirchhoff Index. Recently, Bianchi et al. proposed a variety of lower and upper bounds for s*a (G) in [1] and for the Kirchhoff Index in [2] derived via majorization techniques. In particular, the authors showed that it is possible to obtain tighter results taking into account additional information on the localization of the eigenvalues of proper matrices associated to the graph. From a theoretical point of view, some well-known inequalities on the localization of real eigenvalues have been provided in literature and they can be used to compute *We thank Monica Bianchi, Anna Torriero and an anonymous referee for their valuable comments and suggestions. E-mail addresses: gianpaolo.clemente@unicatt.it (Gian Paolo Clemente), alessandra.cornaro@unicatt.it (Alessandra Cornaro) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 404 Ars Math. Contemp. 11 (2016) 403-413 the above mentioned bounds. Alternative inequalities involving the localization of some eigenvalues of the transition matrix of the graph have been numerically computed in [9] and [10] by applying a theoretical methodology proposed in Bianchi and Torriero [5] based on nonlinear global optimization problems solved through majorization techniques. By means of these results, tighter lower bounds for the Kirchhoff Index for some classes of graphs have been derived in [9]. The original contribution of this paper is to exploit this fruitful theoretical method (see [5]) with the aim to provide some formulae that allow us to compute lower bounds for the first and the second eigenvalues of the normalized Laplacian matrix in a fairly straightforward way. These limitations on the eigenvalues are then used to assess bounds for sa(G) proposed in [1]. We then obtain new bounds for sJj(G) considering both non-bipartite and bipartite graphs. In Section 2 some preliminaries on graph theory are given. Furthermore, the definition of sa(G) and the existing bounds on this index are presented. In Section 3 we describe the nonlinear optimization problem based on majorization techniques. This methodology, useful for our analysis, allows us to localize the first and second eigenvalues of the normalized Laplacian matrix. Lower bounds of these normalized Laplacian eigenvalues have been obtained in Section 4. We prove that our limitation on the first normalized Laplacian eigenvalue is always sharper than the existing one for non-complete graph. By means of this result, we provide bounds on sJj(G) tighter than those given in [7]. Finally, in Section 5 a numerical comparison for bipartite and non-bipartite graphs is reported. 2 Notations and preliminaries In this section we first recall some basic notions on graph theory. For more details refer to [17]. Let G = (V, E) be a simple, connected, undirected graph where V = {1,2,..., n} is the set of vertices and E C V x V the set of edges, |E| = m. The degree sequence of G is denoted by n = (di, d2, .., dn) and it is arranged in non-increasing order d1 > d2 > • • • > dn, where di is the degree of vertex i. It is well n known that J2 d = 2m and that if G is a tree, i.e. a connected graph without cycles, i=i m = n - 1. Let A(G) be the adjacency matrix of G and D(G) be the diagonal matrix of vertex degrees. The matrix L(G) = D(G) - A(G) is called Laplacian matrix of G, while L(G) = D(G)-1/2L(G)D(G)-1/2 is known as normalized Laplacian matrix. Let P > P2 > ... > Pn be the (real) eigenvalues of L(G) and A1 > A2 > ... > An be the (real) eigenvalues of L(G). The following properties of spectra of L(G) and L(G) hold: y^Pi = tr(L(G)) = 2m; p > 1 + d1 > —; pn = 0, pn-1 > 0. n i=1 nn ^Ai = tr(L(G)) = n; ^2 = tr(L2(G)) = n + 2 ^ did-; An = 0; A1 < 2. i=1 i=1 (i,j)€E i j Our aim is the analysis of a particular topological index, sJj(G). In particular, Zhou (see [18]) proposed the index: n1 sa(G) = E = 0,1, G. P. Clemente and A. Cornaro: New bounds for the sum of powers of normalized Laplacian... 405 defined as the sum of the a-th power of the non-zero Laplacian eigenvalues of a graph G. Over the last years this index and its bounds have been intensely studied: Zhou (see [18]) established some properties of sa(G) and some improvements have been provided in [14], [16], [19] and [20]. In [3], taking into account the Schur-convexity or Schur-concavity of the functions sa(G) for a > 1 and a < 0 or 0 < a < 1 respectively, the same bounds as in [18] have been derived. Furthermore, considering additional information on the localization of the eigenvalues, the authors provide also sharper bounds. Bozkurt and Bozkurt in [7] introduced parallely to [18] the following new graph invariant: n-1 4(G) = E A?,a = 0,1, i=1 characterized as the sum of the a-th power of the non-zero normalized Laplacian eigenvalues of a graph. Several properties of this index have been proposed in [7] and some lower and upper bounds for a connected graph have been derived. In [1], considering the Schur-convexity or Schur-concavity of the functions s*a(G) and using additional information on the localization of the eigenvalues, the following Theorems, which generalize Theorem 3.3 in [7], have been proved. Theorem 2.1. Let G be a simple connected graph with n > 3 vertices and A1 > 0: 1. if a < 0 or a > 1 then sa(G) >0a + ^-1 2. if 0 < a < 1 then 4(G) < e*+. (2.2) Theorem 2.2. Let G be a simple connected graph with n > 4 vertices which is not complete and Ai > e, A2 > ß with e > ß and e + ß(n — 2) > n. 1. if a < 0 or a > 1 then (n — e — ß) (n — 3) 4(G) > ea + ßa + ^-i (2.3) 2. if 0 < a < 1 then (n — e — ß) (n — 3) 4 (G) < ea + ßa + 0,nß_i . (2.4) It is noteworthy to state that the results in Theorem 2.2 are tighter than those in Theorem 2.1 (for more details see [3] and [4]). In [7], the bounds in Theorem 2.1 have been previously proved identifying 0 as P = 1 + \ 2 E dV («> n(n — 1) did. In Section 4, by applying some results proved in [5], we provide lower bounds of A1 and A2 that enable us to assess tighter bounds of s*a(G) than in [7]. In particular, we obtain an alternative value of 0 than (2.5) (referred as Q) and a specific value of fi (referred as R). CK 406 Ars Math. Contemp. 11 (2016) 403-413 3 A nonlinear optimization problem to bound eigenvalues We now recall a methodology based on majorization techniques (see [5] and [15]) that allows us to find a suitable localization of Ai and A2. At this regard, we define the set n—1 n—1 S6A = {A e R+—1 : Ai > A2 > ... > An—1 > 0, ^ Ai = n,g(A) = ^ Af = b}, i=i i=1 where p is an integer greater than 1, b e R and g is a continuous function, homogeneous of degree p, real and strictly Schur-Convex (see [15]). The following fundamental lemma holds (see Lemma 2.1 in [5]): Lemma 3.1. Fix b e R and consider the set SThen either b = (n—l^jp-i or there exists a unique integer 1 < h* < (n — 1) such that: —-—r (h* + 1), S* is zero. It is noteworthy that we use this Theorem in the next Section to obtain lower bounds for A1 and A2. G. P. Clemente and A. Cornaro: New bounds for the sum of powers of normalized Laplacian... 407 4 New bounds for normalized Laplacian eigenvalues and s*a(G) We now present a schematic framework of the main steps we follow in order to provide new limitations for Ai and A2 useful to get new bounds for the descriptor s*a(G). 1. A new lower bound Q for Ai At this regard, we consider Theorem 3.2 limiting1 the analysis when p = 2: in this case we know indeed that b = n + 2 Y^ (i f.)£E -r-y. For Lemma 3.1, when b = (n-T) the solution of optimization problem P*(h) is (n-nr ). This is the case of n (n_1) the solution ui optimization piuulem p (h ) is I n_ i 2 the complete graph Kn. Instead, when b = ( " r), h " (n—I}> " ~ [_~b Considering non-complete graphs, to get a lower bound for A1 we solve Equation (3.2) being h = 1. By some basic algebra, the acceptable solution in the interval I is (n+V equal to 5* = ^-(i+h*}- and we refer to this value as Q. 2. New bounds for sjj, (G) based on Q Considering Theorem 2.1 we obtain new bounds for s*a(G) by replacing the generic limitation 0 with Q in (2.1) and (2.2). 3. Comparison between Q and P The value of Q can be compared to P (see Equation (2.5)) in order to show how bounds (2.1) and (2.2), computed by assuming 0 = Q, perform better than those with 0 = P (as proposed in [7]). It is well known that, for every connected graph of order n (see [2]), we have: ^ n E T,r< 1, (4.1) n — 1 n z—' Ad,-(i,ME j and the left inequality is attained for the complete graph G = Kn. Figure 1 reports patterns of P and Q, varying the quantity t = 2 • J2(ij)eE dlF in the proper interval (n—T > n) (see Equation (4.1)) for alternative values of number of vertices n. Being P = 1 + ^J n(nt_1), it is easy to see that P has a monotonic behaviour with respect to t. P G (n—T> 1 + \Jn—t), while Q G (-—t, 2). Furthermore, Figure 1 shows that Q increases faster than P when t g ( -—t, n 1For values of p = 2, b depends on the graph's structure and topology. So the procedure can be only numerically applied: we need to compute the eigenvalues of normalized Laplacian matrix, but this information allows to directly obtain sj (G). In this case, the evaluation of bounds is useless. 408 Ars Math. Contemp. 11 (2016) 403-413 Figure 1: Q and P according to different values of t G i,n) and several number of vertices. Going deeply into the analysis, we now analytically prove that our bound Q on Ai is always better than bound P provided in [7] Main Result. The limitation Q is strictly greater than P for non-complete graphs. Proof. We start considering: f (t) = Q - p n + (ra+t)(h* + 1)—- (1 + h*) 1 t — i — i(n - 1)' (4.2) where f (t) G (o, 1 - —)) , h* = [\ and h* G (L- J , n - 1) . Furthermore, when n(n - x) t n + x with x 0, 2, 4, 1, 3, 5, , (n - 2) if n is even , (n - 2) if n is odd (4.3) 2 2 ff+t isaninteger(i.e. h* = ff+t). We can now distinguish two cases: 2 when (4.3) holds, n+t is an integer. Doing some algebra, we have f (t) = . It is immediate to see that f (t) > 0, with f (t) = 0 only for n(n— 1) complete graphs (being in that case t = i); 2 h G. P. Clemente and A. Cornaro: New bounds for the sum of powers of normalized Laplacian... 409 • otherwise, is not an integer. Being f (t) > 0 at the boundaries of its domain and f (t) > 0 for values of t so that h* is an integer, by proving that f (t) is strictly increasing on its remaining domain, we have f (t) > 0. Since f (t) is required to be strictly increasing, we compute f'(t) =-, 1 2 - 2 ,1 n , 1 (defined in t = ^^). In order to show that f '(t) > 0, by simple algebra we get: t (n(n - 1) - h*(h* + 1)) + nh* (n - (h* + 1)) > 0. Being h* < n - 1 for non-complete graphs, we have f '(t) > 0. It follows that Q > P for non-complete graphs. □ Now, Ai > Q > P entails that bounds (2.1) and (2.2) with 6 = Q perform better than those in [7] (see [3] and [4] for more theoretical details). 4. A new lower bound R for A2 With the aim to improve previous results, we can now derive additional information on A2. We still apply Theorem 3.2, considering the case h = 2. Since h < (h* + 1), we solve the Equation (3.3) finding in the interval I the acceptable solution: l b(n-1)-n2 n — A/ - R = S* = n — A , „ 1 ' -1—2 n — 1 5. New bounds for s*a (G) based on Q and R Considering Theorem 2.2, it is possible to obtain new bounds for s*a (G) by replacing the generic limitations 6 and ^ with Q and R respectively in (2.3) and (2.4). In order to assess these bounds, both conditions of Theorem 2.2 must be satisfied. 2 In this case, the leftmost inequality of (4.1) implies b > ^nr. By plugging this information in the value of R, we easily obtain R < nrj that fulfills the condition R < Q of Theorem 2.2. The other condition, Q + R(n — 2) > n, required by Theorem 2.2 will be numerically checked in the next Section. In case of bipartite graphs it is well known that A1 = 2. If we set 6 = 2 in Theorem 2.1, we derive the same results found in [1]. Furthermore, by placing 6 = 2 and ^ = R in bounds (2.3) and (2.4), we also provide limitations for bipartite graphs. 5 Some numerical results The proposed bounds have been evaluated on different graphs. We now focus only on non-bipartite graphs and we provide a comparison with literature (see [7]). In order to assure a robust analysis, graphs have been randomly generated following the Erdos-Renyi (ER) model GER(n, q) (see [6], [8], [11] and [12]). Graphs have been obtained by using a MatLab code that gives back only connected graph based on the ER model (see [9] and [10]). In this fashion, the graph is constructed by connecting nodes randomly such that edges are included with probability independent from every other edge. The results are based on a classic assumption of a probability of existence of edges q equal to 0.5. We obtain indeed that the generated graphs have a number of edges not far from the half of its maximum value as proved in the literature (see for example [13]). 410 Ars Math. Contemp. 11 (2016) 403-413 At this regard, in Table 1, sa(G) has been computed for several graphs by fixing a equal to 0.5. We report values of upper bound (2.2) evaluated by using 6 = Q or 6 = P (as proposed in [7]). We refer to these bounds as (2.2Q) and (2.2P). Likewise bound (2.4QR) identifies bound (2.4) evaluated when 6 = Q and ft = R, where the results has been provided assuring that assumptions of Theorem 2.2 are satisfied. Relative errors r measures the absolute value of the difference between the upper bounds and s*a(G) divided by the value of (G). We observe an improvement with respect to existing bounds according to all the analyzed graphs and the improvement appears reduced for very large graphs. However, for large graphs the formula provided in [7] already gives a very low relative error. n dl m sa (G) bound (2.2 Q) bound (2.4QR) bound (2.2 P) r(2.2Q) r(2.4QR) r(2.2P) | 4 2 3 3.35 3.44 3.43 3.46 2.86% 2.55% 3.47% 5 4 9 4.46 4.47 4.47 4.47 0.23% 0.21% 0.25% 6 3 6 5.30 5.47 5.46 5.48 3.13% 3.00% 3.27% 7 5 14 6.43 6.48 6.48 6.48 0.83% 0.81% 0.86% 8 5 13 7.33 7.48 7.48 7.48 2.02% 1.98% 2.06% 9 6 16 8.31 8.48 8.48 8.48 2.04% 2.01% 2.07% 10 8 25 9.39 9.51 9.48 9.52 1.36% 1.04% 1.37% 20 15 95 19.37 19.51 19.49 19.51 0.71% 0.62% 0.72% 30 19 209 29.36 29.50 29.50 29.50 0.49% 0.46% 0.49% 50 33 604 49.37 49.50 49.50 49.50 0.27% 0.26% 0.27% 100 60 2459 99.37 99.50 99.50 99.50 0.13% 0.12% 0.13% 200 116 10001 199.38 199.50 199.50 199.50 0.06% 0.05% 0.06% 300 179 22437 299.37 299.50 299.50 299.50 0.04% 0.04% 0.04% 500 279 62456 499.38 499.50 499.50 499.50 0.03% 0.02% 0.03% Table 1: Upper bounds for s^ (G) for a = 0.5 and relative errors. The comparison has been extended in order to test the behaviour of the upper bounds on alternative graphs. First of all, in the ER model used to generate graphs, the parameter q can be thought of as a weighting function. As q increases from 0 to 1, the model becomes more and more likely to include graphs with more edges and less and less likely to include graphs with fewer edges. In this regard, we assign several values of q moving from the default value of 0.5. For sake of simplicity we report only the relative errors derived for graphs generated by using respectively q = 0.1 and q = 0.9 (see Figure 2). In all cases bound (2.4QR) assures the best approximation to s^ (G) for a = 0.5. We observe a best behaviour of all bounds when q = 0.9 because we are moving towards the complete graph. We have indeed that the density of the graphs increases as long as greater probabilities are considered. number of vertices number of vertices r(2.2Q) — r(2.4QR) - r(2.2P| - r(2.2Q) — r(2.4QR) - r(2.2P) Figure 2: Relative errors of upper bounds of Sq .5(G) for graphs ER(n, 0.1) and ER(n, 0.9) respectively. G. P. Clemente and A. Cornaro: New bounds for the sum of powers of normalized Laplacian... 411 Finally, for the same index sg.s (G), upper bounds have been evaluated for trees2. Table 2 depicts slighter differences for larger graphs in this case too. However it could be noticed how the relative improvement of bounds respect to other bounds is greater than in case of non-bipartite graphs. Despite greater relative errors are observed, bound (2.4QR) is confirmed as the tighter bound also in this case. Trees n *£ r(2.2Q) r(2.4QR) r(2.2P ) 4 3.35 2.04% 1.95% 3.47% 5 4.32 2.17% 2.14% 3.48% 6 5.23 3.56% 3.51% 4.73% 7 6.19 3.62% 3.59% 4.67% 8 7.15 3.67% 3.64% 4.61% 9 8.22 2.35% 2.34% 3.20% 10 8.85 6.35% 6.32% 7.15% 20 18.07 7.45% 7.44% 7.88% 30 27.63 6.47% 6.47% 6.77% 50 45.73 8.07% 8.06% 8.25% 100 91.23 8.97% 8.97% 9.06% 200 182.72 9.14% 9.14% 9.18% 300 274.71 8.99% 8.99% 9.02% 500 457.71 9.11% 9.11% 9.13% Table 2: s05(G) and relative errors for Trees T. The analysis has been further developed considering a value of a equal to 1.5. Generating a similar sample of graphs, both s|.5 (G) and the relative bounds have been derived. For sake of simplicity we report only the results for ER(n, 0.5) observing that the additional information on the localization of Ai and A2 lead to the tighter lower bound (2.3QR). Analogous results have been obtained by considering both ER graphs with alternative values of q and bipartite graphs. n | di | m || s%{G> | bound (2.1Q) | bound(2.3QR) | bound(2.1P ) || r(2.1Q) | r(2.3QR) | r(2.1P ) 4 3 4 4.79 4.66 4.67 4.62 2.69% 2.39% 3.49% 5 2 4 6.22 5.65 5.69 5.60 9.07% 8.51% 9.95% 6 4 9 6.85 6.59 6.60 6.57 3.78% 3.63% 4.00% 7 6 13 7.77 7.57 7.57 7.56 2.56% 2.49% 2.65% 8 7 18 8.75 8.56 8.56 8.55 2.15% 2.10% 2.20% 9 4 12 10.28 9.58 9.59 9.55 6.88% 6.79% 7.15% 10 7 26 10.83 10.52 10.55 10.51 2.90% 2.60% 2.94% 20 13 98 20.88 20.50 20.52 20.50 1.81% 1.71% 1.81% 30 19 222 30.88 30.50 30.51 30.50 1.21% 1.18% 1.21% 50 31 644 50.85 50.50 50.51 50.50 0.68% 0.67% 0.68% 100 62 2512 100.87 100.50 100.50 100.50 0.37% 0.36% 0.37% 200 117 9918 200.88 200.50 200.50 200.50 0.19% 0.19% 0.19% 300 179 22540 300.87 300.50 300.50 300.50 0.12% 0.12% 0.12% 500 279 62063 500.88 500.50 500.50 500.50 0.08% 0.08% 0.08% Table 3: Lower bounds for si.5(G) and absolute value of relative errors. 6 Conclusions In this paper we provide tighter bounds for the sum of the a-power of the non-zero normalized Laplacian eigenvalues taking into account additional information on the localization of the eigenvalues of the normalized Laplacian matrix of the graph, L(G). To this aim lower bounds of the eigenvalues are derived by means of the solution of a class of suitable nonlinear optimization problems based on majorization techniques. We provide indeed closed 2 Tree has been generated by using Prufer code. The Priifer sequence of a labeled tree is a unique sequence associated to the tree. The sequence for a tree on n vertices has length n — 2 and it can be generated by a simple iterative algorithm. It is a way to map bijectively trees on n vertices into n — 2 long sequences of integers drawn from n. 412 Ars Math. Contemp. 11 (2016) 403-413 formulae that allow to compute upper and lower bounds of s*a(G) by using the additional information on the first and the second eigenvalue of L(G). It is noteworthy that even only considering the limitation on the first normalized Laplacian eigenvalue we improve existing bounds of s*a(G) for non-complete graphs. Numerical comparisons confirm how bounds based also on the second normalized Laplacian eigenvalue are former than those presented in literature. In particular, the analysis has been developed randomly generating both bipartite and non-bipartite graphs with a different number of vertices. References [1] M. Bianchi, A. Cornaro, J. Palacios and A. Torriero, Bounding the Sum of Powers of Normalized Laplacian Eigenvalues of Graphs through Majorization Methods, MATCH Commun. Math. Comput. Chem. 70(2) (2013), 707-716. [2] M. Bianchi, A. Cornaro, J. Palacios and A. Torriero, Bounds for the Kirchhoff index via majorization techniques, J. Math. Chem. 51(2) (2013), 569-587. [3] M. Bianchi, A. Cornaro and A. Torriero, A majorization method for localizing graph topologi-cal indices, Discrete Appl. Math. 161 (2013), 2731-2739. [4] M. Bianchi, A. Cornaro and A. Torriero, Majorization under constraints and bounds of the second Zagreb index, Mathematical Inequalities and Applications 16(2) (2013), 329-347. [5] M. Bianchi and A. Torriero, Some localization theorems using a majorization technique, Journal of Inequalities and Applications 5 (2000), 443-446. [6] B. Bollobas, Random Graphs, Cambridge Univ. Press, London, 2001. [7] S. Bozkurt and D. Bozkurt, On the sum of powers of normalized laplacian eigenvalues of graphs, MATCH Commun. Math. Comput. Chem. 68 (2012), 917-930. [8] F. R. K. Chung, L. Lu and V. Vu., The spectra of random graphs with given expected degrees, Proceedings of the National Academy of Sciences (2003), 6313-6318. [9] G. P. Clemente and A. Cornaro, Computing Lower Bounds for the Kirchhoff Index Via Majorization Techniques, MATCH Commun. Math. Comput. Chem. 73 (2015), 175-193. [10] A. Cornaro and G. P. Clemente, A New Lower Bound for the Kirchhoff Index using a numerical procedure based on Majorization Techniques, Electronic Notes in Discrete Mathematics 41 (2013), 383-390. [11] P. Erdos and A. Renyi, On Random Graphs I, Publicationes Mathematicae 6 (1959), 290-297. [12] P. Erdos and A. Renyi, On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17-61. [13] E. Estrada, The Structure of Complex Networks: Theory and Applications, Oxford Univ. Press, New York, 2011. [14] M. Liu and B. Liu, A note on sum of powers of the Laplacian eigenvalues of a graphs, Appl. Math. Lett. 24 (2011), 249-252. [15] A. W. Marshall, I. Olkin and B. Arnold, Inequalities: Theory of Majorization and Its Applications, Springer, 2011. [16] G. X. Tian, T. Z. Huang and B. Zhou, A note on sum of powers of the Laplacian eigenvalues of bipartite graphs, Linear Algebra and its Applications 430 (2009), 2503-2510. [17] R. J. Wilson, Introduction to graph theory, Addison Wesley, 1996. [18] B. Zhou, On a sum of powers of the Laplacian eigenvalues of a graphs, Linear Algebra and its Applications 429 (2008), 2239-2246. G. P. Clemente and A. Cornaro: New bounds for the sum of powers of normalized Laplacian... 413 [19] B. Zhou, On a sum of powers of Laplacian eigenvalues and Laplacian Estrada index of graphs, MATCH Common. Math. Comput. Chem. 62 (2009), 611-619. [20] B. Zhou and A. Ilic, On a sum of powers of Laplacian eigenvalues of bipartite graphs, Czech. Math. J. 60 (2010), 1161-1169.