✦ LIBER ✦

Bipartite graphs with cycles of all even lengths

✍ Scribed by Edward Schmeichel; John Mitchem

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 428 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060407

No coin nor oath required. For personal study only.

✦ Synopsis

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 length when n > 3.

📜 SIMILAR VOLUMES

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

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

Planar Graphs Without Cycles of Specific

Planar Graphs Without Cycles of Specific Lengths

✍ G. Fijavž; M. Juvan; B. Mohar; R. Škrekovski 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 208 KB

It is easy to see that planar graphs without 3-cycles are 3-degenerate. Recently, it was proved that planar graphs without 5-cycles are also 3-degenerate. In this paper it is shown, more surprisingly, that the same holds for planar graphs without 6-cycles.

Complementary Cycles of All Lengths in T

Complementary Cycles of All Lengths in Tournaments

✍ Z.M. Song 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 295 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

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,