TR-2012-21

On minimally k-rigid graphs

Viktória Kaszanitzky, Csaba Király



Abstract

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:

@techreport{egres-12-21,
AUTHOR = {Kaszanitzky, Vikt{\'o}ria and Kir{\'a}ly, Csaba},
TITLE = {On minimally k-rigid graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
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!