Let be the weighted Laplacian matrix defined for a simple connected graph on vertices with edge set and edge weights defined by
(1)
|
where means . Let have eigenvalues
(2)
|
and let be the vector of length consisting of all 1's. Steinerberger and Thomas (2024) then call a graph conformally rigid if its weighted Laplacian eigenvalues satisfy
(3)
|
for all edge weights and that are nonnegative and normalized such that
(4)
|
where is the edge count of .
Conformal rigidity reflects an extraordinary amount of symmetry in a graph (Steinerberger and Thomas 2024).
All connected edge-transitive graphs and distance-regular graphs are conformally rigid (Steinerberger and Thomas 2024). Since connected distance-regular graphs are strongly regular, connected strongly regular graphs are also conformally rigid.
There are no conformally rigid graphs that are edge-transitive or distance-regular on 10 or fewer vertices (E. Weisstein, Mar. 1, 2024). The smallest known conformally rigid graph that is not edge-transitive or distance-regular is the Hoffman graph on 16 vertices (Steinerberger and Thomas 2024). The following table, which extends the results of Steinerberger and Thomas (2024), lists all 13 known such exceptionally conformally rigid graphs (E. Weisstein, Feb. 23, 2024).
non-ET, non-DR, CR graph | |
16 | Hoffman graph |
18 | circulant graph |
20 | smallest cubic crossing number graph CNG6B |
20 | 565-Haar graph |
20 | (10, 3)-incidence graph 3 |
20 | (10, 3)-incidence graph 4 |
20 | 20-noncayley vertex-transitive graph 10 |
24 | distance-2 graph of the 24-Klein graph |
24 | 24-noncayley vertex-transitive graph 23 |
40 | (20, 8)-accordion graph |
48 | (0, 2)-bipartite graph (7, 1) |
48 | (0, 2)-bipartite graph (7, 2) |
120 | 120-Klein graph |
Some Cayley graphs are conformally rigid and others are not. Steinerberger and Thomas (2024) provide a sufficient condition for Cayley graphs to be conformally rigid.
Circulant graphs are not conformally rigid for (Steinerberger and Thomas 2024), meaning antiprism graphs (other than the octahedral graph) are also not conformally rigid.