Article ID Journal Published Year Pages File Type
4624790 Advances in Applied Mathematics 2014 40 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
,