𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Amr Elmasry; Kurt Mehlhorn; Jens M. Schmidt

Book ID
112121105
Publisher
John Wiley and Sons
Year
2012
Tongue
English
Weight
468 KB
Volume
72
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Non-contractible edges in a 3-connected
Non-contractible edges in a 3-connected graph
✍ Yoshimi Egawa; Katsuhiro Ota; Akira Saito; Xingxing Yu πŸ“‚ Article πŸ“… 1995 πŸ› Springer-Verlag 🌐 English βš– 412 KB
The 3-connected graphs having a longest
The 3-connected graphs having a longest cycle containing only three contractible edges
✍ R. E. L. Aldred; Robert L. Hemminger; Katsuhiro Ota πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 570 KB

## Abstract It is shown that with one small exception, the 3‐connected graphs admitting longest cycles that contain less than four contractible edges of the parent graph are the members of three closely related infinite families. Β© 1993 John Wiley & Sons, Inc.

A Degree Sum Condition for the Existence
A Degree Sum Condition for the Existence of a Contractible Edge in a ΞΊ-Connected Graph
✍ Matthias Kriesell πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 184 KB

It is known that a noncomplete }-connected graph of minimum degree of at least w 5} 4 x contains a }-contractible edge, i.e., an edge whose contraction yields again a }-connected graph. Here we prove the stronger statement that a noncomplete }-connected graph for which the sum of the degrees of any