Ordering connected graphs by their Kirchhoff indices

Kexiang Xu; Kinkar Ch Das; Xiao Dong Zhang

doi:10.1080/00207160.2015.1073722

Ordering connected graphs by their Kirchhoff indices

Kexiang Xu, Kinkar Ch Das, Xiao Dong Zhang

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

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 K_n with p ≤ |n/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.

Original language	English
Pages (from-to)	1741-1755
Number of pages	15
Journal	International Journal of Computer Mathematics
Volume	93
Issue number	10
DOIs	https://doi.org/10.1080/00207160.2015.1073722
State	Published - 2 Oct 2016

Keywords

distance (in graph)
graph
Kirchhoff index
Laplacian spectrum
ordering

Access to Document

10.1080/00207160.2015.1073722

Cite this

@article{1af8aedc84784ba08c1e013d51ba01fc,

title = "Ordering connected graphs by their Kirchhoff indices",

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{\'c}. 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 p ≤ |n/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.",

keywords = "distance (in graph), graph, Kirchhoff index, Laplacian spectrum, ordering",

author = "Kexiang Xu and Das, \{Kinkar Ch\} and Zhang, \{Xiao Dong\}",

note = "Publisher Copyright: {\textcopyright} 2015 Taylor \& Francis.",

year = "2016",

month = oct,

day = "2",

doi = "10.1080/00207160.2015.1073722",

language = "English",

volume = "93",

pages = "1741--1755",

journal = "International Journal of Computer Mathematics",

issn = "0020-7160",

publisher = "Taylor and Francis Ltd.",

number = "10",

}

TY - JOUR

T1 - Ordering connected graphs by their Kirchhoff indices

AU - Xu, Kexiang

AU - Das, Kinkar Ch

AU - Zhang, Xiao Dong

PY - 2016/10/2

Y1 - 2016/10/2

N2 - 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 p ≤ |n/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.

AB - 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 p ≤ |n/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.

KW - distance (in graph)

KW - graph

KW - Kirchhoff index

KW - Laplacian spectrum

KW - ordering

UR - https://www.scopus.com/pages/publications/84939189032

U2 - 10.1080/00207160.2015.1073722

DO - 10.1080/00207160.2015.1073722

M3 - Article

AN - SCOPUS:84939189032

SN - 0020-7160

VL - 93

SP - 1741

EP - 1755

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 10

ER -

Ordering connected graphs by their Kirchhoff indices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this