2016/10/28 by Matthias Kriesell, Kriesell, Matthias, Jens M. Schmidt +1
Mathematics · #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1610.09093
An edge in a k-connected graph G is called \em k-contractible if the graph G/e obtained from G by contracting e is k-connected. Generalizing earlier results on 3-contractible edges in spanning trees of 3-connected graphs, we prove that (except for the graphs Kk+1 if k ∈ \1,2\) (a) every spanning tree of a k-connected triangle free graph has two k-contractible edges, (b) every spanning tree of a k-connected graph of minimum degree at least (3)/(2)k-1 has two k-contractible edges, (c) for k>3, every DFS tree of a k-connected graph of minimum degree at least (3)/(2)k-(3)/(2) has two k-contractible edges, (d) every spanning tree of a cubic 3-connected graph nonisomorphic to K4 has at least (1)/(3)|V(G)|-1 many 3-contractible edges, and (e) every DFS tree of a 3-connected graph nonisomorphic to K4, the prism, or the prism plus a single edge has two 3-contractible edges. We also discuss in which sense these theorems are best possible.