Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

DOI10.1002/jgt.21635zbMath1259.05097OpenAlexW2166011833MaRDI QIDQ4908826

Kurt Mehlhorn, Jens M. Schmidt, Amr Elmasry

Publication date: 7 March 2013

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21635

zbMATH Keywords

edgesspanning tree3-connected graphDFS-tree

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40)

Related Items (3)

Contractible edges in longest cycles ⋮ Contractible edges and removable edges in 3-connected graphs ⋮ Unnamed Item

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certifying algorithms
• Non-\(\kappa\)-critical vertices in graphs
• Contractible edges in 3-connected graphs
• The number of contractible edges in 3-connected graphs
• Generalizaions of critical connectivity of graphs
• A new graph triconnectivity algorithm and its parallelization
• A survey on contractible edges in graphs of a prescribed vertex connectivity
• On the number of contractible triples in 3-connected graphs
• Zur Theorie der n-fach zusammenhängenden Graphen
• Removable edges in 3-connected graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Removable Edges of a Spanning Tree in 3-Connected 3-Regular Graphs
• Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs
• Finding triconnected components of graphs
• Longest cycles in 3-connected graphs contain three contractible edges
• Dividing a Graph into Triconnected Components
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge