126
Views
8
CrossRef citations to date
0
Altmetric
Original Articles

Ordering connected graphs by their Kirchhoff indices

, &
Pages 1741-1755 | Received 20 May 2015, Accepted 11 Jul 2015, Published online: 10 Aug 2015
 

Abstract

The Kirchhoff index Kf(G) 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 Kn with pn/2 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.

AMS Subject Classifications (2010):

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].

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.