Ordering connected graphs by their Kirchhoff indices

DOI10.1080/00207160.2015.1073722zbMATH Open1354.05084arXiv1602.07039OpenAlexW3104383933MaRDI QIDQ2957754FDOQ2957754

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)

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

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

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

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)

Cites Work

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

Cited In (19)

• On the normalized Laplacian spectral radii of a graph and its line graph
• Title not available (Why is that?)
• 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
• Block graphs of maximum Kirchhoff index
• On the ordering of the Kirchhoff indices of the complements of trees and unicyclic graphs
• 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
• Title not available (Why is that?)
• The minimal Kirchhoff index of graphs with a given number of cut vertices
• Ordering \(Q\)-indices of graphs: given size and circumference

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)