Ordering connected graphs by their Kirchhoff indices

DOI10.1080/00207160.2015.1073722MaRDI QIDQ2957754zbMATH OpenOpenAlexFDO

Authors Kexiang Xu, Kinkar Ch. Das, Xiao-Dong Zhang

Publication date 27 January 2017

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.07039

zbMATH Keywords

graphdistanceorderingKirchhoff indexLaplacian spectrum

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

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 characterized all extremal graphs with Kirchhoff index among all graphs obtained by deleting $p$ edges from a complete graph $K_n$ with $pleqlfloorfracn2floor$ and obtained 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$.

Recommendations

• On the minimum Kirchhoff index of graphs with given number of cut-edges
• On the ordering of the Kirchhoff indices of the complements of trees and unicyclic graphs
• The minimal Kirchhoff index of graphs with a given number of cut vertices
• Block graphs of maximum Kirchhoff index
• Some bounds for the Kirchhoff index of graphs

Cites work

• scientific article; zbMATH DE number 44688 (Why is no real title available?)
• A certain polynomial of a graph and graphs with an extremal number of trees
• A recursion formula for resistance distances and its applications
• An improved upper bound for Laplacian graph eigenvalues
• Asymptotic Laplacian-energy-like invariant of lattices
• Comparison between Kirchhoff index and the Laplacian-energy-like invariant
• Comparison theorems on resistance distances and Kirchhoff indices of S,T-isomers
• Graph theory with applications
• Laplacian matrices of graphs: A survey
• On the Kirchhoff index of graphs with diameter 2
• Resistance distance-based graph invariants of subdivisions and triangulations of graphs
• The Kirchhoff index of subdivisions of graphs
• The Laplacian Spectrum of a Graph
• The number of spanning trees of a graph with given matching number

Cited in

(19)

• The minimal Kirchhoff index of graphs with a given number of cut vertices
• Ordering \(Q\)-indices of graphs: given size and circumference
• On the normalized Laplacian spectral radii of a graph and its line graph
• scientific article; zbMATH DE number 7523847 (Why is no real title available?)
• Maximum reciprocal degree resistance distance index of unicyclic graphs
• Maximum resistance-Harary index of cacti
• Ordering connected graphs having small degree distances
• Solution to a conjecture on a Nordhaus-Gaddum type result for the Kirchhoff index
• Resistance distances in corona and neighborhood corona networks based on Laplacian generalized inverse approach
• On the ordering of the Kirchhoff indices of the complements of trees and unicyclic graphs
• Block graphs of maximum Kirchhoff index
• On the Kirchhoff index of graphs with diameter 2
• The upper bound for Kirchhoff index of \(p\)-partite graph
• On the minimum Kirchhoff index of graphs with given number of cut-edges
• Comparison of the Wiener and Kirchhoff indices of random pentachains
• Ordering graphs with small index and its application
• An Efficient Method for Indexing All Topological Orders of a Directed Graph
• Ordering signed graphs with large index
• scientific article; zbMATH DE number 5914876 (Why is no real title available?)

This page was built for publication: Ordering connected graphs by their Kirchhoff indices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957754)