Conformally rigid graphs

Given a finite, simple, connected graph $G=(V,E)$ with $|V|=n$, we consider the associated graph Laplacian matrix $L = D - A$ with eigenvalues 0 = λ₁ < λ₂ ≤ ≤ λₙ. One can also consider the same graph equipped with positive edge weights w:E → R> 0 normalized to ∑e ∈ E wₑ = |E| and the associated weighted Laplacian matrix Lw. We say that G is conformally rigid if constant edge-weights maximize the second eigenvalue λ₂(w) of Lw over all w, and minimize λₙ(w') of Lw' over all $w'$, i.e., for all $w,w'$, λ₂(w) ≤ λ₂(1) ≤ λₙ(1) ≤ λₙ(w'). Conformal rigidity requires an extraordinary amount of symmetry in G. Every edge-transitive graph is conformally rigid. We prove that every distance-regular graph, and hence every strongly-regular graph, is conformally rigid. Certain special graph embeddings can be used to characterize conformal rigidity. Cayley graphs can be conformally rigid but need not be, we prove a sufficient criterion. We also find a small set of conformally rigid graphs that do not belong into any of the above categories; these include the Hoffman graph, the crossing number graph 6B and others. Conformal rigidity can be certified via semidefinite programming, we provide explicit examples.