Ordering circuits of matroids
When a graph theorist first learns about matroids he might hope that matroids possess some property that can be used to make up for their lack of vertices. One such property is the orderability property studied in this paper. A matroid is orderable if its circuits can be given a consistent ordering, that is, the elements of each circuit can be given a reversible cyclic ordering, so that if two elements are adjacent in a circuit, then they are adjacent in every circuit in which they both appear. Clearly graphic matroids are orderable, but it is easy to see that \(U_{2,4}\) is also orderable. The authors' main result characterizes connected, non-binary, orderable matroids as those which may be obtained from \(U_{2,4}\) by a sequence of balanced series extensions (series extensions in which every element is replaced by the same number of series elements) and parallel path additions (essentially the matroid analogue of taking a path \(P\) with each internal vertex having degree two and attaching a new path \(P^\prime\) with the same length as \(P\) to the ends of \(P\)). The situation for binary matroids is less clear. The authors show that for every binary matroid \(M\), if either every series minor of \(M\) is orderable or every parallel minor of \(M\) is orderable, then \(M\) is graphic. Certainly there are non-graphic binary matroids which are not orderable, as the authors describe series extensions of \(F_7^\ast\) and \(M^\ast(K_5)\) which are not orderable. They conjecture that every \(3\)-connected binary orderable matroid is graphic and prove that every \(4\)-connected regular orderable matroid is graphic.
- A characterization of graphic matroids based on circuit orderings
- Internally 4-connected binary matroids with cyclically sequential orderings
- A circuit characterization of graphic matroids
- Adjacency, inseparability, and base orderability in matroids
- Ordering of the elements of a matroid such that its consecutive w elements are independent
- 2-Isomorphic Graphs
- A circuit characterization of graphic matroids
- A strengthened form of Tutte's characterization of regular matroids
- Adjacency in binary matroids
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- Kuratowski's and Wagner's theorems for matroids
- Matroids and Graphs
- Minors of 3-connected matroids
- On Nonbinary 3-Connected Matroids
This page was built for publication: Ordering circuits of matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2112564)
