Distribution of contractible edges in k-connected graphs
Let G be a k-connected graph and let \(e=xy\) be an edge in g. The edge e is said to be k-contractible if identifying the vertices x and y results in a k-connected graph. The paper investigates the distribution of k- contractible edges in a graph G. It shows that, if G is a k-connected graph which is triangle-free or has minimum degree at least \(\lfloor 3k/2\rfloor\) then the subgraph of G induced by its k-contractible edges is a 2-connected spanning subgraph of G. Furthermore, if \(k\geq 3\), then G contains an induced cycle C such that all edges in C are k-contractible and V(C) is not a cutset for G.
scientific article; zbMATH DE number 4125431