✦ LIBER ✦

Hamiltonicity of regular 2-connected graphs

✍ Scribed by Broersma, H. J.; van den Heuvel, J.; Jackson, B.; Veldman, H. J.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 832 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199606)22:2<105::aid-jgt2>3.0.co;2-r

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n 5 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to q k if G is 3-connected and k 2 63. We improve both results by showing that G is hamiltonian if n 5 gk -7 and G does not belong to a restricted class 3 of nonhamiltonian graphs of connectivity 2. To establish this result we obtain a variation of Woodall's Hopping Lemma and use it to prove that if n 5 $ k -7 and G has a dominating cycle (i.e., a cycle such that the vertices off the cycle constitute an independent set), then G is hamiltonian. We also prove that if n 5 4k -3 and G $ 3, then G has a dominating cycle. For k 2 4 it is conjectured that G is hamiltonian if n 5 4k and G $ 3.

📜 SIMILAR VOLUMES

Hamilton Cycles in Almost-Regular 2-Conn

Hamilton Cycles in Almost-Regular 2-Connected Graphs

✍ B. Jackson 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 348 KB

On the Circumferences of Regular 2-Conne

On the Circumferences of Regular 2-Connected Graphs

✍ Bing Wei 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 135 KB

Let G be a 2-connected d-regular graph on n rd (r 3) vertices and c(G) denote the circumference of G. Bondy conjectured that c(G) 2nÂ(r&1) if n is large enough. In this paper, we show that c(G) 2nÂ(r&1)+2(r&3)Â(r&1) for any integer r 3. In particular, G is hamiltonian if r=3. This generalizes a resu

On Hamiltonian-connected regular graphs

✍ Ioan Tomescu 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

In this paper it is shown that any rn-regular graph of order 2rn (rn 3 3), not isomorphic to K, , , , or of order 2rn + 1 (rn even, rn 3 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains at least rn Hamiltonian

Hamiltonicity and forbidden subgraphs in

Hamiltonicity and forbidden subgraphs in 4-connected graphs

✍ Florian Pfender 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

## Abstract Let __T__ be the line graph of the unique tree __F__ on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., __T__ is a chain of three triangles. We show that every 4‐connected {__T__, __K__~1,3~}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49:

Hamilton cycles in regular graphs

✍ Bill Jackson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## UNIVERSIW OF WATERLOO ' The research reported here has been sponsored by the Canadian Commonwealth Association.

On the hamiltonicity of line graphs of l

On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs

✍ Richard C. Brewster; Daryl Funk 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a