Computing the Additive Degree-Kirchhoff Index with the Laplacian Matrix

Document Type : Research Paper

Author

The University of New Mexico, Albuquerque, NM 87131, USA

Abstract

For any simple connected undirected graph, it is well known that the Kirchhoff and multiplicative degree-Kirchhoff indices can be computed using the Laplacian matrix. We show that the same is true for the additive degree-Kirchhoff index and give a compact Matlab program that computes all three Kirchhoffian indices with the Laplacian matrix as the only input.

Keywords

Main Subjects


1. D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs,
unfinished monograph, 2014, available at
http://www.stat.berkeley.edu/~aldous/RWG/book.html.
2. R. B. Bapat, I. Gutman and W. Xiao, A simple method for computing the effective
resistance, Z. Naturforsch. A 58 (2003) 494–498.
3. H. Chen and F. Zhang, Resistance distance and the normalized Laplacian
spectrum, Discrete Appl. Math. 155 (2007) 654–661.
4. H. Coen, A Course in Computational Algebraic Number Theory, Graduate texts in
Mathematics, 138, Springer–Verlag, 1993.
5. P. Courrieu, Fast computation of Moore–Penrose inverse matrices, Neural Inform.
Process. Lett. Rev 8 (2005) 25–29.
6. I. Gutman, L. Feng and G. Yu, Degree resistance distance of unicyclic graphs,
Trans. Comb. 1 (2012) 27–40.
7. I. Gutman and B. Mohar, The quasi–Wiener and the Kirchhoff indices coincide, J.
Chem. Inf. Comput. Sci. 36 (1996) 982–985.
8. I. Gutman, D. Vidović and B. Furtula, Chemical applications of the Laplacian
spectrum VII. Studies of the Wiener and Kirchhoff indices, Indian J. Chem. 42A
(2003) 1272–1278.
9. S. Huang, J. Zhou and C. Bu, Some results on Kirchhoff index and degree–
Kirchhoff index, MATCH Commun. Math. Comput. Chem. 75 (2016) 207–222.
10. D. J. Klein and M. Randi'c, Resistance distance, J. Math. Chem. 12 (1993) 81–95.
11. Matlab. The Mathworks. http://www.mathworks.com/products/matlab/
12. I. Milovanović, I. Gutman and E. Milovanović, On Kirchhoff and degree Kirchhoff
indices, Filomat 29 (2015) 1869–1877.
13. A. Mostowski and M. Stark, Introduction to Higher Algebra, The Macmillan
Company, New York, 1964.
14. J. L. Palacios, Resistance distance in graphs and random walks, Int. J. Quantum
Chem 81 (2001) 29–33.
15. J. L. Palacios and J. M. Renom, Sum rules for hitting times of Markov chains,
Linear Algebra Appl. 433 (2010) 491–497.
16. J. L. Palacios and J. M. Renom, Broder and Karlin's formula for hitting times and
the Kirchhoff index, Int. J. Quantum Chem. 111 (2011) 35–39.
17. J. L. Palacios, Some interplay of the three Kirchhoffian indices, MATCH Commun.
Math. Comput. Chem. 75 (2016) 199–206.
18. J. L. Palacios, Some more interplay of the three Kirchhoffian indices, Linear
Algebra Appl. 511 (2016) 421–429.
19. M. Somodi, On the Ihara zeta function and resistance distance-based indices,
Linear Algebra Appl. 513 (2017) 201–209
20. Y. Yang and D. J. Klein, A note on the Kirchhoff and additive degree–Kirchhoff
indices of graphs, Z. Naturforsch. A 70 (2015) 459–463.
21. H. Y. Zhu, D. J. Klein and I. Lukovits, Extensions of the Wiener number, J. Chem.
Inf. Comput. Sci. 36 (1996) 420–428.