Resistance distance in directed cactus graphs

Abstract

Let $G=(V,E)$ be a strongly connected and balanced digraph with vertex set $V=\{1,\dots ,n\}$. The classical distance $d_{ij}$ between any two vertices $i$ and $j$ in $G$ is the minimum length of all the directed paths joining $i$ and $j$. The resistance distance (or, simply the resistance) between any two vertices $i$ and $j$ in $V$ is defined by $r_{ij}:=l_{ii}^{†}+l_{jj}^{†}-2l_{ij}^{†}$, where $l_{pq}^{†}$ is the $(p,q{)}^{\mathrm{th}}$ entry of the Moore-Penrose inverse of $L$ which is the Laplacian matrix of $G$. In practice, the resistance $r_{ij}$ is more significant than the classical distance. One reason for this is, numerical examples show that the resistance distance between $i$ and $j$ is always less than or equal to the classical distance, i.e. $r_{ij}\le d_{ij}$. However, no proof for this inequality is known. In this paper, we show that this inequality holds for all directed cactus graphs.