✦ LIBER ✦

Cycles of even lengths modulo k

✍ Scribed by Ajit A. Diwan

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 84 KB
Volume: 65
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20477

No coin nor oath required. For personal study only.

✦ Synopsis

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__k__−1, which improves the previously known bound of 3__k__−2. We also show that Thomassen's conjecture is true for m = 2. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 246–252, 2010

📜 SIMILAR VOLUMES

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

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

The Number of k-Sums Modulo k

✍ Béla Bollobás; Imre Leader 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 110 KB

Periods in missing lengths of rainbow cy

Periods in missing lengths of rainbow cycles

✍ Petr Vojtěchovský 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

## Abstract A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph __G__, define Then 𝔊(__G__) is a monoid with respect to the operation __n__∘__m__=__n__+ __m__−2, and thus there is a least positive integer π

Complementary Cycles of All Lengths in T

Complementary Cycles of All Lengths in Tournaments

✍ Z.M. Song 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 295 KB

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.