Options
More on foxes
Publikationstyp
Journal Article
Date Issued
2018-10-01
Sprache
English
Author(s)
TORE-URI
Journal
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.
Subjects
05c05
05c40
contractible edge
DFS tree
fox
spanning tree