✦ LIBER ✦

Lengths of cycles in halin graphs

✍ Scribed by J. A. Bondy; L. Lovász

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 436 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090311

No coin nor oath required. For personal study only.

✦ Synopsis

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 cycles of all lengths I, 3 zs I4 n, except, possibly, for one even value m of 1. W e prove also that if the tree T contains no vertex of degree three then G is pancyclic

📜 SIMILAR VOLUMES

Minimum cycle bases of Halin graphs

✍ Peter F. Stadler 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Halin graphs are planar 3‐connected graphs that consist of a tree and a cycle connecting the end vertices of the tree. It is shown that all Halin graphs that are not “necklaces” have a unique minimum cycle basis. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 150–155, 2003

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.

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

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,

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

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