✦ LIBER ✦

Graphs with a Cycle of Length Divisible by Three

✍ Scribed by G.T. Chen; A. Saito

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 468 KB
Volume: 60
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1019

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we will prove that every graph (G) with minimum degree (\delta(G) \geqslant 3) contains a cycle of length divisible by three. This was conjectured to be true by Barefoot, Clark, Douthett, and Entringer. 11994 Academic Press, Inc.

📜 SIMILAR VOLUMES

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

Covering the vertices of a graph by cycl

Covering the vertices of a graph by cycles of prescribed length

✍ D. Amar; I. Fournier; A. Germa 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

The main theorem of that paper is the following: let G be a graph of order n, of size at least (nZ -3n + 6 ) / 2 . For any integers k, n,, n2,. . . , nk such that n = n, + n2 + ... + nk and n, 2 3, there exists a covering of the vertices of G by disjoint cycles (C,),=,..,k with ICjl = n,, except whe

Maximum packings of the complete graph w

Maximum packings of the complete graph with uniform length cycles

✍ Daniel Horsley 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

In this paper we find the maximum number of pairwise edgedisjoint m-cycles which exist in a complete graph with n vertices, for all values of n and m with 3 ≤ m ≤ n.

Cycles in a graph whose lengths differ b

Cycles in a graph whose lengths differ by one or two

✍ Bondy, J. A.; Vince, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 2 views

Several problems concerning the distribution of cycle lengths in a graph have been proposed by P. Erdös and colleagues. In this note two variations of the following such question are answered. In a simple graph where every vertex has degree at least three, must there exist two cycles whose lengths d

On the number of cycles of length 4 in a

On the number of cycles of length 4 in a maximal planar graph

✍ Ahmad Fawzi Alameddine 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ ≥