✦ LIBER ✦

Cycles of length 0 modulo 4 in graphs

✍ Scribed by Nathaniel Dean; Linda Lesniak; Akira Saito

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 829 KB
Volume: 121
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90535-2

No coin nor oath required. For personal study only.

✦ Synopsis

In several papers a variety of questions have been raised concerning the existence of cycles of length Omod k in graphs. For the case k=4, we answer three of these questions by showing that a graph G contains such a cycle provided it has any of the following three properties: (1) G has minimum degree at least 2 and at most two vertices of degree 2, (2) G is not 3-colorable, and (3) G is a subdivision of a graph of order p>5 with at least 3p-5 edges.

📜 SIMILAR VOLUMES

Cycles of length 0 modulo k in directed

Cycles of length 0 modulo k in directed graphs

✍ Noga Alon; N Linial 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 417 KB

Cycles of length 2 modulo 3 in graphs

✍ Akira Saito 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 274 KB

Saito, A., Cycles of length 2 modulo 3 in graphs, Discrete Mathematics 101 (1992) 285-289. We prove that if a graph G of minimum degree at least 3 has no cycle of length 2 (mod 3), then G has an induced subgraph which is isomorphic to either K4 or Ks,s. The above result together with its relatively

Cycles of even lengths modulo k

✍ Ajit A. Diwan 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB

## Abstract Thomassen [J Graph Theory 7 (1983), 261–271] conjectured that for all positive integers __k__ and __m__, every graph of minimum degree at least __k__+1 contains a cycle of length congruent to 2__m__ modulo __k__. We prove that this is true for __k__⩾2 if the minimum degree is at least 2

Cycles of even length in graphs

✍ J.A Bondy; M Simonovits 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 363 KB

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

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