✦ LIBER ✦

Cycle lengths and circuit matroids of graphs

✍ Scribed by D.R. Woodall

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 331 KB
Volume: 105
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90149-a

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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,

On removable circuits in graphs and matr

On removable circuits in graphs and matroids

✍ Lemos, Manoel; Oxley, James 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 283 KB

Mader proved that every 2-connected simple graph G with minimum degree d exceeding three has a cycle C, the deletion of whose edges leaves a 2-connected graph. Jackson extended this by showing that C may be chosen to avoid any nominated edge of G and to have length at least d-1. This article proves

Existence of graphs with specified cycle

Existence of graphs with specified cycle lengths

✍ William McCuaig 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 808 KB

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 c

Transversals of circuits and acyclic ori

Transversals of circuits and acyclic orientations in graphs and matroids

✍ C. Berge; M. Las Vergnas 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 132 KB

Note on graphs without repeated cycle le

Note on graphs without repeated cycle lengths

✍ Chen, Guantao; Lehel, Jen�; Jacobson, Michael S.; Shreve, Warren E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

In this note we prove that every 2-connected graph of order n with no repeated cycle lengths has at most n + 2(n -2) -1 edges and we show this result is best possible with the correct order of magnitude on √ n. The 2connected case is also used to give a quick proof of Lai's result on the general cas