Total Conformal Rigidity in Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917475040362496 |
|---|---|
| author | Assumpção, Henrique Coutinho, Gabriel Godsil, Chris |
| author_facet | Assumpção, Henrique Coutinho, Gabriel Godsil, Chris |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_08508 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Total Conformal Rigidity in Graphs Assumpção, Henrique Coutinho, Gabriel Godsil, Chris Combinatorics Optimization and Control 05C50, 90C22 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. |
| title | Total Conformal Rigidity in Graphs |
| topic | Combinatorics Optimization and Control 05C50, 90C22 |
| url | https://arxiv.org/abs/2605.08508 |