2024/02/19 by Steinerberger, Stefan, Thomas, Rekha R. · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Spectral Theory (math.SP)
paper · doi:10.48550/arxiv.2402.11758
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 = λ1 < λ2 ≤ … ≤ λn. One can also consider the same graph equipped with positive edge weights w:E → ℝ> 0 normalized to ∑e ∈ E we = |E| and the associated weighted Laplacian matrix Lw. We say that G is conformally rigid if constant edge-weights maximize the second eigenvalue λ2(w) of Lw over all w, and minimize λn(w') of Lw' over all w', i.e., for all w,w', λ2(w) ≤ λ2(1) ≤ λn(1) ≤ λn(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.