Home > Research > Publications & Outputs > An inductive construction of (2,1)-tight graphs

Electronic data

  • NixonOwen(2,1)Final

    Accepted author manuscript, 298 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License


View graph of relations

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

Research output: Contribution to Journal/MagazineJournal articlepeer-review

<mark>Journal publication date</mark>2014
<mark>Journal</mark>Contributions to Discrete Mathematics
Issue number2
Number of pages16
Pages (from-to)1-16
Publication StatusPublished
<mark>Original language</mark>English


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.