✦ LIBER ✦

Contractible edges in longest cycles in non-Hamiltonian graphs

✍ Scribed by M.N. Ellingham; R.L. Hemminger; Kathryn E. Johnson

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 727 KB
Volume: 133
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90018-3

No coin nor oath required. For personal study only.

✦ Synopsis

An edge of a 3-connected graph is contractible if its contraction results in a graph which is still 3-connected. All 3-connected graphs with seven or more vertices are known to have at least three contractible edges on any longest cycle. Recently, it has been conjectured that any non-Hamiltonian 3-connected graph has at least six contractible edges on any longest cycle. We prove this conjecture and provide a construction to show that it is best possible.

📜 SIMILAR VOLUMES

Longest cycles in 3-connected graphs con

Longest cycles in 3-connected graphs contain three contractible edges

✍ Nathaniel Dean; Robert L. Hemminger; Katsuhiro Ota 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB 👁 1 views

We show that if G is a 3-connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges. We consider only finite undirect

Contractible Non-edges in 3-Connected Gr

Contractible Non-edges in 3-Connected Graphs

✍ Matthias Kriesell 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 495 KB

We present a reduction theorem for the class of all finite 3-connected graphs which does not make use of the traditional contraction of certain connected subgraphs. ## 1998 Academic Press Contractible edges play an important role in the theory of 3-connected graphs. Besides the famous wheel theore

Contractible edges in 3-connected graphs

✍ Kiyoshi Ando; Hikoe Enomoto; Akira Saito 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 371 KB

Longest cycles in tough graphs

✍ Jung, H.A.; Wittmann, P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 2 views

In this article, we establish bounds for the length of a longest cycle C in a 2-connected graph G in terms of the minimum degree δ and the toughness t. It is shown that C is a Hamiltonian cycle or |C| ≥ (t + 1)δ + t.

Longest cycles in threshold graphs

✍ N.V.R. Mahadev; U.N. Peled 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 495 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.