Path 3-(edge-)connectivity of lexicographic product graphs (Q2185739)

This paper studies path 3-connectivity \(\pi_3\) and path 3-edge-connectivity \(\omega_3\) of lexicographic product graphs. If \(G\) is a 2-connected graph and \(H\) is a graph with \(n\) vertices, it is shown that \(\pi_3(G\circ H)\ge n\). Moreover, \(\omega_3(G\circ H)\ge3\lfloor n/2\rfloor\) if \(n\) is even while \(\omega_3(G\circ H)\ge3\lfloor n/2\rfloor+1\) if \(n\) is odd. If in addition \(H\) is connected, then \(\omega_3(G\circ H)\ge3\lfloor n/2\rfloor\) if \(n\) is even while \(\omega_3(G\circ H)\ge3\lfloor n/2\rfloor+2\) if \(n\) is odd. If \(G\) is a connected graph with minimum degree \(\delta\) and \(H\) is a cycle, then \(\omega_3(G\circ H)\le(3/4)n\delta+3/2\).