𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cycle Cover Ratio of Regular Matroids

✍ Scribed by Hong-Jian Lai; Hoifung Poon


Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
180 KB
Volume
23
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis


A cycle in a matroid is a disjoint union of circuits. This paper proves that every regular matroid M without coloops has a set S of cycles whose union is E(M) such that every element is in at most three of the cycles in S. It follows immediately from this that, on average, each element of M is in at most three members of the cycle cover S. This improves on a 1989 result of Jamshy and Tarsi who proved that there is a cycle cover for which this average is at most 4, and conjectured that a cycle cover exists for which the average is at most 2.


πŸ“œ SIMILAR VOLUMES


Cycle covering of binary matroids
✍ Ury Jamshy; Michael Tarsi πŸ“‚ Article πŸ“… 1989 πŸ› Elsevier Science 🌐 English βš– 408 KB