Ordering connected graphs by their Kirchhoff indices

Abstract

The Kirchhoff index $\mathrm{Kf}\left(G\right)$ of a graph G is the sum of resistance distances between all unordered pairs of vertices, which was introduced by Klein and Randić. In this paper, we characterize all extremal graphs with respect to Kirchhoff index among all graphs obtained by deleting p edges from a complete graph $K_n$ with $p\le \lfloor n/2\rfloor$ and obtain a sharp upper bound on the Kirchhoff index of these graphs. In addition, all the graphs with the first to ninth maximal Kirchhoff indices are completely determined among all connected graphs of order $n>27$.

Keywords:

• graph
• distance (in graph)
• Kirchhoff index
• Laplacian spectrum
• ordering

AMS Subject Classifications (2010):

• 05C50
• 05C12
• 05C35

Acknowledgments

The authors are much grateful to two anonymous referees for their valuable comments on our paper, which have considerably improved the presentation of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The first author is supported by NNSF of China [No. 11201227], China Postdoctoral Science Foundation [2013M530253] and Natural Science Foundation of Jiangsu Province [BK20131357], the second author was supported by National Research Foundation funded by the Korean government with the grant No. 2013R1A1A2009341, the third author is supported by NNSF of China [No. 11271256].