TR-2012-21

On minimally k-rigid graphs

Viktória Kaszanitzky, Csaba Király

A graph G=(V,E) is called k-rigid in R^d if |V| ≥ k+1 and after deleting at most k-1 arbitrary vertices the resulting graph is generically rigid in R^d. 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 R². 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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-21}

}