2011/03/15 by Anthony Nixon, John Owen, John J. T. Owen +2 · 1 citation
Computer Science · Engineering · Mathematics · #05B35 #05C05 #05C10 #52C25 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Structural Analysis and Optimization #math.CO #math.MG #msc:05B35 #msc:05C05 #msc:05C10 #msc:52C25
paper · pdf · doi:10.48550/arxiv.1103.2967
14 pages, 7 figures, revised and shortened after comments from referees
openalex publication_date 2011/03/15 · arxiv created 2012/10/16 · arxiv updated 2012/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The simple graphs G=(V,E) that satisfy |E'|≤ 2|V'|-l for any subgraph (and for l=1,2,3) are the (2,l)-sparse graphs. Those that also satisfy |E|=2|V|-l are the (2,l)-tight graphs. These can be characterised by their decompositions into two edge disjoint spanning subgraphs of various types. The Henneberg--Laman theorem characterises (2,3)-tight graphs inductively in terms of two simple moves, known as the Henneberg moves. Recently this has been extended, via the addition of a graph extension move, to the case of (2,2)-tight graphs. Here an alternative characterisation is provided by means of vertex-to-K4 and edge-to-K3 moves, and this is extended to the (2,1)-tight graphs by addition of an edge joining move. Similar characterisations of (2,l)-sparse graphs are also provided.