Constructing internally 4-connected binary matroids
Autor: | Dillon Mayhew, Carolyn Chun, James Oxley |
---|---|
Rok vydání: | 2013 |
Předmět: |
Discrete mathematics
Inductive construction Chain theorem Applied Mathematics 010102 general mathematics Minor (linear algebra) Binary number 0102 computer and information sciences 01 natural sciences Matroid Constructive Combinatorics Binary matroid Graphic matroid 010201 computation theory & mathematics Internally 4-connected Matroid partitioning 0101 mathematics Mathematics |
Zdroj: | Advances in Applied Mathematics. 50(1):16-45 |
ISSN: | 0196-8858 |
DOI: | 10.1016/j.aam.2012.03.005 |
Popis: | This is the post-print version of the Article - Copyright @ 2013 Elsevier In an earlier paper, we proved that an internally 4-connected binary matroid with at least seven elements contains an internally 4-connected proper minor that is at most six elements smaller. We refine this result, by giving detailed descriptions of the operations required to produce the internally 4-connected minor. Each of these operations is top-down, in that it produces a smaller minor from the original. We also describe each as a bottom-up operation, constructing a larger matroid from the original, and we give necessary and su fficient conditions for each of these bottom-up moves to produce an internally 4-connected binary matroid. From this, we derive a constructive method for generating all internally 4-connected binary matroids. This study is supported by NSF IRFP Grant 0967050, the Marsden Fund, and the National Security Agency. |
Databáze: | OpenAIRE |
Externí odkaz: |