Mathematics – Combinatorics
Scientific paper
2012-03-16
Mathematics
Combinatorics
Scientific paper
The prism graph is the dual of the complete graph on five vertices with an edge deleted, $K_5\backslash e$. In this paper we determine the class of binary matroids with no prism minor. The motivation for this problem is the 1963 result by Dirac where he identified the simple 3-connected graphs with no minor isomorphic to the prism graph. We prove that besides Dirac's infinite families of graphs and four infinite families of non-regular matroids determined by Oxley, there are only three possibilities for a matroid in this class: it is isomorphic to the dual of the generalized parallel connection of $F_7$ with itself across a triangle with an element of the triangle deleted; it's rank is bounded by 5; or it admits a non-minimal exact 3-separation induced by the 3-separation in $P_9$. Since the prism graph has rank 5, the class has to contain the binary projective geometries of rank 3 and 4, $F_7$ and $PG(3, 2)$, respectively. We show that there is just one rank 5 extremal matroid in the class. It has 17 elements and is an extension of $R_{10}$, the unique splitter for regular matroids. As a corollary, we obtain Dillon, Mayhew, and Royle's result identifying the binary internally 4-connected matroids with no prism minor [5].
Kingan Sandra
Lemos Manoel
No associations
LandOfFree
A decomposition theorem for binary matroids with no prism minor does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A decomposition theorem for binary matroids with no prism minor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A decomposition theorem for binary matroids with no prism minor will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-352068