###### Options

# More on foxes

Publikationstyp

Journal Article

Publikationsdatum

2018-10-01

Sprache

English

TORE-URI

Enthalten in

Volume

89

Issue

2

Start Page

101

End Page

114

Citation

Journal of Graph Theory (2018)

Publisher DOI

Scopus ID

An edge in a k-connected graph G is called 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 đ â 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/2k-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.