On minimally k-rigid graphs

Viktória Kaszanitzky, Csaba Király


A graph G=(V,E) is called k-rigid in Rd if |V| ≥ k+1 and after deleting at most k-1 arbitrary vertices the resulting graph is generically rigid in Rd. A k-rigid graph G is called minimally k-rigid if the omission of an arbitrary edge results in a graph that is not k-rigid. It was shown in [7] that the smallest possible number of edges is 2|V|-1 in a 2-rigid graph in R2. We generalize this result, provide an upper bound for the number of edges of minimally 2-rigid graphs (for any d) and give examples for minimally k-rigid graphs in higher dimensions.

Bibtex entry:

AUTHOR = {Kaszanitzky, Vikt{\'o}ria and Kir{\'a}ly, Csaba},
TITLE = {On minimally k-rigid graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-21}

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