✦ LIBER ✦

Approximating Longest Cycles in Graphs with Bounded Degrees

✍ Scribed by Chen, Guantao; Gao, Zhicheng; Yu, Xingxing; Zang, Wenan

Book ID: 118180686
Publisher: Society for Industrial and Applied Mathematics
Year: 2006
Tongue: English
Weight: 301 KB
Volume: 36
Category: Article
ISSN: 0097-5397
DOI: 10.1137/050633263

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Longest Paths and Longest Cycles in Grap

Longest Paths and Longest Cycles in Graphs with Large Degree Sums

✍ Ingo Schiermeyer; Meike Tewes 📂 Article 📅 2002 🏛 Springer Japan 🌐 English ⚖ 139 KB

Longest cycles in polyhedral graphs

✍ Hansjoachim Walther 📂 Article 📅 1993 🏛 The Hebrew University Magnes Press 🌐 English ⚖ 254 KB

Longest cycles in threshold graphs

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

The longest cycle of a graph with a larg

The longest cycle of a graph with a large minimal degree

✍ Noga Alon 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB 👁 1 views

We show that every graph G on n vertices with minimal degree at least n / k contains a cycle of length at least [ n / ( k -111. This verifies a conjecture of Katchalski. When k = 2 our result reduces t o the classical theorem of Dirac that asserts that if all degrees are at least i n then G is Hamil

Longest cycles in 3-connected graphs

✍ B. Wei 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 395 KB