✦ LIBER ✦

On the distribution of cycle lengths in graphs

✍ Scribed by A. Gyárfás; J. Komlós; E. Szemerédi

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 843 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080402

No coin nor oath required. For personal study only.

✦ Synopsis

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 suitable positive constants a, b the following holds:

where 6(G) denotes the minimum degree of G.

📜 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,

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

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

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

On the length of longest dominating cycl

On the length of longest dominating cycles in graphs

✍ Hoa Vu Dinh 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 719 KB

Vu Dinh, H., On the length of longest dominating cycles in graphs, Discrete Mathematics 121 (1993) 21 l-222. ## A cycle C in an undirected and simple graph if G contains a dominating cycle. There exists l-tough graph in which no longest cycle is dominating. Moreover, the difference of the length

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