✦ LIBER ✦

Unavoidable cycle lengths in graphs

✍ Scribed by Jacques Verstraete

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 160 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20072

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An old conjecture of Erdős states that there exists an absolute constant c and a set S of density zero such that every graph of average degree at least c contains a cycle of length in S. In this paper, we prove this conjecture by showing that every graph of average degree at least ten contains a cycle of length in a prescribed set S satisfying $|S \cap { 1,2,\ldots ,n} | = O(n^{0.99})$. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Distribution of Cycle Lengths in Graphs

✍ Genghua Fan 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 148 KB

Bondy and Vince proved that every graph with minimum degree at least three contains two cycles whose lengths differ by one or two, which answers a question raised by Erdo ˝s. By a different approach, we show in this paper that if G is a graph with minimum degree d(G) \ 3k for any positive integer k,

Cycle lengths in graphs with large minim

Cycle lengths in graphs with large minimum degree

✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Our main result is the following theorem. Let __k__ ≥ 2 be an integer, __G__ be a graph of sufficiently large order __n__, and __δ__(__G__) ≥ __n__/__k__. Then: __G__ contains a cycle of length __t__ for every even integer __t__ ∈ [4, __δ__(__G__) + 1]. If __G__ is nonbipartite then

Lengths of cycles in halin graphs

✍ J. A. Bondy; L. Lovász 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB 👁 1 views

A Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree t w o and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T We prove that such a graph on n vertices contains cy

Note on graphs without repeated cycle le

Note on graphs without repeated cycle lengths

✍ Chen, Guantao; Lehel, Jen�; Jacobson, Michael S.; Shreve, Warren E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

In this note we prove that every 2-connected graph of order n with no repeated cycle lengths has at most n + 2(n -2) -1 edges and we show this result is best possible with the correct order of magnitude on √ n. The 2connected case is also used to give a quick proof of Lai's result on the general cas

Degree sums for edges and cycle lengths

Degree sums for edges and cycle lengths in graphs

✍ Brandt, Stephan; Veldman, Henk Jan 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 3 views

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference-the length of a longest cycle-of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length be

Planar Graphs Without Cycles of Specific

Planar Graphs Without Cycles of Specific Lengths

✍ G. Fijavž; M. Juvan; B. Mohar; R. Škrekovski 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 208 KB

It is easy to see that planar graphs without 3-cycles are 3-degenerate. Recently, it was proved that planar graphs without 5-cycles are also 3-degenerate. In this paper it is shown, more surprisingly, that the same holds for planar graphs without 6-cycles.