Published in:
J. Comb Theory B 88 (2003) 77-97.
A graph G=(V,E) is called a generic cycle if |E|=2|V|-2 and every X \subset V with 2 \leq |X| \leq |V|-1 satisfies i(X) \leq 2|X|-3. Here i(X) denotes the number of edges induced by X. The operation extension subdivides an edge uw of a graph by a new vertex v and adds a new edge vz for some vertex z \not= u,w. R. Connelly conjectured that every 3-connected generic cycle can be obtained from K_{4} by a sequence of extensions. We prove this conjecture. As a corollary, we also obtain a special case of a conjecture of Hendrickson on generically globally rigid graphs.
Keywords:
Graphs, Connectivity, Rigidity
Bibtex entry:
@techreport{egres-01-08,
AUTHOR | = | {Berg, Alex and Jord{\'a}n, Tibor}, |
TITLE | = | {A proof of Connelly's conjecture on 3-connected generic cycles}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2001}, |
NUMBER | = | {TR-2001-08} |