✦ LIBER ✦

A Note on Cycle Lengths in Graphs

✍ Scribed by R.J. Gould; P.E. Haxell; A.D. Scott

Publisher: Springer Japan
Year: 2002
Tongue: English
Weight: 121 KB
Volume: 18
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s003730200035

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Unavoidable cycle lengths in graphs

✍ Jacques Verstraete 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB

## 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 degre

Cycle lengths in sparse graphs

✍ Benny Sudakov; Jacques Verstraëte 📂 Article 📅 2008 🏛 Springer-Verlag 🌐 English ⚖ 515 KB

On the distribution of cycle lengths in

On the distribution of cycle lengths in graphs

✍ A. Gyárfás; J. Komlós; E. Szemerédi 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 843 KB

The set of different cycle lengths of a graph G is denoted by C(G). We study how the distribution of C(G) depends on the minimum degree of G. We prove two results indicating that C(G) is dense in some sense. These results lead to the solution of a conjecture of Erdos and Hajnal stating that for suit

On cycle lengths in graphs of moderate d

On cycle lengths in graphs of moderate degree

✍ H. Bencherif Ait-Djafer 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 447 KB

We show that for all positive E, an integer N(E) exists such that if G is any graph of order n>N(s) with minimum degree 63324 then G contains a cycle of length 21 for each integer 1, 2<1<~/(16+s). Bondy [4] and Woodall [15] have obtained sufficient conditions for a graph to contain cycles of each le

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,