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

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.

authors

• Klein, Douglas

published proceedings

• JOURNAL OF MATHEMATICAL CHEMISTRY

author list (cited authors)

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

citation count

• 14

complete list of authors

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

publication date

• September 2011

publisher

• Springer Nature  Publisher

published in

• Journal of Mathematical Chemistry  Journal

keywords

• Kirchhoff Index
• Nordhaus-gaddum-type Result
• Resistance Distance

Digital Object Identifier (DOI)

• 10.1007/s10910-011-9845-0

start page

• 1587

end page

• 1598

volume

• 49

issue

• 8

URL

• http://dx.doi.org/10.1007/s10910-011-9845-0