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) 381-389 On maximum signless Laplacian Estrada index of graphs with given parameters Hamid Reza Ellahi Department of Mathematics, Faculty of Sciences, University of Qom, 37161-46611, Qom, I. R. Iran Gholam Hossein Fath-Tabar * Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, 87317-51167, Kashan, I. R. Iran Ahmad Gholami , Ramin Nasiri Department of Mathematics, Faculty of Sciences, University of Qom, 37161-46611, Qom, I. R. Iran Received 21 April 2015, accepted 15 December 2015, published online 19 July 2016 For a simple graph G on n vertices, the signless Laplacian Estrada index is defined as SLEE(G) = ¡Li eqi, where q1, q2,..., qn are the eigenvalues of the signless Laplacian matrix of G. In this paper, the unique graph on n vertices with maximum signless Lapla-cian Estrada index is determined among graphs with given number of cut edges, pendent vertices, (vertex) connectivity and edge connectivity, respectively. Keywords: Signless Laplacian Estrada index, semi-edge walk, cut edge, vertex connectivity, edge connectivity. Math. Subj. Class.: 05C50, 05C12, 05C35. 1 Introduction Throughout this paper, each graph, say G, is simple with its vertex and edge sets V(G) and E(G), respectively. If | V(G) | = n, then G is considered as an n-vertex graph. Let u and v be two vertices of G. We say that u is a neighbor of v, if they are joined together in G. The * Financially supported by University of Kashan (Grant No. 504631/6). E-mail addresses: H.R.Ellahi@Gmail.com (Hamid Reza Ellahi), Fathtabar@kashanu.ac.ir (Gholam Hossein Fath-Tabar), Gholami@Kashanu.ac.ir (Ahmad Gholami), R.Nasiri.82@Gmail.com (Ramin Nasiri) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ Abstract 382 Ars Math. Contemp. 11 (2016) 403-413 number of neighbors of v in G is called the degree of v, and denoted by dG (v). The vertex v of G is referred to as a pendent vertex if it has only one neighbor (i.e. dG(v) = 1). A cut edge of a (connected) graph G is an edge whose deletion disconnects G. The vertex (resp. edge) connectivity of G is the minimum number of vertices (resp. edges) which need to be removed to disconnect G or convert it to a single vertex. Let A(G) be the adjacency matrix of G and D(G) = [dj]nxn be the diagonal matrix, where the element dj is equal to dG(vj) if i = j, and 0 otherwise. The Laplacian matrix and signless Laplacian matrix of G are denoted by L(G) and Q(G), respectively, where L(G) = D(G) - A(G) and Q(G) = D(G) + A(G) (see [7,22]). We represent the eigenvalues of A(G), L(G) and Q(G) by Ai, A2,..., An; ^i, m2,..., Mn and qi, q2,..., qn, respectively. Estrada [11,12], for the first time, defined a graph-spectrum-based invariant and named it Estrada index, which is as follows: EE (G) = £ eXi Fath-Tabar et al. [13] proposed the Laplacian Estrada index (after here LEE), in full analogy with Estrada index as LEE(G) = Estrada and Laplacian Estrada indices have been studied in a large variety of problems. In the mathematical literature, there are two types of problems in almost all papers researching on such indices: finding bounds for the index (e.g. [1,4, 16, 20, 24]), and determining extremal graphs with respect to the index (e.g. [10,21,23,25]). Ayyaswamy et al. [2] defined the signless Laplacian Estrada index (SLEE) as SLEE (G) = £ e 1 They also established lower and upper bounds for SLEE in terms of the number of vertices and edges. They showed that for any graph G on n vertices and m edges, \Jn + 4 m + n (n - 1) e< SLEE(G) < n - 1 + eV("2-n+2 m)m with equality on both sides if and only if G is empty. In the same sense, Binthiya et al. [5] established upper bound for SLEE in terms of the vertex connectivity of graph and the specific corresponding extremal graph. They find that [5, Theorem 3.1.] for each (n, m)-graph G with vertex connectivity k, SLEE(G) < k en-2 + (n - k - 2) en-3 + e2 n+K-4. It is well-known that the Laplacian and signless Laplacian spectra of bipartite graphs coincide (see [14,15]). Thus, for a bipartite graph G, SLEE(G) = LEE(G). Chemically, since the vast majority of molecular graphs are bipartite, we can use the provided statements in SLEE for LEE, and vice versa. However, the interesting case occurs when SLEE H. R. Ellahi et al.: On maximum SLEE of graphs with given parameters 383 and LEE differ, namely, in fullerenes, fluoranthenes and other non-alternant conjugated species [3,9,17-19], Moreover, Cvetkovic et al. [8] gathered many reasons about advantage of studying Q-spectra. They found that the signless Laplacian spectra perform better in comparison to spectra of other commonly used graph matrices, say the Laplacian, or the Seidel matrix. Also, they expressed that among generalized adjacency matrices, i.e. matrices which are a linear combination of A(G), J (the all-ones matrix) and I (the identity matrix) with a non-zero coefficient for A(G), the signless Laplacian seems to be the most convenient for use in studying graph properties. The goal of this paper is to find the unique extremal graph with maximum SLEE among all /'-vertex graphs with given number of cut edges, pendent vertices, (vertex) connectivity, or edge connectivity. Our main results are the following two theorems: Theorem 1.1. Let 0 < p < n, and GnjP be the graph obtained by attaching p pendent vertices to one vertex of complete graph Kn (see Figure 1). Then, up to isomorphism, we have: 1. Among the set of all n-vertex graphs having p cut edges, Gn p is the unique graph with maximum SLEE. 2. Among the set of all n-vertex graphs having p pendent vertices, GnjP is the unique graph with maximum SLEE. Figure 1: An illustration of the general forms of Gn p and l((l/ ,ljr, with some examples. Theorem 1.2. Let p, q and r be three non-negative integers, and let q-)r be the graph obtained from three vertex-disjoint complete graphs K , K and I\r, by attaching any vertex of I\r to all vertices of both K and K (see Figure 1). Then, up to isomorphism, we have: 384 Ars Math. Contemp. 11 (2016) 403-413 1. Among the set of all n-vertex graphs with vertex connectivity k, where 0 < k < n—1, K(„-i-k,i)k is the unique graph with maximum SLEE. 2. Among the set of all n-vertex graphs with edge connectivity k' , where 0 < k' < n—1, K(„_i_k',i)k' is the unique graph with maximum SLEE. 2 Preliminaries and lemmas Before proving our main theorems, we shall provide some fundamental definitions and propositions. In this section, we first declare some basic and useful notations, definitions and a proved theorem; afterward, we propose three effective lemmas to prove Theorems 1.1 and 1.2. Denote by Tk(G) the k-th signless Laplacian spectral moment of the graph G, i.e., Tk (G) = J2n= i qk. By applying the Taylor expansion to the function ex, we have: SLEE(G) = £ ^. (2.1) k> o ' Moreover, by the following definition and theorem, we can easily compare the SLEE's of some graphs. Definition 2.1. [8] A semi-edge walk of length k in a graph G is an alternating sequence W = v1e1v2e2 • • • vkekvk+1 of vertices v1, v2,..., vk, vk+1 and edges e1, e2,..., ek such that the vertices v and vi+1 are end-vertices (not necessarily distinct) of the edge e4, for any i = 1, 2,..., k. If v1 = vk+1, then W is said to be a closed semi-edge walk. Theorem 2.2. [8] The signless Laplacian spectral moment Tk is equal to the number of closed semi-edge walks of length k. Let G and G' be two graphs, and x,y G V(G), and x', y' G V(G'). Denoting by SWk (G; x, y), the set of all semi-edge walks of length k in G, each of which starts at vertex x and ends at vertex y. Note that |SWk(G; x,y)| = |SWk(G; y,x)| for any x, y G V(G). For convenience, we may denote SWk(G; x, x) by SWk(G; x). The notation SWk (G) will be used as the set of all closed semi-edge walks of length k in G, i.e. SWk(G) = QxeV(G) SWk (G; x). We will use the notation (G; x,y) (G'; x',y') when for any k > 0, |SWk(G; x,y)| < |SWk (G'; x', y')|. Moreover, if (G; x,y) (G'; x' ,y'), and there exists some k0 where |SW^ (G; x, y) | < |SWk (G'; x', y') |, then we will write (G; x, y) (G'; x',y'). We abbreviate (G; x, x) (G'; x',x') as (G; x) (G'; x'), and (G; x, x) (G'; x', x') as (G; x) (G'; x'). Indeed, by using the above notations, we can restate the Theorem 2.2 as: Tk (G) = |SWk (G; x)| = | (J SWk (G; x)| = £ |SWk (G; x)|. (2.2) xev(G) xev(G) Let G be a graph and E be a set of edges. If E C E(G), then we write G — E for the graph obtained from G by removing all of its edges in E. Also, if E C E(G), then we denote by G + E the graph obtained from G by adding all of edges in E to the graph. For convenience, we set G + e for G + {e}. The next result immediately follows from equations (2.1) and (2.2). H. R. Ellahi et al.: On maximum SLEE of graphs with given parameters 385 Lemma 2.3. Let G be a graph. If e is an edge such that e 0. Similarly, (G; wi,v) ^s (G; wi,u) implies that there exist following injections for each i = 1, 2,... ,r, and k > 0: fk : SWk (G; wi,v) ^ SWk (G; wi,u) gk : SWk (G; v,wi) ^ SWk(G; u,wi) For any W e SWk(G; x, y) where x,y e {v,w1,..., wr}, let W be as follows: 1) If k = 0 and W = wt, where t e {1,..., r}, then W = W. 2) If W e SWk(G; v), then W = fk(W). 3) If W e SWk(G; wt,v), then W = fk(W). 4) If W e SWk (G; v,wt), then W = gtk (W). 5) If W e SWk (G; wt, wj), where t,j e {1,..., r}, then W = W. 386 Ars Math. Contemp. 11 (2016) 403-413 To prove the statement, it is enough to show that Tk (Gv) < Tk(Gu), and there exists k0 such that inequality is strict. If W e SWk(Gv), then W can be decomposed uniquely to s + 1 sections as W = W1ej1 W2ej2 W3 • • • Wsejs Ws+1, where ej1,..., ejs e Ev, and for each i e {2,3,..., s}, there are x^y e {v,w^...,wr} such that Wi e SWk(G;x^yj. Moreover, since W is closed, for some x',y' e {v,w^...,wr}, W' = Ws+1W1 e SWk,(G;x',y') where k' = k1 + ks+1. Therefore, we can uniquely decompose W' to Ws+1 W1, where Ws+1 is a semi-edge walk of length ks+1 in G, starting at x and ending at z, and W1 is a semi-edge walk of length k1 in G, starting at z and ending at y, for some z e V(G) and x, y e {u, W1, ..., wr}. Now, one can show that the map hk : SWk (Gv) ^ SWk (Gu) defined by the rule hk (W) = hfc (W^ W2ej2 W3 • • • WseJs W^) = W jW2ej2W3 ••• WjWs+1 is injective, for each k > 0. Thus, Tk(Gv) < Tk (Gu), for any k > 0. Moreover, for some k0, /k[i is not surjective, and |SWk (G, v)| < |SWk (G, u)|, i.e. Tfco(Gv) < Tfco(G„). Hence SLEE(Gv) < SLEE(G„). ° ° □ The following lemma enables us to provide the necessary conditions in Lemma 2.4, and to use it to compare SLEE's of some particular graphs. Lemma 2.5. Let G be a graph and u,v e V(G). If v is a pendent vertex attached to u, then (G; v) (G; u), with equality if and only if dG(u) = dG(v) = 1. Moreover, (G; w, v) (G; w, u) for each w e V(G) \ {v}. Proof. The case k = 0 is trivial. Let k > 1 and W = veW'ev e SWk (G; v), where W' is a semi-edge walk of length k - 2 in G. We may construct an injection / : SWk (G; v) ^ SWk(G; u), by the rule /(W) = ueW'eu. Thus |SWk(G; v)| < |SWk(G; u)|, for any k > 2. Moreover, if dG(u) > 1, then we have |SW1 (G; v)| = dG(v) = 1 < dG(u) = |SW1(G; u)|. Recall that if dG(u) = 1, then G has an automorphism, interchanges u and v and fixes the other vertices. In a similar way, by changing the end of each member of SWk (G; w, v) from v to u, we find that (G; w,v) (G; w,u) for each w e V(G) \ {v}. Note that for k = 0, |SW0(G; v,v)| = 1 > 0 = |SW0(G; v,u)|. □ 3 The proof of Theorem 1.1 At the end of this section, we prove our first main theorem which determines the unique extremal graph with maximum SLEE among the set of all n-vertex graphs with given number of cut edges or pendent vertices. However, we should bring forth another lemma to this purpose. Let us denote by G (n,p), the set of all graphs obtained by attaching p pendent vertices to some vertices of a complete graph Kn-p , for 0 < p < n. Lemma 3.1. Suppose that 1 < p < n — 3, and G e G(n,p). If u and v are two distinct non-pendent vertices of G, such that dG(v) = n — p — 1 < dG(u), then (G; v) - 1, the map fk : SWk(G; v) ^ SWk(G; u) defined by the rule fk (veiWe^v) = uelWeJ.u is well-defined and injective, where e, = vw; and ej = uw,, for some neighbors w, of v and i G {1, k}. Therefore, |SWk(G; v)| < |SWk(G; u)|, for any k > 1. Moreover, |SWi(G; v)| = dG(v) = n - p - 1 < dG(u) = |SWi(G; u)| implies (G; v) (G; u). □ Proof of Theorem 1.1. To prove the first part, let G be an extremal n-vertex graph with maximum SLEE, having p cut edges. We shall show that G = Gn,p. If p = 0, then by Lemma 2.3, G = Kn = Gn,0. Moreover, if n = 1 or 2, then p = n - 1, and G = Kn = G„in-1. Therefore, suppose that n > 3 and p > 1. If E is the set of all cut edges in G, then by Lemma 2.3, all of p +1 connected components of G - E are complete. Suppose that there exists one edge e of E, attaching vertices u and v in G, where dG (u), dG (v) > 2. Let G' be the graph obtained from G by transferring all neighbors of v except u to the set of neighbors of u, and H be the transfer route graph. By Lemma 2.5, (H; v) (H; u). Thus, Lemma 2.4 results in SLEE(G) < SLEE(G'). This is a contradiction, because both graphs G and G' have the same number of cut edges. Therefore, each cut edge incidents to a pendent vertex. Let Vp be a set of vertices of G, each of which is a pendent vertex of a cut edge such that there is no cut edge with both ends in Vp. By Lemma 2.3, G - Vp is a complete graph on n - p vertices. Thus G is a graph obtained from Kn-p, by attaching p pendent vertices to some vertices of Kn-p, which means G G G(n,p). If G ^ Gn p, then there are at least two non-pendent vertices, say u and v, such that each of them has at least one pendent neighbor. Now, by Lemmas 2.4 and 3.1 and transferring pendent neighbors of v to the set of neighbors of u, we may get a graph with higher SLEE than G in G(n,p), which is a contradiction again. Therefore, G = Gn,p. Now, to prove the second part, suppose that G is an extremal n-vertex graph with maximum SLEE, having p pendent vertices. If H is the graph obtained from G, by removing all of its p pendent vertices, then by Lemma 2.3, H is a complete graph on n - p vertices. Thus G G G(n,p). Finally, the proof of this part is accomplished by using the same argument mentioned in the above paragraph. □ 4 The proof of Theorem 1.2 In this section, we are going to prove Theorem 1.2, which determines the unique extremal graph with maximum SLEE among the set of all n-vertex graphs with given (vertex) connectivity or edge connectivity. We start with the following lemma: Lemma 4.1. If 2 < q < p, and r > 0, then SLEE(K(p,q)r) < SLEE(K(p+q_1j1)r). Proof. Suppose that V (Kp) = {x1, x2,... ,xp}, and V (Kq) = {y1,y2 ,---,Vq}, and V(Kr) = {z1, z2,..., zr}. Let G be the graph obtained from K(p,q)r by transferring neighbors y2,..., yq of y1 to the set of neighbors of x1, and H be the transfer route graph. If r = 0, then obviously (H; y1) (H; x1). If r > 0, then, since any neighbor of y1 in H is a neighbor of x1, by a similar method used in the proof of Lemma 3.1, we can also show that (H; y1) (H; x1) and (H; yj,y1) (H; y,, x1), for each i G {2,..., q}. 388 Ars Math. Contemp. 11 (2016) 403-413 Therefore, Lemma 2.4 implies SLEE(K(p,q)r) < SLEE(G). Note that, since p > 2, G is a proper subgraph of K(p+g-11)r. Thus, by Lemma 2.3, SLEE(K(p g)r) < SLEE(G) < SLEE(K(p+q_M)r). □ Proof of Theorem 1.2. Note that the case k = n - 1 is trivial, because K(0j1)k = Kn is (up to isomorphism) the unique graph with vertex connectivity n - 1. Let G be an extremal graph with maximum SLEE, among n-vertex graphs with connectivity k. Suppose that S is a subset of V(G), where G - S is disconnected, and |S| = k. By Lemma 2.3, there exist integers p and q, such that 1 < q < p, p + q = n - k, and G - S is the union of two complete components Kq and Kp. Again, by Lemma 2.3, each vertex in S is attached to another one and also to vertices of both Kq and Kp. It means that G = K(p q)K. If q > 2, then Lemma 4.1 implies SLEE(G) < SLEE(K(p+q_M)K), which is a contradiction. Hence, q =1, and therefore G = K(n-1_Kj1)K. This proves the first part of the theorem. To prove the second part, we note that if G is a graph with vertex and edge connectivity k and k', respectively, then k < k' (see [6]). If k = k', then by previous part of the proof we have SLEE(G) < SLEE(K(„_1_k/j1)k/ ), and equality holds if and only if G = K(„_1_k/j1)k/. Moreover, if k < k' then K(n-1_Kj1)K is a proper subgraph of K(n_1_K/,1)K/. In this case, Lemma 2.3 and the above arguments show that SLEE(G) < SLEE(K(n_1_M)„) < slee(k(„_1_k,j1)k,). This completes the proof. □ References [1] A. R. Ashrafi and G. H. Fath-Tabar, Bounds on the Estrada index of ISR (4, 6)-fullerenes, Appl. Math. Lett. 24 (2011), 337-339, doi:10.1016/j.aml.2010.10.018, http://dx.doi. org/10.1016/j.aml.2 010.10.018. [2] S. K. Ayyaswamy, S. Balachandran, Y. B. Venkatakrishnan and I. Gutman, Signless Laplacian Estrada index, MATCH Commun. Math. Comput. Chem. 66 (2011), 785-794. [3] A. T. Balaban, J. Durdevic and I. Gutman, Comments on n-electron conjugation in the five-membered ring of benzo-derivatives of corannulene, Polycyclic Aromatic Compounds 29 (2009), 185-208, doi:10.1080/10406630903087784. [4] H. Bamdad, F. Ashraf and I. Gutman, Lower bounds for Estrada index and Laplacian Estrada index, Appl. Math. Lett. 23 (2010), 739-742, doi:10.1016/j.aml.2010.01.025, http://dx. doi.org/10.1016/j.aml.2010.01.025. [5] R. Binthiya and P. B. Sarasija, On the signless Laplacian energy and signless Laplacian Estrada index of extremal graphs, Appl. Math. Sci. (Ruse) 8 (2014), 193-198, doi:10.12988/ams.2014. 311621. [6] J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. [7] D. Cvetkovic, P. Rowlinson and S. Simic, An introduction to the theory of graph spectra, volume 75 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 2010. H. R. Ellahi et al.: On maximum SLEE of graphs with given parameters 389 [8] D. Cvetkovic, P. Rowlinson and S. K. Simic, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007), 155-171, doi:10.1016/j.laa.2007.01.009, http://dx.doi.org/ 10.1016/j.laa.2007.01.009. [9] J. R. Dias, Structure/formula informatics of isomeric sets of fluoranthenoid/fluorenoid and in-dacenoid hydrocarbons, Journal of mathematical chemistry 48 (2010), 313-329, doi:10.1007/ s10910-010-9671-9. [10] Z. Du, B. Zhou and R. Xing, On maximum Estrada indices of graphs with given parameters, Linear Algebra Appl. 436 (2012), 3767-3772, doi:10.1016/j.laa.2011.12.031, http://dx. doi.org/10.1016/j.laa.2011.12.031. [11] E. Estrada, Characterization of 3d molecular structure, Chemical Physics Letters 319 (2000), 713-718, doi:10.1016/S0009-2614(00)00158-5. [12] E. Estrada, Characterization of the folding degree of proteins, Bioinformatics 18 (2002), 697704, doi:10.1093/bioinformatics/18.5.697. [13] G. H. Fath-Tabar, A. R. Ashrafi and I. Gutman, Note on Estrada and L-Estrada indices of graphs, Bull. Cl. Sci. Math. Nat. Sci. Math. (2009), 1-16. [14] R. Grone and R. Merris, The Laplacian spectrum of a graph. II, SIAM J. Discrete Math. 7 (1994), 221-229, doi:10.1137/S0895480191222653, http://dx.doi.org/10.1137/ S0895480191222653. [15] R. Grone, R. Merris and V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990), 218-238, doi:10.1137/0611016, http://dx.doi.org/10.1137/ 0611016. [16] I. Gutman, H. Deng and S. Radenkovic, The Estrada index: an updated survey, Zb. Rad. (Beogr.) 14(22) (2011), 155-174. [17] I. Gutman and J. Durdevic, Fluoranthene and its congeners—a graph theoretical study, MATCH Commun. Math. Comput. Chem. 60 (2008), 659-670. [18] I. Gutman and J. Durdevic, On n-electron conjugation in the five-membered ring of fluoranthene-type benzenoid hydrocarbons, J. Serb. Chem. Soc 74 (2009), 765-771, doi: 10.2298/JSC0907765G. [19] I. Gutman and J. Durdevic, Cycles in dicyclopenta-derivatives of benzenoid hydrocarbons, MATCH Commun. Math. Comput. Chem. 65 (2011), 785-798. [20] A. Khosravanirad, A lower bound for Laplacian Estrada index of a graph, MATCH Commun. Math. Comput. Chem. 70 (2013), 175-180. [21] J. Li and J. Zhang, On the Laplacian Estrada index of unicyclic graphs, MATCH Commun. Math. Comput. Chem. 68 (2012), 835-842. [22] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994), 143176, doi:10.1016/0024-3795(94)90486-3, second Conference of the International Linear Algebra Society (ILAS) (Lisbon, 1992), http://dx.doi.org/10.1016/0024-3795(94) 90486-3. [23] W.-H. Wang, Unicyclic graph with maximal Estrada indices, MATCH Commun. Math. Comput. Chem. 68 (2012), 939-955. [24] B. Zhou and I. Gutman, More on the Laplacian Estrada index, Appl. Anal. Discrete Math. 3 (2009), 371-378, doi:10.2298/AADM0902371Z, http://dx.doi.org/10.22 98/ AADM0902371Z. [25] B.-X. Zhu, On the Laplacian Estrada index of graphs, MATCH Commun. Math. Comput. Chem. 66 (2011), 769-776.