Isoperimetric Edge Connectivity of Line Graphs and Path Graphs

Abstract

The $k$-th isoperimetric edge connectivity ${\gamma }_k(G)=min\{|[U,\overline{U}]|:U\subset V(G),|U|\ge k\}$. A graph $G$ with ${\gamma }_k(G)={\beta }_k(G)$ is said to be ${\gamma }_k$-optimal, where ${\beta }_k(G)=min\{|[U,\overline{U}]|:U\subset V(G),|U|=k\}$. Let $G$ be a connected $d$-regular graph. Write $L(G)$ and $P_2(G)$ the line graph and the 2-path graph of $G$, respectively. In this paper, we derive some sufficient conditions for $L(G)$ and $P_2(G)$ to be ${\gamma }_k$-optimal.