Resistance distance in directed cactus graphs

Main Article Content

R. Balaji
R.B. Bapat
Shivani Goel

Abstract

Let $G=(V,E)$ be a strongly connected and balanced digraph with vertex set $V=\{1,\dotsc,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}^{\dagger}+l_{jj}^{\dagger}-2l_{ij}^{\dagger}$, where $l_{pq}^{\dagger}$ is the $(p,q)^{\rm 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} \leq d_{ij}$. However, no proof for this inequality is known. In this paper, it is shown that this inequality holds for all directed cactus graphs.

Article Details

Section
Article