A constructive characterisation of circuits in the simple (2,1)-sparse matroid

2016/04/18 by Thomas A. McCourt, Thomas A McCourt, Anthony Nixon +2
Computer Science · Mathematics · #05C75 #52C25 #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Complexity and Algorithms in Graphs #FOS: Mathematics #math.CO #msc:05C75 #msc:52C25

paper · pdf · doi:10.48550/arxiv.1604.05226

25 pages, 17 figures, revised following reviewer comments

openalex publication_date 2016/04/18 · arxiv created 2018/01/08 · arxiv updated 2018/01/09 · openalex created_date 2022/08/06 · openalex updated_date 2026/07/28

Abstract

A simple graph G=(V,E) is a (2,1)-circuit if |E|=2|V| and |E(H)|≤ 2|V(H)|-1 for every proper subgraph H of G. Motivated, in part, by ongoing work to understand unique realisations of graphs on surfaces, we derive a constructive characterisation of (2,1)-circuits. The characterisation uses the well known 1-extension and X-replacement operations as well as several summation moves to glue together (2,1)-circuits over small cutsets.

Related

• A Constructive Characterisation of Circuits in the Simple (2,2)-sparsity Matroid
• k-fold circuits and coning in rigidity matroids
• A Method to construct the Sparse-paving Matroids over a Finite Set
• Minimal matroids in dependency posets: algorithms and applications to computing irreducible decompositions of circuit varieties
• On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)