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
• DOI: 10.1006/eujc.2002.0606

✦ 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.