Accepted author manuscript, 298 KB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - An inductive construction of (2,1)-tight graphs
AU - Nixon, Anthony
AU - Owen, John
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
M3 - Journal article
VL - 9
SP - 1
EP - 16
JO - Contributions to Discrete Mathematics
JF - Contributions to Discrete Mathematics
SN - 1715-0868
IS - 2
ER -