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

DOI10.1002/JGT.22245MaRDI QIDQ4553733zbMATHOpenAlexFDO

Authors Thomas A. McCourt, Anthony Nixon

Publication date 31 October 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.05226

zbMATH Keywords

rigiditycount matroidconstructive characterisation

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99)

Abstract: A simple graph $G=(V,E)$ is a $(2,1)$-circuit if $|E|=2|V|$ and $|E(H)|leq2|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.

Recommendations

• A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid
• A circuit characterization of graphic matroids
• An inductive construction of \((2,1)\)-tight graphs
• A characterization of graphic matroids based on circuit orderings
• Graphs for \(n\)-circular matroids

Cited in

(1)

• A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid

This page was built for publication: A constructive characterisation of circuits in the simple (2,1)-sparse matroid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4553733)