Cycle Cover Ratio of Regular Matroids |
| |
Authors: | Hong-Jian Lai Hoifung Poon |
| |
Affiliation: | Department of Mathematics, West Virginia University, Morgantown, WV 26506, U.S.A.f1 |
| |
Abstract: | A cycle in a matroid is a disjoint union of circuits. This paper proves that every regular matroidM 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|