TR-2010-07

Highly connected rigidity matroids have unique underlying graphs

Tibor Jordán, Viktória Kaszanitzky

Published in:
European Journal of Combinatorics Volume 34, Issue 2, February 2013, Pages 240-247

In this note we consider the following problem: is there a (smallest) integer k_d such that every graph G is uniquely determined by its d-dimensional rigidity matroid ℜ_d(G), provided that ℜ_d(G) is k_d-connected? Since ℜ₁(G) is isomorphic to the cycle matroid of G, a celebrated result of H. Whitney implies that k₁=3. We prove that if G is 7-vertex-connected then it is uniquely determined by ℜ₂(G). We use this result to deduce that k₂ ≤ 11, which gives an affirmative answer for d=2.

Bibtex entry:

@techreport{egres-10-07,

AUTHOR	=	{Jord{\'a}n, Tibor and Kaszanitzky, Vikt{\'o}ria},
TITLE	=	{Highly connected rigidity matroids have unique underlying graphs},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2010},
NUMBER	=	{TR-2010-07}

}