Extremal polygonal cacti for Wiener index and Kirchhoff index

Document Type : Research Paper

Authors

Hunan Normal University

Abstract

For a connected graph G, the Wiener index W(G) of G is the sum of the distances of all pairs of vertices, the Kirchhoff index Kf(G) of G is the sum of the resistance distances of all pairs of vertices. A k-polygonal cactus is a connected graph in which the length of every cycle is k and any two cycles have at most one common vertex. In this paper, we give the maximum and minimum values of the Wiener index and the Kirchhoff index for all k-polygonal cacti with n cycles and determine the corresponding extremal graphs, generalize results of spiro hexagonal chains with n hexagons.

Keywords


  1. D. Babić, D. J. Klein, I. Lukovits, S. Nikolić, N. Trinajstić, Resistance-distance matrix: A computational algorithm and its application, Int. J. Quantum Chem. 90 (2002) 166−176.
  2. H. Deng, On the minimum Kirchhoff index of graphs with a given number of cut-edges, MATCH Commun.Math. Comput. Chem. 63 (2010) 171−180.
  3. H. Deng, Wiener indices of spiro and polyphenyl hexagonal chains, Math. Comput. Model. 55 (2012) 634−644.
  4. H. Deng, Z. Tang, Kirchhoff indices of spiro and polyphenyl hexagonal chains, Util. Math. 95 (2014) 113−128.
  5. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211−249.
  6. A. Dobrynin, I. Gutman, S. Klavˇ zar, P. Zigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002) 247−294.
  7. Q. Guo, H. Deng, D. Chen, The extremal Kirchhoff index of a class of unicyclic graphs, MATCH Commun. Math. Comput. Chem. 61 (2009) 713−722.
  8. I. Gutman, S. Li, W. Wei, Cacti with n vertices and t cycles having extremal Wiener index, Discrete Appl. Math. 232 (2017) 189−200.
  9. G. Huang, M. Kuang, H. Deng, The expected values of Kirchhoff indices in the random polyphenyl and spiro chains, ARS Math. Contem. 9 (2) (2015) 207−217.
  10. D. J. Klein, Resistance-distance sum rules, Croat. Chem. Acta 75 (2002) 633−649.
  11. D. J. Klein, M. Randi´ c, Resistance distance, J. Math. Chem. 12 (1993) 81−95.
  12. J. Palacios, Resistance distance in graphs and random walks, Int. J. Quantum Chem. 81 (2001) 29−33.
  13. J. Palacios, Closed-form formulas for Kirchhoff index, Int. J. Quantum Chem. 81 (2001) 135−140.
  14. O. E. Polansky, D. Bonchev, The Wiener number of graphs I: general theory and changes due to graph operations, MATCH Commun. Math. Comput. Chem. 21 (1986) 133−186.
  15. O. E. Polansky, D. Bonchev, Theory of the Wiener number of graphs II: Transfer graphs and some of their metric properties, MATCH Commun. Math. Comput. Chem. 25 (1990) 3−39.
  16. Z. Tang, H. Deng, The (n,n)-graphs with the first three extremal Wiener indices, J. Math. Chem. 43 (2008) 60−74.
  17. H. Wang, H. Hua, D. Wang, Catic with minimum, second-minimum, and third- minimum Kirchhoff indices, Math. Commun. 15 (2) (2010) 347−358.
  18. H. Wiener, Structural determination of paraffin boiling point, J. Am. Chem. Soc. 69 (1947) 17−20.12
  19. Y. Yang, X. Jiang, Unicyclic graphs with extremal Kirchhoff index, MATCH Commun. Math. Comput. Chem. 60 (2008) 107−120.
  20. Y. Yang, H. Zhang, Kirchhoff index of linear hexagonal chains, Int. J. Quantum Chem. 108 (2008) 503−512.
  21.  J. Ye, M. Liu, Y. Yao, K. Ch. Das, Extramal polygonal cacti for bond incident degree indices, Discrete Applied Math. 257 (2019) 289−298.
  22. W. Zhang, H. Deng, The second maximal and minimal Kirchhoff indices of unicyclic graphs, MATCH Commun. Math. Comput. Chem. 69 (2009) 683−695.
  23. H. Zhang, Y. Yang, Resistance distance and Kirchhoff index in circulant graphs, Int. J. Quantum Chem. 107 (2007) 330−339.