✦ LIBER ✦

On the Circumferences of Regular 2-Connected Graphs

✍ Scribed by Bing Wei

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 135 KB
Volume: 75
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1866

No coin nor oath required. For personal study only.

✦ Synopsis

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 result of Jackson. Examples to show that the bond for c(G) is sharp and that Bondy's conjecture does not hold if r is allowed to take non-integer values are given.

📜 SIMILAR VOLUMES

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

Circumference of a regular graph

✍ Min Aung 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB

Circumferences of k-connected graphs inv

Circumferences of k-connected graphs involving independence numbers

✍ Guantao Chen; Zhiquan Hu; Yaping Wu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB 👁 1 views

Let G be a k-connected graph of order n, := (G) the independence number of G, and c(G) the circumference of G. Chvátal and Erdo ˝s proved that if ≤ k then G is hamiltonian. For ≥ k ≥ 2, Fouquet and Jolivet in 1978 made the conjecture that c(G) ≥ k(n+ -k) / . Fournier proved that the conjecture is tr

Hamilton Cycles in Almost-Regular 2-Conn

Hamilton Cycles in Almost-Regular 2-Connected Graphs

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

Degree bounds for the circumference of 3

Degree bounds for the circumference of 3-connected graphs

✍ Heinz A. Jung; Elkin Vumar 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB 👁 1 views

## Abstract Let __C__ be a longest cycle in the 3‐connected graph __G__ and let __H__ be a component of __G__ − __V__(__C__) such that |__V__(__H__)| ≥ 3. We supply estimates of the form |__C__| ≥ 2__d__(__u__) + 2__d__(__v__) − α(4 ≤ α ≤ 8), where __u__,__v__ are suitably chosen non‐adjacent verti

r-Regular, r-connected decompositions of

r-Regular, r-connected decompositions of complete graphs

✍ H. Fleischner; W. R. Johnstone; A. J. W. Hilton 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 2 views

If rjn À 1 and rn is even, then K n can be expressed as the union of t nÀ1 r edgedisjoint isomorphic r-regular r-connected factors.