Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4624790 | Advances in Applied Mathematics | 2014 | 40 Pages |
In 1971, Nash-Williams proved that if G is a simple 2-connected graph on n vertices having minimum degree at least 13(n+2), then any longest cycle C in G is also edge-dominating; that is, each edge of G has at least one end-vertex incident with a vertex of C. We say that a circuit C in a matroid M is dominating if each component of M/CM/C has rank at most one. In this paper, we show that an analogous theorem holds for regular matroids. More specifically, suppose M is a simple, connected, regular matroid and let C be a circuit in M . We show that if |C⁎|>r(M)3+1, for all cocircuits C⁎C⁎ in M which are disjoint from C, then either C is a dominating circuit, or there is a circuit D such that the symmetric difference of C with D is a circuit which is strictly larger than C.