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



Abstract

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:

@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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2010},
NUMBER = {TR-2010-07}
}


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