|
The characterization of rigid graphs in $\R^d$ for $d\geq 3$ is a
major open problem in rigidity theory. The same holds for globally
rigid graphs. In this paper our goal is to give necessary and/or sufficient
conditions for the (global) rigidity of the square $G^2$ (and more generally, the power $G^k$) of
a graph $G$ in $\R^d$, for some values of $k,d$. Our work is motivated by some results
and conjectures of M. Cheung and W. Whiteley from 2008, the Molecular Theorem
of N. Katoh and S. Tanigawa from 2011, which settled the case of rigidity for $k=2, d=3$,
and the potential applications
in molecular conformation and sensor network localization.
We first characterize those graphs $G$ for which $G^{d}$ is globally
rigid in $\R^d$, for all $d\geq 1$, and then focus on the case
when $k=d-1$. We provide a new, direct proof for the
$3$-dimensional bar-and-joint version of the
Molecular Theorem ($d=3$) and a necessary condition for the rigidity
of $G^{d-1}$ in $\R^d$, for all $d\geq 3$. We conjecture that this
condition is also sufficient.
The global rigidity of square graphs in $\R^3$ is still an open problem.
We formulate a Molecular Global Rigidity Conjecture, which proposes
a combinatorial characterization of globally rigid square graphs in terms of vertex partitions
and edge count conditions. We prove that the condition is necessary.
For the general case we give a best possible connectivity based
sufficient condition by showing that if $G$ is $3$-edge-connected then
$G^{d-1}$ is globally rigid in $\R^d$, for all $d\geq 3$.
Our results imply affirmative answers to the conjectures of M. Cheung and
W. Whiteley in two special cases.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor and Tanigawa, Shin-ichi}, |
| TITLE | = | {Globally rigid powers of graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2021}, |
| NUMBER | = | {TR-2021-05} |