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| \geq 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.