On the $d$-dimensional algebraic connectivity of graphs

Abstract

The $d$-dimensional algebraic connectivity $a_d(G)$ of a graph $G=(V,E)$, introduced by Jordán and Tanigawa, is a quantitative measure of the $d$-dimensional rigidity of $G$ that is defined in terms of the eigenvalues of stiffness matrices (which are analogues of the graph Laplacian) associated to mappings of the vertex set $V$ into ${\mathbb{R}}^d$. Here, we analyze the $d$-dimensional algebraic connectivity of complete graphs. In particular, we show that, for $d\ge 3$, $a_d(K_{d+1})=1$, and for $n\ge 2d$, \[ \left\lceil\frac{n}{2d}\right\rceil-2d+1\leq a_d(K_n) \leq \frac{2n}{3(d-1)}+\frac{1}{3}. \]