On the Path-Connectivity of Lexicographic Product Graphs

Abstract

The $k$-path-connectivity ${\pi }_k(G)$ of a graph $G$ was introduced by Hager in $1986$. Recently, Mao investigated the $3$-path-connectivity of lexicographic product graphs. Denote by $G\circ H$ the lexicographic product of two graphs $G$ and $H$. In this paper, we prove that ${\pi }_4(G\circ H)\ge \lfloor \frac{|V(H)|-2}{3}\rfloor$ for any two connected graphs $G$ and $H$. Moreover, the bound is sharp. We also derive an upper bound of ${\pi }_4(G\circ H)$, that is, ${\pi }_4(G\circ H)\le 2{\pi }_4(G)|V(H)|$.