Path 3-(edge-)connectivity of lexicographic product graphs (Q2185739)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Path 3-(edge-)connectivity of lexicographic product graphs |
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
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
connectivity
0 references
\(S\)-Steiner paths
0 references
path 3-connectivity
0 references
path 3-edge-connectivity
0 references
lexicographic product
0 references