On the Path Edge-Connectivity of Graphs

Abstract

Dirac showed that in a \((k-1)\)-connected graph there is a path through each \(k\) vertices. The path \(k\)-connectivity \(\pi_k(G)\) of a graph \(G\), which is a generalization of Dirac’s notion, was introduced by Hager in 1986. Recently, Mao introduced the concept of path \(k\)-edge-connectivity \(\omega_k(G)\) of a graph \(G\). Denote by \(G \circ H\) the lexicographic product of two graphs \(G\) and \(H\). In this paper, we prove that \(\omega_4(G \circ H) \geq \omega_4(G) |V(H)|\) for any two graphs \(G\) and \(H\). Moreover, the bound is sharp.