TR-2001-08

A proof of Connelly's conjecture on 3-connected generic cycles

Alex Berg, Tibor Jordán

Published in:
J. Comb Theory B 88 (2003) 77-97.



Abstract

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 K4 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}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!