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

From MaRDI portal





scientific article
Language Label Description Also known as
English
Path 3-(edge-)connectivity of lexicographic product graphs
scientific article

    Statements

    Path 3-(edge-)connectivity of lexicographic product graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    5 June 2020
    0 references
    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\).
    0 references
    0 references
    connectivity
    0 references
    \(S\)-Steiner paths
    0 references
    path 3-connectivity
    0 references
    path 3-edge-connectivity
    0 references
    lexicographic product
    0 references

    Identifiers