Abstract | ||
---|---|---|
The Kirchhoff index <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"gcom_a_1073722_ilm0001.gif\"/</inline-formula> 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 <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"gcom_a_1073722_ilm0002.gif\"/</inline-formula> with <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"gcom_a_1073722_ilm0003.gif\"/</inline-formula> 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 <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"gcom_a_1073722_ilm0004.gif\"/</inline-formula>. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1080/00207160.2015.1073722 | Int. J. Comput. Math. |
Keywords | Field | DocType |
graph, distance (in graph), Kirchhoff index, Laplacian spectrum, ordering | Graph theory,Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Nowhere-zero flow,Cograph,Pathwidth,1-planar graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
93 | 10 | 0020-7160 |
Citations | PageRank | References |
2 | 0.40 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kexiang Xu | 1 | 72 | 11.43 |
Kinkar Ch. Das | 2 | 208 | 30.32 |
Xiao-Dong Zhang | 3 | 97 | 19.87 |