Name
Abstract | ||
|---|---|---|
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 k is an element of {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/2k - 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 K-4 has at least 1/3 vertical bar V(G)vertical bar - 1 many 3-contractible edges, and (e) every DFS tree of a 3-connected graph nonisomorphic to K-4, 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/jgt.22243 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
contractible edge,DFS tree,fox,spanning tree | Journal | 89.0 |
Issue | ISSN | Citations |
2.0 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthias Kriesell | 1 | 349 | 43.73 |
| Jens M. Schmidt | 2 | 0 | 1.69 |