New Nordhaus-Gaddum-type results for the Kirchhoff index Academic Article uri icon

abstract

  • Let G be a connected graph. The resistance distance between any two vertices of G is defined as the net effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index is the sum of resistance distances between all pairs of vertices in G. Zhou and Trinajstić (Chem Phys Lett 455(1-3):120-123, 2008) obtained a Nordhaus-Gaddum-type result for the Kirchhoff index by obtaining lower and upper bounds for the sum of the Kirchhoff index of a graph and its complement. In this paper, by making use of the Cauchy-Schwarz inequality, spectral graph theory and Foster's formula, we give better lower and upper bounds. In particular, the lower bound turns out to be tight. Furthermore, we establish lower and upper bounds on the product of the Kirchhoff index of a graph and its complement. © 2011 Springer Science+Business Media, LLC.

published proceedings

  • JOURNAL OF MATHEMATICAL CHEMISTRY

author list (cited authors)

  • Yang, Y., Zhang, H., & Klein, D. J.

citation count

  • 13

complete list of authors

  • Yang, Yujun||Zhang, Heping||Klein, Douglas J

publication date

  • May 2011