An inductive construction of $(2,1)$-tight graphs

Anthony Nixon, John Owen


The graphs $G=(V,E)$ with $|E|=2|V|-\ell$ that satisfy $|E'|\leq 2|V'|-\ell$ for any subgraph $G'=(V',E')$ (and for $\ell=1,2,3$) are the $(2,\ell)$-tight graphs. The Henneberg--Laman theorem characterizes $(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 simple graphs. Here an alternative characterization is provided by means of vertex-to-$K_4$ and edge-to-$K_3$ moves. This is extended to the $(2,1)$-tight simple graphs by the addition of an edge joining move.

Full Text:


Contributions to Discrete Mathematics. ISSN: 1715-0868