Bounds for the Kirchhoff index via majorization techniques

详细信息    查看全文

• 作者：Monica Bianchi (1)
  Alessandra Cornaro (1)
  José Luis Palacios (2)
  Anna Torriero (1)
  
• 关键词：Majorization ; Schur ; convex functions ; Graphs ; Kirchhoff index
• 刊名：Journal of Mathematical Chemistry
• 出版年：2013
• 出版时间：February 2013
• 年：2013
• 卷：51
• 期：2
• 页码：569-587
• 全文大小：228KB
• 参考文献：1. Bendito E., Carmona A., Encinas A.M., Gesto J.M.: A formula for the Kirchhoff index. Int. J. Quantum Chem. 108, 1200-206 (2008) CrossRef
  2. Bianchi M., Torriero A.: Some localization theorems using a majorization technique. J. Inequal. Appl. 5, 433-46 (2000)
  3. M. Bianchi, A. Cornaro, A. Torriero, Majorization under constraints and bounds of the second Zagreb index, Contributi di Ricerca in Econometria e Matematica 115, Università Cattolica del Sacro Cuore, Milano, arXiv:1105.1888v1 [math.CO] (2011)
  4. M. Bianchi, A. Cornaro, A. Torriero, A Majorization Method for localizing graph topological indices, Contributi di Ricerca in Econometria e Matematica 116, Università Cattolica del Sacro Cuore, Milano, arXiv:1105.3631v1 [math.CO] (2011)
  5. Chen H., Zhang F.: Resistance distance and the normalized Laplacian spectrum. Discret. Appl. Math. 155, 654-61 (2007) CrossRef
  6. J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian. Problems in analysis (Papers dedicated to Salomon Bochner) (Princeton University Press, Princeton, 1969), pp. 195-99
  7. Gao X., Luo Y., Liu W.: Resistance distances and the Kirchhoff index in Cayley graphs. Discret. Appl. Math. 159, 2050-057 (2011) CrossRef
  8. Grassi R., Stefani S., Torriero A.: Extremal properties of graphs and Eigencentrality in trees with a given degree sequence. J. Math. Sociol. 34(2), 115-35 (2010) CrossRef
  9. Grone R., Merris R.: The Laplacian spectrum of a graph II. SIAM J. Discret. Math. 7, 221-29 (1994) CrossRef
  10. Gutman I., Mohar B.: The Quasi-Wiener and the Kirchhoff indices coincide. J. Chem. Inf. Comput. Sci. 36, 982-85 (1996) CrossRef
  11. Klein D.J.: Prolegomenon on partial orderings in chemistry. MATCH Commun. Math. Chem. 42, 7-1 (2000)
  12. Klein D.J., Randi? M.: Resistance distance. J. Math. Chem. 12, 81 (1993) CrossRef
  13. Klein D.J., Babic D.: Partial orderings in chemistry. J. Chem. Inf. Comp. Sci 37, 656-71 (1997) CrossRef
  14. Li X., Shi Y.: A survey on the Randi? index. MATCH Commun. Math. Comput. Chem. 59, 127-56 (2008)
  15. Lu M., Zhang L., Tian F.: Lower bounds of the Laplacian spectrum of graphs based on diameter. Linear Algebra Appl. 420, 400-06 (2007) CrossRef
  16. Marshall A.W., Olkin I.: Inequalities: Theory of Majorization and Its Applications. Academic Press, London (1979)
  17. Palacios J.L.: Closed form formulas for Kirchhoff index. Int. J. Quantum Chem. 81, 135-40 (2001) CrossRef
  18. Palacios J.L., Renom J.M.: Broder and Karlin’s formula for hitting times and the Kirchhoff index. Int. J. Quantum Chem. 111, 35-9 (2011) CrossRef
  19. Palacios J.L., Renom J.M.: Another look at the degree-Kirchhoff index. Int. J. Quantum Chem. 111, 3453-455 (2011) CrossRef
  20. Palacios J.L., Renom J.M.: Bounds for the Kirchhoff index of regular graphs via the spectra of their random walks. Int. J. Quantum Chem. 110, 1637-641 (2010)
  21. Diaconis P., Stroock D.: Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1, 36-1 (1991) CrossRef
  22. Randi? M.: On characterization of molecular branching. J. Am. Chem. Soc. 97, 6609-615 (1975) CrossRef
  23. Ruch E., Gutman I.: The branching extent of graphs. J. Comb. Inf. Syst. Sci. 4, 285-95 (1979)
  24. Tarazaga P.: More estimate for eigenvalues and singular values. Linear Algebra Appl. 149, 97-10 (1991) CrossRef
  25. Wang H., Hua H., Wang D.: Cacti with minimum, second-minimum, and third-minimum Kirchhoff indices. Math. Commun. 15, 347-58 (2010)
  26. R.J. Wilson, Introduction to Graph Theory (Addison Wesley, Boston, 1996)
  27. Wolkowicz H., Styan G.P.H.: Bounds for eigenvalues using trace. Linear Algebra Appl. 29, 471-06 (1980) CrossRef
  28. Yang Y., Zhang H.: Kirchhoff index of linear hexagonal chains. Int. J. Quantum Chem. 108, 503-12 (2008) CrossRef
  29. Yang Y., Zhang H., Klein D.: New Nordhaus-Gaddum-type results for the Kirchhoff index. J. Math. Chem. 49, 1-2 (2011) CrossRef
  30. Zhou B., Trinajstic N.: A note on Kirchhoff index. Chem. Phys. Lett. 455, 120-23 (2008) CrossRef
  31. Zhu H.Y., Klein D.J., Lukovits I.: Extensions of the Wiener number. J. Chem. Inf. Comput. Sci 36, 420-28 (1996) CrossRef
  
• 作者单位：Monica Bianchi (1)
  Alessandra Cornaro (1)
  José Luis Palacios (2)
  Anna Torriero (1)
  
  1. Department of Mathematics and Econometrics, Catholic University, Milan, Italy
  2. Department of Scientific Computing and Statistics, Simón Bolívar University, Caracas, Venezuela
  
• ISSN：1572-8897

文摘

Using a majorization technique that identifies the maximal and minimal vectors of a variety of subsets of ${\mathbb{R}^{n}}$ , we find upper and lower bounds for the Kirchhoff index K(G) of an arbitrary simple connected graph G that improve those existing in the literature. Specifically we show that $$K(G) \geq \frac{n}{d_{1}} \left[ \frac{1}{1+\frac{\sigma}{\sqrt{n-1}}} + \frac{(n-2)^{2}}{n-1-\frac{\sigma}{\sqrt{n-1}}}\right] ,$$ where d 1 is the largest degree among all vertices in G, $$\sigma ^{2} = \frac{2}{n} \sum_{(i, j) \in E} \frac{1}{d_{i}d_{j}} = \left( \frac{2}{n}\right) R_{-1}(G),$$ and R ?(G) is the general Randi? index of G for ${\alpha =-1}$ . Also we show that $$K(G) \leq \frac{n}{d_{n}}\left( \frac{n-k-2}{1-\lambda _{2}}+\frac{k}{2}+\frac{1}{\theta}\right) ,$$ where d n is the smallest degree, ${\lambda _{2}}$ is the second eigenvalue of the transition probability of the random walk on G, $$k = \left \lfloor \frac{\lambda _{2} \left( n-1\right) +1}{\lambda _{2}+1}\right\rfloor {\rm and}\quad\theta = \lambda _{2} \left( n-k-2\right) -k+2.$$