✦ LIBER ✦

Longest cycles in tough graphs

✍ Scribed by Jung, H.A.; Wittmann, P.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 347 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199906)31:2<107::aid-jgt4>3.0.co;2-l

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Toughness and longest cycles in 2-connec

Toughness and longest cycles in 2-connected planar graphs

✍ B�hme, T.; Broersma, H. J.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB 👁 2 views

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) 2 ona for some positiv

Intersections of longest cycles in grid

Intersections of longest cycles in grid graphs

✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 2 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

Cycles in butterfly graphs

✍ Hwang, Shien-Ching; Chen, Gen-Huey 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB 👁 1 views

Three problems in connection with cycles on the butterfly graphs are studied in this paper. The first problem is to construct complete uniform cycle partitions for the butterfly graphs. Suppose that

Long cycles in critical graphs

✍ Noga Alon; Michael Krivelevich; Paul Seymour 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 57 KB 👁 1 views

Hamilton cycles in random graphs and dir

Hamilton cycles in random graphs and directed graphs

✍ Colin Cooper; Alan Frieze 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 1 views

Disjoint cycles in star-free graphs

✍ Markus, Lisa R.; Snevily, Hunter S. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 322 KB 👁 1 views

A graph is claw-free if it does not contain K l , 3 as an induced subgraph. It is Kl,,-free if it does not contain K l , r as an induced subgraph. We show that if a graph is Kl,,-free ( r 2 4), only p + 2r -1 edges are needed to insure that G has t w o disjoint cycles. As an easy consequence w e ge