View PDF HTML (experimental)

Abstract:This article presents new contributions to the study of graph rigidity and its interplay with fundamental graph invariants. Recently, a quantitative measure of graph rigidity in $\mathbb{R}^d$, termed the generalized algebraic connectivity, was introduced. This development extends the notion of algebraic connectivity---the second-smallest eigenvalue of the Laplacian matrix---which is commonly used to quantify graph connectivity. In this work, we show that the generalized algebraic connectivity is bounded above by the algebraic connectivity. To capture this relationship, we introduce the $d$-rigidity ratio, a normalized metric of a graph's rigidity relative to its connectivity. We also investigate the relationship between rigidity and the diameter---a measure of the graph's overall extent. In this context, we provide the maximal diameter achievable by rigid graphs and show that generalized path graphs serve as extremal examples. Moreover, we establish a new upper bound for the algebraic connectivity that depends inversely on the diameter and the vertex connectivity, improving upon previous bounds. Finally, we derive an upper bound for the algebraic connectivity of generalized path graphs that asymptotically improves existing ones by a factor of four.

Submission history

From: Juan Francisco Presenza [view email]
[v1] Wed, 21 May 2025 20:58:52 UTC (34 KB)
[v2] Fri, 4 Sep 2026 13:18:34 UTC (35 KB)