On the minimum Kirchhoff index of graphs with a given vertex k-partiteness and edge k-partiteness

摘要

The Kirchhoff index of a connected graph is the sum of the resistance distance between all unordered pairs of vertices and may also be expressed by its Laplacian eigenvalues. The vertex (resp. edge) k-partiteness of a graph G with n vertices is the minimum number of vertices (resp. edges) whose deletion from G yields a k-partite graph. In this paper, we determine the minimum Kirchhoff index of graphs with a given vertex k-partiteness and the minimum Kirchhoff index of graphs with a given edge bipartiteness, when the given edge bipartiteness is no more than n4.