Edge-connectivity and super edge-connectivity of \(P_{2}\)-path graphs
For a graph \(G\), the \(P_2\)-path graph, \(P_2(G)\), has for vertices the set of all paths of length 2 in \(G\). Two vertices are adjacent in \(P_2(G)\) whenever the union of the corresponding paths is a path or a cycle of length 3. In the paper, there are lower bounds for the edge-connectivity of \(P_2\)-path graphs of connected graphs. Further, conditions on a graph \(G\) which force maximum edge-connectivity of \(P_2(G)\) are presented. Finally, for maximum edge-connected \(P_2\)-path graphs the authors consider nontrivial edge cuts.
scientific article; zbMATH DE number 1967259
scientific article