Combinatorial explanation of the weighted Kirchhoff index of graphs

Abstract

Let $G$ be a connected graph with vertex set $V(G)=\{v_1,v_2,\dots ,v_n\}$, and let $\omega :V(G)\to {\mathbb{R}}^{+}$ be a positive vertex-weight function satisfying $\omega (v_i)=x_i$ for each $v_i\in V(G)$. The weighted Kirchhoff index of $G$ is defined by $K(G;x_1,x_2,\dots ,x_n)={\sum }_{1\le i<j\le n}{x}_i{x}_j{r}_G(v_i,v_j)$, where $r_G(v_i,v_j)$ denotes the resistance distance between $v_i$ and $v_j$. In this paper, we give a combinatorial interpretation of the weighted Kirchhoff index of an arbitrary connected graph. More precisely, we express $K(G;x_1,x_2,\dots ,x_n)$ in terms of the sums of weights of matchings in an appropriately weighted subdivision graph of $G$, and in the subgraphs obtained from this weighted subdivision graph by deleting the subdivision graphs corresponding to \(2\)-regular subgraphs of $G$. This gives an affirmative answer to a question posed by Li, Li and Yan [Discrete Math. 345 (2022) 113109] concerning a combinatorial explanation of the weighted Kirchhoff index of a general graph by using matchings in weighted subdivision graphs and their subgraphs. As special cases, our formula recovers the known formulas for the weighted Kirchhoff index of trees and unicyclic graphs, as well as the known formula for the ordinary Kirchhoff index of an arbitrary connected graph.

15 pages, 1 figure