✦ LIBER ✦

Existence of graphs with specified cycle lengths

✍ Scribed by William McCuaig

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 808 KB
Volume: 78
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90169-6

No coin nor oath required. For personal study only.

✦ Synopsis

We prove the following two theorems. L,etn,ga3andletIr{3,..., g}. There exists an n-regular n-connected graph G such that for every i E (3, . . .,g}, GhasacycleofDengthiifandonlyifiEI.

L&m, da1 andletJc{O,l,... , d}. There exists an m-connected graph H such that for everyiE{O,l,...

, d}, H has a cycle of length v(H) -i if and only if i EJ

📜 SIMILAR VOLUMES

Graphs with k odd cycle lengths

✍ A. Gyárfás 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 481 KB

Gyarf&, A., Graphs with k odd cycle lengths, Discrete Mathematics 103 (1992) 41-48. If G is a graph with k z 1 odd cycle lengths then each block of G is either KZk+2 or contains a vertex of degree at most 2k. As a consequence, the chromatic number of G is at most 2k + 2. For a graph G let L(G) deno

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

Cycle lengths and circuit matroids of gr

Cycle lengths and circuit matroids of graphs

✍ D.R. Woodall 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 331 KB

Berge graphs with chordless cycles of bo

Berge graphs with chordless cycles of bounded length

✍ Rusu, Irena 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 2 views

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C

Bipartite graphs with cycles of all even

Bipartite graphs with cycles of all even lengths

✍ Edward Schmeichel; John Mitchem 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB 👁 1 views

## Abstract Let __G__ = (__X, Y, E__) be a bipartite graph with __X__ = __Y__ = __n__. Chvátal gave a condition on the vertex degrees of __X__ and __Y__ which implies that __G__ contains a Hamiltonian cycle. It is proved here that this condition also implies that __G__ contains cycles of every even