Extremal properties and bounds for the generalized algebraic connectivity of graphs in Euclidean spaces

Abstract

Graph rigidity—the study of vertex realizations in ℝ d and the motions that preserve the induced edge lengths—has been the focus of extensive research for decades. Its equivalency to graph connectivity for d = 1 is well known; thus it can be viewed as a generalization that incorporates geometric constraints. Graph connectivity is commonly quantified by the algebraic connectivity, the second-smallest eigenvalue of the Laplacian matrix. Recently, a graph invariant for quantifying graph rigidity in ℝ d , termed the generalized algebraic connectivity, was introduced. Recognizing the intrinsic relationship between rigidity and connectivity, this article presents new contributions. In particular, we introduce the d -rigidity ratio as a metric for expressing the level of rigidity of a graph in ℝ d relative to its connectivity. We show that this ratio is bounded and provide extremal examples. Additionally, we offer a new upper bound for the generalized algebraic connectivity that depends inversely on the diameter and on the vertex connectivity, thereby improving previous bounds. Moreover, we investigate the relationship between graph rigidity and the diameter—a measure of the graph’s overall extent. We provide the maximal diameter achievable by rigid graphs and show that generalized path graphs serve as extremal examples. Finally, we derive an upper bound for the generalized algebraic connectivity of generalized path graphs that (asymptotically) improves upon existing ones by a factor of four.