Every DFS tree of a 3-connected graph contains a contractible edge

Amr Ahmed Abd Elmoneim Elmasry; Kurt Mehlhorn; Jens M. Schmidt

doi:10.1002/jgt.21635

Every DFS tree of a 3-connected graph contains a contractible edge

Amr Ahmed Abd Elmoneim Elmasry, Kurt Mehlhorn, Jens M. Schmidt

Department of Computer Science

3 Citations (Scopus)

Abstract

Tutte proved that every 3-connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth-first-search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3-regular or if G does not contain two disjoint pairs of adjacent degree-3 vertices.

Original language	English
Journal	Journal of Graph Theory
Volume	72
Issue number	1
Pages (from-to)	112-121
Number of pages	10
ISSN	0364-9024
DOIs	https://doi.org/10.1002/jgt.21635
Publication status	Published - Jan 2013

Access to Document

10.1002/jgt.21635

Cite this

@article{9dd838a48183461f890a3bfb0eacca5f,

title = "Every DFS tree of a 3-connected graph contains a contractible edge",

abstract = "Tutte proved that every 3-connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth-first-search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3-regular or if G does not contain two disjoint pairs of adjacent degree-3 vertices.",

author = "Elmasry, {Amr Ahmed Abd Elmoneim} and Kurt Mehlhorn and Schmidt, {Jens M.}",

year = "2013",

month = jan,

doi = "10.1002/jgt.21635",

language = "English",

volume = "72",

pages = "112--121",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "JohnWiley & Sons, Inc.",

number = "1",

}

TY - JOUR

T1 - Every DFS tree of a 3-connected graph contains a contractible edge

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Mehlhorn, Kurt

AU - Schmidt, Jens M.

PY - 2013/1

Y1 - 2013/1

N2 - Tutte proved that every 3-connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth-first-search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3-regular or if G does not contain two disjoint pairs of adjacent degree-3 vertices.

AB - Tutte proved that every 3-connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth-first-search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3-regular or if G does not contain two disjoint pairs of adjacent degree-3 vertices.

U2 - 10.1002/jgt.21635

DO - 10.1002/jgt.21635

M3 - Journal article

SN - 0364-9024

VL - 72

SP - 112

EP - 121

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -