Scientific paper On Sum-Connectivity Matrix and Sum-Connectivity Energy of (Molecular) Graphs Bo Zhou1 and Nenad Trinajsti}2 1 Department of Mathematics, South China Normal University, Guangzhou 510631, China 2 The Rugjer Boškovic Institute, P. O. Box 180, HR-10002 Zagreb, Croatia * Corresponding author: E-mail: zhoubo@scnu.edu.cn, trina@irb.hr Received: 18-12-2009 This paper is dedicated to Professor Milan Randi} on the occasion of his 80th birthday Abstract If G is a (molecular) graph with n vertices, and di is the degree of its ¿-th vertex, then the sum-connectivity matrix of G is the n x n matrix whose (i, j) -entry is equal to 1/Vd; + dj if the ¿-th and the j-th vertices are adjacent and 0 otherwise. The sum-connectivity energy of a graph G is defined as the sum of the absolute values of the eigenvalues of the sum-connectivity matrix. Some properties including upper and lower bounds for the eigenvalues of the sum-connectivity matrix and the sum-connectivity energy are established, and the extremal cases are characterized. Keywords: Randic connectivity index, Randic matrix, product-connectivity matrix, sum-connectivity matrix, sum-connectivity energy, sum-connectivity index 1. Introduction Let G be a simple (molecular) graph with vertex set V(G) = {1, 2, ..., n}.1'2 For a vertex i e V(G), dt or di(G) denotes the degree of i in G. Recall that di = |r(i)|, where r(i) is the set of (first) neighbors of i in G. For vertices i and j of the graph G, i ~ j means that i and j are adjacent, i.e., ij is an edge of G. The product-connectivity matrix R = R(G) of the graph G is defined as It was discussed by Rodriguez3, Rodriguez and Si-garreta4, Hogben5 and Bozkurt et al.6 under different names the weighted adjacency matrix3, the degree-adjacency matrix4, the normalized adjacency matrix5 and the Randic matrix6. Recall that the product-connectivity index or the Randic index of the graph G is defined as in Ref. 7 and 8 The uses of the product-connectivity index and Ran-dic-like indices in the structure-property-activity modeling is summarized by Todeschini and Consonni in their two Handbooks910. Similarly these authors also discussed in their Handbooks the role of graph-theoretical matrices in deriving molecular descriptors (topological indices) and in describing molecules from a topological point of view1112. A useful summary of definitions and applications of graph-theoretical matrices in chemistry appeared recently13. In parallel to the definition of the product-connectivity index of Randic, the sum-connectivity index of the graph G is defined as in Ref. 14 and 15 Sum-connectivity index belongs to a family of Ran-dic-like indices. The uses of the sum-connectivity index in modeling a number of molecular properties is presented in the monograph entitled Novel Molecular Structure Des- criptors - Theory and Applications I, edited by Gutman and Furtula16. Similarly to the product-connectivity matrix, the sum-connectivity matrix S = S(G) of the (molecular) graph G is defined as Obviously, S(G) is a symmetric real matrix. Thus its eigenvalues are all real. The sum-connectivity energy of a graph G is defined as the sum of the abosulute values of the eigenvalues of its sum-connectivity matrix of G. The aim of this report is to study properties of the eigenvalues of the sum-connectivity matrix and the sum-connectivity energy, mainly upper and lower bounds of the largest and smallest eigenvalues, the spectral diameter (of the sum-connectivity matrix) and the sum-connectivity energy in terms of other structural invariants and complete characterizations for the extremal cases (for which the bounds are attained). 2. Definitions The adjacency matrix A = A(G) of the graph G is defined as1 For a square symmetric real matrix B, its eigenvalues are all real. The energy of B is defined as the sum of absolute values of its eigenvalues, denoted by E(B). The energy of the graph G is defined as17 E(G) = E(A(G)) = X|Ai|, where Xv ..., Xn are the eigenvalues of A(G) arranged in a non-increasing manner. The product-connectivity energy or the Randic energy of the graph G is defined as6 RE(G) = E(R(G)). Similarly, the sum-connectivity energy of the graph G is defined as SE(G) = E(S(G)) = X |u,.|, where ^2, ..., ^n are the eigenvalues of S(G) arranged in a non-increasing manner. Let tr(B) be the trace of the matrix B. Then |>f=fr(S) = 0, 1 /=1 i-\ J-t l-j "/ T "j d) (2) A graph is a semiregular graph of degrees r and s if it is a bipartite graph such that all vertices in one partite set have degree r and all vertices in the other partite set have degree s. 3. Properties of the Eigenvalues of the Sum-Connectivity Matrix Obviously the spectrum of the sum-connectivity matrix of a disconnected graph is the union of the spectra of the sum-connectivity matrices of its components. For a vector or matrix X, XT denotes its transpose. Lemma 1.18 Let B be a k x k non-negative irreducible symmetric matrix with exactly two distinct eigenvalues. Then B = uuT + rIk for some positive column vector u and some r where I, is the unit matrix of order k. Proposition 1. Let G be a graph with n > 2 vertices. Then (3) with equality if and only if G is an empty graph or a complete graph. Proof. From (1) and applying the Cauchy-Schwarz inequality, we have Mi = -2>, ] v (-2 From (2), we have M2 <(»-!) rld.+dj -/v and then (3) follows. It is obvious that (3) is an equality if G is an empty graph. Suppose that equality holds in (3) and G is nonempty. Then n2 = ••• = ^n and thus from (1), S(G) has exactly two distinct eigenvalues, and by (1), the eigenvalues are not equal to zero. Let H be a component of G say V(H) = {1, 2, ..., k}. Then S(H) has exactly two distinct eigenvalues. Note that S(H) is a non-negative irreducible symmetric matrix. By Lemma 1, S(H) = uuT + rIk for some positive column vector u and some r. Since each diagonal entry of S(H) is zero, each entry of u is equal to V-r.Thus for 1 < i, j < k with i # j all (i,j)-entries of S(H) are equal to -r, implying that G is a complete graph. Obviously, if G is a complete graph, then (3) is an equality. We mention that is a particular case of the general sum-connectivity in-dex19. Corollary 1. Let G be a graph with n > 2 vertices. Then In-1 R(G) with equality if and only if G is an empty graph or a complete graph. Proof. It is easily seen that with equality if and only if every component of G is regular. Now the result follows from Proposition 1. Corollary 2. Let G be a graph with n > 2 vertices. Then with equality if and only if G is a complete graph. Proof. Note that20 R(G) < n. Then the result follows from Corollary 1. Let G be a graph with n vertices. By Rayleigh's principle21, an easy lower bound for ^ is given by with equality if and only if S(G) has equal row sums. For example, the sum-connectivity matrix of a regular graph or a semiregular graph has equal row sums. Let G be a graph with n > 2 vertices. Then by Proposition 1 and the Perron-Frobenius theorem, with equality if and only if G is an empty graph or a 2-ver-tex complete graph. A classic result is that the number of distinct eigenvalues of (the adjacency matrix of) a connected graph of diameter d is at least d + 1 [Theorem 3.13 in Ref. 22]. By the straightforward modification of the argument there to the sum-connectivity matrix, we have similar result as follows. Lemma 2. Let G be a connected graph with diameter d. If S(G) has exactly k distinct eigenvalues, then k > d + 1. Recall that ^ - ^n is the spectral diameter of S = S(G). Consonni and Todeschini23 investigated the use of the spectral diameter of molecular matrices. Proposition 2. Let G be a graph with n > 2 vertices. ' d,+dj %dt + d} (4) with either equality if and only if G is an empty graph or G is a complete bipartite graph with possibly isolated vertices. Proof. From (2) we have and then Then implying the first inequality, and the second inequality follows from the Cauchy-Schwarz inequality. It is obvious that both inequalities in (4) are equalities if G is an empty graph. Suppose that either equality holds in (4) and G is non-empty. By discussion above and using (1), S(G) has exactly two nonzero eigenvalues ^ and i.e., S(G)2 has exactly two distinct eigenvalues (with multiplicity 2) and 0 (with multiplicity n - 2). Thus there is (precisely) one component, say H with k > 2 vertices of G, for which S(H)2 has exactly two distinct eigenvalues ^ (with multiplicity 2) and 0 (with multiplicity k -2), and if k < n, then all other components are isolated vertices. Suppose first that H is not a bipartite graph. There is only one connected non-bipartite graph, i.e., the complete graph on three vertices, for whic1h th1e eigenvalues of its sum-connectivity matrix are 1, - -,- -, contradicting condition that S(G) has exactly two nonzero eigenvalues ^ and -ur Thus k > 4. By the Perron-Frobenius theorem, S(H)2 is irreducible. By Lemma 1, S(H)2 = uuT + rIk for some positive column vector u and some r. Thus there is an orthogonal matrix U such that UT(uuT + rIk)U = diag (M2v 0, ..., 0, Let y = (yp ..., yk)T = UTu. Then yyT = diag (u1 - r, - r,..., - r, ^ - r). Note that the rank of yyTis at most one. Then r = 0, and thus ^ = 0, a contradiction. Thus H must be a bipartite graph, and by Lemma 2, the diameter of H is at most two, implying that H is a complete bipartite graph. It follows that G is a complete bipartite graph with possibly isolated vertices. Conversely, if G is a complete bipartite graph with possibly isolated vertices, then ^ = 0 for i = 2, ..., n - 1 and thus (4) is an equality. Let G be a graph with n > 2 vertices. By the arguments as in Corollaries 1 and 2, we have with the first equality if and only if G is an empty graph or G is a regular complete bipartite graph with possibly isolated vertices, and with the second equality if and only if G is a regular complete bipartite graph. 4. Properties of the Sum-Connectivity Energy Proposition 3. Let G be a graph with n vertices. Then (5) with equality if and only if G is an empty graph or a regular graph of degree one. Proof. By Cauchy-Schwarz inequality and using (2), we have W Suppose that equality holds in (5). Then ft1 = ft2\ = ... = \ftn\. If ft1 = 0, then G is an empty graph. Suppose that ft1 > 0. From (1), we have ftn < 0 and then S(G) has exactly two distinct eigenvalues, implying that for any component H of G, S(H) has exactly two distinct eigenvalues ftx and -pr By the Perron-Frobenius theorem, the multiplicity of ft1 as an eigenvalue of S(H) is one. Then ft1 -(\V(H)\ -1) ft1 = 0 i.e., \V(H)\ = 2 and thus G is a regular graph of degree one. Conversely, if G is an empty graph or a regular graph of degree one, then it is easily seen that all eigenvalues of S(G) have equal abosolute values and thus (5) is an equality. Let G be a graph with n vertices and m edges. Then by Proposition 3, SE(G) < Vwm with equality if and only if G is an empty graph or a regular graph of degree one. Let G be a graph with n vertices. Then by Proposition 3 and the proof of Corollaries 1 and 2, with the first equality if and only if G is an empty graph or a regular graph of degree one, and with the second equality if and only if G is a regular graph of degree one. Proposition 4. Let G be a regular graph with n vertices and degree r.Then Proof. Note that V2r S(G) = A(G). Then V2r ^ = ^ for i = 1, 2, ..., n. Now the result follows by the definitions of SE(G) and E(G). Proposition 5. Let G be a semiregular graph of degrees r > 1 and s > 1. Then lows. y[7+!sE(G) = £(G). Proof. Note that Vr + sS(G) = A(G). The result fol-Proposition 6. Let G be a graph with n vertices. Then (6) with equality if and only if G is an empty graph or G is a complete bipartite graph with ponssibly isolated vertices. Proof. From (1), we have X ft + 2 X ft ft, = 0, 1 4Y-- Then (6) follows. d- + d) It is obvious that (6) is an equality if G is an empty graph. Suppose that G is non-empty. From (1), we have ftl > 0, ftn < 0. It is easily seen that equality holds in (6) if and only if there are not both positive and negative terms in the sum or equivalently, ft ft < 0 for all i and j with 1 < i < j < n, 1.e., ftt = 0 for i = 2, ..., n - 1. By the proof of Proposition 2, equality holds in (6) if and only if G is a complete bipartite graph with possibly isolated vertices. Recall that the first Zagreb index of the graph G is defined24-28 as Ml(G) = Id2. Observe that14 M1(G) = X(d. + d). i=1 H Corollary 3. Let G be a graph with n vertices and m > 1 edges. Then SE(G)> 1m x/ÂW with equality if and only if G is a complete bipartite graph with possibly isolated vertices. Proof. By Cauchy-Schwarz inequality, with equality if and only if di + d- is a constant for all edges ij of G which is obviously satisfied by complete bipartite graphs with possibly isolated vertices. Then the result follows from Proposition 6. Corollary 4. Let G be a triangle-free graph with n vertices and m > 1 edges. Then SE(G) V n with equality if and only if G is a complete bipartite graph. Proof. From Ref. 27 and 28, we have M1(G) < nm with equality if and only if G is a complete bipartite graph. The result follows from Corollary 3. Let G be a tree with n vertices. By Corollary 4, with equality if and only if G is a star. 5. Concluding Remarks In this report, we study some properties of the eigenvalues of the sum-connectivity matrix and sum-connectivity energy of (molecular) graphs. We give a number of upper and lower bounds for the largest eigenvalue, the spectral diameter and the sum-connectivity energy using some other structural invariants, such as the number of vertices (atoms) and their degrees (valencies) of a graph (molecule), and characterize the extremal cases. The bounds of a descriptor are important information of a molecule (graph) in the sense that they establish the approximate range of the descriptor in terms of molecular structural parameters. 6. Acknowledgements This work was supported by the Guangdong Provincial Natural Science Foundation of China (Grant No. 8151063101000026) and by the Ministry of Science, Education and Sports of Croatia (Grant No. 098-17704952919). 7. References 1. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1971, 2nd printing. 2. N. Trinajsti}, Chemical Graph Theory, CRC, Boca Raton, FL, 1992, 2nd revised edition. 3. J.A. Rodriguez, Lin. Algebra Appl. 2005, 400, 339-344. 4. J.A. Rodriguez, J.M. Sigarreta, MATCH Commun. Math. Comput. Chem. 2005, 54, 403-413. 5. L. Hogben, Electronic J. Lin. Algebra 2005, 14, 12-31. 6. S.B. Bozkurt, A.D. Güngör, I. Gutman, A.S. Çevik, MATCH Commun. Math. Comput. Chem. 2010, 64, 239-250. 7. M. Randic, J. Am. Chem. Soc. 1975, 97, 6609-6615. 8. M. Randic, J. Mol. Graph. Model. 2001, 20, 19-35. 9. R. Todeschini, V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, 2000, pp. 84-90. 10. R. Todeschini, V. Consonni, Molecular Descriptors for Che-moinformatics, Wiley-VCH, Weinheim, 2009, pp. 161-172. 11. Ref. 9, pp. 283-286. 12. Ref. 10, pp. 478-487. 13. D. Janežic, A. Milicevic, S. Nikoli}, N. Trinajsti}, Graph Theoretical Matrices in Chemistry, Univ. Kragujevac, Kra-gujevac, 2007, pp. 6-13. 14. B. Zhou, N. Trinajsti}, J. Math. Chem. 2009, 46, 1252-1270. 15 B. Luci}, N. Trinajsti}, B. Zhou, Chem. Phys. Lett. 2009, 475, 146-148. 16. B. Luci}, S. Nikoli}, N. Trinajsti}, B. Zhou, S. Ivaniš Turk, Sum-connectivity index, in: I. Gutman, B. Furtula (Eds.), Novel Molecular Structure Descriptors - Theory and Applications I, Univ. Kragujevac, Kragujevac, 2010, pp. 101-136. 17. I. Gutman, O.E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, 1986, pp. 139-139. 18. D. Cao, V. Chvatal, A.J. Hoffman, A. Vince, Lin. Algebra Appl. 1997, 260, 215-222. 19 B. Zhou, N. Trinajsti}, J. Math. Chem. 2010, 47, 210-218. 20. B. Zhou, W. Luo, MATCH Commun. Math. Comput. Chem. 2009, 62, 155-162. 21. R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge Univ. Press, Cambridge, 1985. 22. D.M. Cvetkovi}, M. Doob, H. Sachs, Spectra of Graphs -Theory and Application, Barth, Heidelberg, 1995, 3rd edition. 23. V. Consonni, R. Todeschini, MATCH Commun. Math. Comput. Chem. 2008, 60, 3-14. 24. I. Gutman, B. Rušci}, N. Trinajsti}, C. F. Wilcox, Jr., J. Chem. Phys. 1975, 62, 3399-3405. 25. S. Nikoli}, G. Kovačevi}, A. Milicevi}, N. Trinajsti}, Croat. Chem. Acta 2003, 76, 113-124. 26. I. Gutman, K.C. Das, MATCH Commun. Math. Comput. Chem. 2004, 50, 83-92. 27. B. Zhou, MATCH Commun. Math. Comput. Chem. 2004, 52, 113-118. 28. B. Zhou, MATCH Commun. Math. Comput. Chem. 2007, 57, 591-596. Povzetek Ce je G (molekulski) graf z n vozlišči in je di stopnja i-tega vozlišča, potem je matrika vsot povezljivosti grafa G n x n matrika, katere element (i j) je enak 1/Vdi + d, če sta vozlišči i in j sosednji in 0, če nista sosednji. Energija vsot-pove-zljivosti grafa G je definirana kot vsota absolutnih vrednosti lastnih vrednosti matrike vsot-povezljivosti. Vpeljane so nekatere lastnosti, vključno z zgornjo in spodnjo mejo lastnih vrednosti matrike vsot-povezljivosti in energije vsot-povezljivosti, in okarakterizirani ekstremni primeri.