Bounds for the Kirchhoff Index of Bipartite Graphs

Abstract EN

A (m,n)-bipartite graph is a bipartite graph such that one bipartition has m vertices and the other bipartition has n vertices.

The tree dumbbell D(n,a,b) consists of the path Pn−a−b together with a independent vertices adjacent to one pendent vertex of Pn−a−b and b independent vertices adjacent to the other pendent vertex of Pn−a−b.

In this paper, firstly, we show that, among (m,n)-bipartite graphs (m≤n), the complete bipartite graph Km,n has minimal Kirchhoff index and the tree dumbbell D(m+n,⌊n−(m+1)/2⌋,⌈n−(m+1)/2⌉) has maximal Kirchhoff index.

Then, we show that, among all bipartite graphs of order l, the complete bipartite graph K⌊l/2⌋,l−⌊l/2⌋ has minimal Kirchhoff index and the path Pl has maximal Kirchhoff index, respectively.

Finally, bonds for the Kirchhoff index of (m,n)-bipartite graphs and bipartite graphs of order l are obtained by computing the Kirchhoff index of these extremal graphs.