✦ LIBER ✦

On cycle lengths in graphs of moderate degree

✍ Scribed by H. Bencherif Ait-Djafer

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 447 KB
Volume: 125
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90143-0

No coin nor oath required. For personal study only.

✦ Synopsis

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 length 2, 3 < I < m, where m is a constant. Subsequently, several authors [3, 5, 12-141 proved results which support Bondy's metaconjecture.

We state sufficient conditions in terms of minimum degree for a graph to contain cycles of specified lengths.

We start with a result due to Dirac.

Theorem 1.1 (Dirac [9]). Let G be a graph of order n > 3, with minimum degree 6 2 n/2.

Then G is Hamiltonian.

The following result of Bondy generalizes Theorem 1.1.

Theorem 1.2 (Bondy [ 51). Let G be a graph of order n> 3, with minimum degree 6 >n/2. Then G is pancyclic unless n is even and G is the complete bipartite graph K./z, n/2.

📜 SIMILAR VOLUMES

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

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

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

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

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,

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