Large circuits in binary matroids of large cogirth. I (Q1127871)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Large circuits in binary matroids of large cogirth. I
scientific article

    Statements

    Large circuits in binary matroids of large cogirth. I (English)
    0 references
    14 December 1998
    0 references
    The purpose of this paper is to extend two classical results concerning the existence of long circuits in a simple 2-connected graph \(G\) to a simple connected regular matroid \(M\), or more generally to a simple connected binary matroid \(M\) with certain forbidden minors, including the class of regular matroids. The first result, due to G. A. Dirac, states that if \(G\) has minimum degree \(d\geq| V(G)|/2\), then \(G\) is hamiltonian. The second result, due to P. Erdős and T. Gallai, states that if \(e= uv\in E(G)\) and every vertex of \(V(G)- \{u,v\}\) has degree at least \(d\), then \(G\) has a circuit \(C\) containing \(e\) and of size at least \(d+1\). Our extension of Dirac's theorem is to show that if every cocircuit of \(M\) has size at least \(d\geq (r(M)+1)/2\) then \(M\) has a circuit of size \(r(M)+1\). Our extension of the Erdős-Gallai theorem is to show that, if \(e\in E(M)\) and every cocircuit of \(M\) disjoint from \(e\) has size at least \(d\geq 3\), then \(M\) has a circuit of size at least \(d+1\) containing \(e\). The extension of Dirac's theorem was conjectured by D. J. A. Welsh. The extension of the Erdős-Gallai result generalises a result of R. E. Bixby and W. H. Cunningham that if \(M\) is a simple binary matroid with no \(F_7\)-minor and every cocircuit of \(M\) has size at least \(d\), then \(r(M)\geq d\).
    0 references
    binary matroids
    0 references
    regular matroids
    0 references
    hamiltonicity
    0 references
    0 references
    0 references

    Identifiers