|
In this paper we consider the 3-dimensional rigidity matroid of squares of graphs. These graphs are also called molecular graphs due to their importance in the study of flexibility in molecules. The Molecular Conjecture, posed in 1984 by T-S. Tay and W. Whiteley, indicates that determining independence (or more generally, computing the rank) in the rigidity matroids of squares of graphs may be tractable by combinatorial methods. We give sufficient conditions for independence and upper bounds on the rank of these matroids. In particular, we give a self-contained proof for the necessity part of the bar-and-joint version of the Molecular Conjecture. Our proofs are based on new structural results on forest covers of graphs as well as extensions of some basic techniques of combinatorial rigidity.
Bibtex entry:
| AUTHOR | = | {Jackson, Bill and Jord{\'a}n, Tibor}, |
| TITLE | = | {Rank and independence in the rigidity matroid of molecular graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2006}, |
| NUMBER | = | {TR-2006-02} |