Abstract | ||
---|---|---|
In 1981, Seymour proved a conjecture of Welsh that, in a connected matroid M, the sum of the maximum number of disjoint circuits and the minimum number of circuits needed to cover M is at most r*(M)+1. This paper considers the set Ce(M) of circuits through a fixed element e such that M/e is connected. Let ve(M) be the maximum size of a subset of Ce(M) in which any two distinct members meet only in {e}, and let θe(M) be the minimum size of a subset of Ce(M) that covers M. The main result proves that ve(M)+θe(M)≤r*(M)+2 and that if M has no Fano-minor using e, then ve(M)+θe(M)≤r*(M)+1. Seymour's result follows without difficulty from this theorem and there are also some interesting applications to graphs. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1016/j.jctb.2005.07.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
distinct member,main result,disjoint circuit,matroid packing,connected matroid,minimum size,minimum number,maximum number,maximum size,set ce,fixed element e | Matroid,Graph,Discrete mathematics,Combinatorics,Disjoint sets,Electronic circuit,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
96 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
1 | 0.35 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manoel Lemos | 1 | 83 | 19.44 |
James Oxley | 2 | 194 | 24.39 |