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 kd such that every graph G is uniquely determined by its d-dimensional rigidity matroid ℜd(G), provided that ℜd(G) is kd-connected? Since ℜ1(G) is isomorphic to the cycle matroid of G, a celebrated result of H. Whitney implies that k1=3. We prove that if G is 7-vertex-connected then it is uniquely determined by ℜ2(G). We use this result to deduce that k2 ≤ 11, which gives an affirmative answer for d=2.

Bibtex entry:

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

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