A Decomposition Theorem for Binary Matroids with no Prism Minor |
| |
Authors: | S R Kingan Manoel Lemos |
| |
Institution: | 1. Department of Mathematics Brooklyn College, City University of NewYork, Brooklyn, NY, 11210, USA 2. Departamento de Matematica, Universidade Federal de Pernambuco, Recife Pernambuco, 50740-540, Brazil
|
| |
Abstract: | The prism graph is the dual of the complete graph on five vertices with an edge deleted, K 5\ 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 Mayhew and Royle’s result identifying the binary internally 4-connected matroids with no prism minor Mayhew and Royle (Siam J Discrete Math 26:755–767, 2012). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|