Edge-connectivity in \(P_k\)-path graphs (Q1887639)

Path graphs were defined as a natural generalization of line graphs. The vertex set of the \(k\)-path graph \(P_{k}(G)\) is the set of all paths of length \( k\) of \(G\). Two vertices of \(P_{k}(G)\) are joined by an edge if and only if the intersection of the corresponding paths forms a path of length \(k-1\) in \(G\), and their union forms either a cycle, or a path of length \(k+1\). The authors study the problem of edge-connectivity of path-graphs for arbitrary values of \(k\) and also for the special case \(k=2\). The case \(k=1\) corresponds to line graphs. The edge-connectivity of path-graph-\(P_{k}(G)\) can be estimated in terms of minimal degree of graph \(G\) and the edge-connectivity of \(G\). The edge-connectivity, \(\lambda (G)\), of graph \(G\) is the minimum cardinality of an edge cut of \(G\). In the paper is proved that if the minimal degree \(\delta (G)\geq 2\), then \(\lambda (P_{2}(G))\) \(\geq \delta (G)-1\). Moreover if \( \lambda (G)\geq 2\), then \(\lambda (P_{2}(G))\) \(\geq 2\delta (G)-2\). For graphs without short cycles, it means with girth at least \(k+1,\) it is proved that if \(k>2\) and \(\delta (G)\geq 2\) then \(\lambda (P_k(G))\) \(\geq \delta (G)-1.\) Moreover if \(\delta (G)\geq 3\) and girth \(g(G)\geq k+1\), then \(\lambda (P_k(G))\) \(\geq 2\delta (G)-2\). When \(G\) is a regular graph, results are best possible, it means \(\lambda (P_k(G))\) \(=2\delta (G)-2\).