Total Conformal Rigidity in Graphs

Abstract

We introduce and study a generalization of conformal rigidity for graphs. A graph is $k$-conformally rigid if the uniform edge weights simultaneously maximize the sum of the $k$ smallest nontrivial Laplacian eigenvalues and minimize the sum of the $k$ largest, over all normalized non-negative weight assignments. A graph that is $k$-conformally rigid for every $k$ is called totally conformally rigid. Our main result is a complete characterization: a graph is totally conformally rigid if and only if it is edge-rigid, meaning every canonical spectral embedding onto a Laplacian eigenspace is edge-isometric. We further show this is equivalent to all edges of the graph being pairwise Laplacian-cospectral, that is, the removal of any single edge yields a graph with the same Laplacian characteristic polynomial. Using semidefinite programming duality, we establish this equivalence and derive a polynomial-time algorithm for deciding edge-rigidity using only integer arithmetic. We provide a combinatorial characterization of edge-rigidity in terms of Laplacian walks and connect it to the walk-regularity of signed line graphs. We show that a graph is edge-rigid if and only if it is either $1$-walk-regular or $1$-walk-biregular, and we finally show an equivalence based on monotone gauges and gauge duality. As an application, we derive two non-trivial combinatorial consequences of total conformal rigidity, relating it to the number of spanning trees and the Kirchhoff index of the graph.

22 pages, 1 figure