Minimizing Kirchhoff index among graphs with a given vertex bipartiteness

The resistance distance between any two vertices of a graph G is defined as the effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index Kf(G) is the sum of the resistance distances between all the pairs of vertices in G. The vertex bipartiteness vb of...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2016-12, Vol.291, p.84-88
Main Authors: Liu, Jia-Bao, Pan, Xiang-Feng
Format: Article
Language:English
Subjects:
Generalized join
Kirchhoff index
Laplacian eigenvalues
Resistance distance
Vertex bipartiteness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The resistance distance between any two vertices of a graph G is defined as the effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index Kf(G) is the sum of the resistance distances between all the pairs of vertices in G. The vertex bipartiteness vb of a graph G is the minimum number of vertices whose deletion from G results in a bipartite graph. In this paper, we characterize the graph having the minimum Kf(G) values among graphs with a fixed number n of vertices and fixed vertex bipartiteness, 1≤vb≤n−3.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2016.06.017