Premium
A constructive characterisation of circuits in the simple (2,1)‐sparse matroid
Author(s) -
McCourt Thomas A.,
Nixon Anthony
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22245
Subject(s) - matroid , constructive , simple (philosophy) , mathematics , electronic circuit , combinatorics , matroid partitioning , graph , discrete mathematics , extension (predicate logic) , simple graph , graphic matroid , computer science , philosophy , process (computing) , epistemology , electrical engineering , programming language , engineering , operating system
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.