arxiv: 2605.08508 · v1 · submitted 2026-05-08 · 🧮 math.CO · math.OC

Recognition: no theorem link

Total Conformal Rigidity in Graphs

Chris Godsil, Gabriel Coutinho, Henrique Assump\c{c}\~ao

Pith reviewed 2026-05-12 01:08 UTC · model grok-4.3

classification 🧮 math.CO math.OC

keywords total conformal rigidityedge-rigid graphsLaplacian characteristic polynomialspectral embeddingwalk-regular graphsspanning treesKirchhoff index

0 comments

The pith

A graph is totally conformally rigid if and only if removing any edge leaves its Laplacian characteristic polynomial unchanged.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines total conformal rigidity as the property that uniform edge weights simultaneously maximize every sum of the k smallest nontrivial Laplacian eigenvalues and minimize every sum of the k largest, across all normalized nonnegative weight assignments. It proves this property holds exactly when the graph is edge-rigid, meaning every canonical embedding of vertices into a Laplacian eigenspace preserves edge lengths, and shows the same condition is equivalent to every pair of edges being Laplacian-cospectral. A reader should care because the equivalences supply both a polynomial-time recognition procedure that uses only integer arithmetic and direct combinatorial consequences for the number of spanning trees and the Kirchhoff index.

Core claim

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. This holds precisely when all edges are pairwise Laplacian-cospectral, that is, the Laplacian characteristic polynomial is identical after deletion of any single edge. The equivalences follow from semidefinite programming duality applied to the eigenvalue-sum optimization problems, and they further imply that edge-rigid graphs are exactly the 1-walk-regular or 1-walk-biregular graphs.

What carries the argument

Edge-rigidity, the requirement that every canonical embedding of the graph into a Laplacian eigenspace maps all edges to segments of equal length, serves as the central mechanism that equates uniform-weight optimality with invariance of the Laplacian spectrum under single-edge removal.

If this is right

Edge-rigid graphs can be recognized in polynomial time by an algorithm that performs only integer arithmetic.
A graph is edge-rigid if and only if it is 1-walk-regular or 1-walk-biregular.
Total conformal rigidity produces explicit relations between the number of spanning trees and the edge structure of the graph.
The Kirchhoff index of an edge-rigid graph satisfies corresponding identities derived from the spectral invariance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The walk-regularity characterization may allow an exhaustive enumeration of all totally conformally rigid graphs on a small number of vertices.
The duality technique could be adapted to optimize other linear combinations of Laplacian eigenvalues over weight assignments.
Random graphs could be sampled to estimate how frequently the pairwise cospectrality condition occurs.

Load-bearing premise

The equivalences assume that semidefinite programming duality holds without degeneracy for the normalized nonnegative weight assignments and that the graph meets the implicit connectivity or size conditions needed for the embeddings and characteristic polynomials to behave uniformly.

What would settle it

A graph in which every single-edge deletion produces the same Laplacian characteristic polynomial yet at least one canonical embedding into an eigenspace stretches some edges relative to others would falsify the claimed equivalences.

Figures

Figures reproduced from arXiv: 2605.08508 by Chris Godsil, Gabriel Coutinho, Henrique Assump\c{c}\~ao.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper cleanly equates total conformal rigidity to edge-rigidity and pairwise Laplacian-cospectrality, with a poly-time integer-arithmetic test and walk-based combinatorial links.

read the letter

The main thing to know is that the authors define total conformal rigidity and prove it is equivalent to edge-rigidity (every canonical Laplacian spectral embedding is edge-isometric) and to every pair of edges being Laplacian-cospectral (removing any one edge leaves the same characteristic polynomial). They start from k-conformal rigidity, where uniform weights simultaneously maximize the sum of the k smallest nontrivial Laplacian eigenvalues and minimize the sum of the k largest, over normalized non-negative weights, and total rigidity requires this for all k. They derive the equivalences via SDP duality and also give a direct combinatorial route through Laplacian walks and signed line graphs, showing edge-rigid graphs are precisely the 1-walk-regular or 1-walk-biregular ones. They add a monotone-gauge duality perspective and extract two concrete consequences for the number of spanning trees and the Kirchhoff index. The poly-time decision algorithm that uses only integer arithmetic is a clear practical plus. The work sits squarely inside spectral graph theory and extends existing notions of rigidity and cospectrality in a controlled way. The combinatorial characterizations and the algorithm are the parts that feel most reusable. The main soft spot is the SDP duality step. The feasible set is a simplex, and if the optimum sits on a face or strict feasibility fails for some graphs, the duality argument could need extra justification to guarantee the uniform weight is recovered uniquely. The paper supplies an independent walk-based proof, which probably rescues the equivalences, but the duality route still needs to be checked for degeneracy cases. This is for readers already comfortable with Laplacian spectra, cospectrality, and combinatorial optimization on graphs. Someone who works on rigidity or spectral embeddings will see the value in the equivalences and the algorithm. It has enough new definitions, verifiable claims, and applications to deserve a serious referee. I would send it to peer review; the core characterization and the combinatorial side are worth a detailed check.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces k-conformal rigidity for graphs, where uniform edge weights simultaneously maximize the sum of the k smallest nontrivial Laplacian eigenvalues and minimize the sum of the k largest over normalized non-negative weight assignments. Total conformal rigidity holds when this is true for every k. The main result is a complete characterization: total conformal rigidity is equivalent to edge-rigidity (every canonical spectral embedding onto a Laplacian eigenspace is edge-isometric) and to pairwise Laplacian-cospectrality (removing any single edge preserves the Laplacian characteristic polynomial). These equivalences are established via semidefinite programming duality, yielding a polynomial-time algorithm using integer arithmetic. Further results include a combinatorial characterization in terms of Laplacian walks and walk-regularity of signed line graphs (edge-rigid graphs are precisely the 1-walk-regular or 1-walk-biregular graphs), an equivalence via monotone gauges and gauge duality, and applications relating the property to the number of spanning trees and the Kirchhoff index.

Significance. If the equivalences hold, the work provides a valuable link between variational characterizations of Laplacian spectra, combinatorial rigidity notions, and cospectrality properties, with algorithmic consequences that are computationally attractive. The combinatorial characterization via walks and the applications to spanning trees and Kirchhoff index add structural and applied value. The derivation of a polynomial-time decision procedure from SDP duality is a positive feature, as is the explicit connection to signed line graphs.

major comments (2)

[Section 3, Theorem 3.1] Section 3, Theorem 3.1 and the surrounding SDP duality argument: the claimed equivalences between total conformal rigidity, edge-rigidity, and pairwise Laplacian-cospectrality rest on strong duality for the primal SDP of maximizing/minimizing sums of Laplacian eigenvalues over the simplex of normalized non-negative edge weights. The manuscript does not verify the Slater condition (strict feasibility in the relative interior of the feasible set). For many graphs the Laplacian quadratic-form constraints may force the optimum onto a face of the simplex where the non-negativity multipliers are degenerate, risking a positive duality gap or failure of complementary slackness to recover the uniform weight. This directly affects the central characterization and the polynomial-time algorithm.
[Section 5] Section 5, combinatorial characterization (edge-rigidity iff 1-walk-regular or 1-walk-biregular): the equivalence is stated in terms of Laplacian walks and signed line graphs, but the argument does not explicitly treat the case of multiple eigenvalues or graphs with bridges, where the walk-count conditions may not imply the required cospectrality of all edges. A concrete check on a small non-regular example would confirm the claim.

minor comments (2)

[Abstract] Abstract and Section 2: the term 'canonical spectral embedding' is used before a formal definition or reference is given; a one-sentence clarification would improve accessibility.
[Section 6] Section 6 (applications): the consequences for the number of spanning trees and Kirchhoff index are asserted but lack an explicit formula or numerical illustration on a small edge-rigid graph.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. Below we respond point-by-point to the major comments.

read point-by-point responses

Referee: Section 3, Theorem 3.1 and the surrounding SDP duality argument: the claimed equivalences between total conformal rigidity, edge-rigidity, and pairwise Laplacian-cospectrality rest on strong duality for the primal SDP of maximizing/minimizing sums of Laplacian eigenvalues over the simplex of normalized non-negative edge weights. The manuscript does not verify the Slater condition (strict feasibility in the relative interior of the feasible set). For many graphs the Laplacian quadratic-form constraints may force the optimum onto a face of the simplex where the non-negativity multipliers are degenerate, risking a positive duality gap or failure of complementary slackness to recover the uniform weight. This directly affects the central characterization and the polynomial-time algorithm.

Authors: We appreciate the referee highlighting the need to verify the Slater condition. In the SDP formulation, the feasible set is the simplex intersected with affine constraints on the weighted Laplacian quadratic forms. The uniform weight vector lies in the relative interior: small positive perturbations of the weights preserve the eigenvalue sum equalities while keeping all weights strictly positive, owing to the continuity of the spectrum. We will add a short lemma in Section 3 establishing strict feasibility for connected graphs, confirming zero duality gap and recovery of uniform weights via complementary slackness. This strengthens the proof of Theorem 3.1 and leaves the polynomial-time algorithm unchanged. revision: yes
Referee: Section 5, combinatorial characterization (edge-rigidity iff 1-walk-regular or 1-walk-biregular): the equivalence is stated in terms of Laplacian walks and signed line graphs, but the argument does not explicitly treat the case of multiple eigenvalues or graphs with bridges, where the walk-count conditions may not imply the required cospectrality of all edges. A concrete check on a small non-regular example would confirm the claim.

Authors: The proof in Section 5 works with the full eigenspace projection, so multiplicity is handled by the invariant subspace rather than individual eigenvectors. For graphs with bridges the signed line-graph structure encodes the disconnection, ensuring walk counts distinguish cospectrality. To address the request explicitly, we will add a verification example in the revised Section 5: the non-regular graph formed by a triangle with a pendant edge attached to one vertex. Direct computation of the 1-walk counts in the signed line graph confirms that 1-walk-biregularity holds precisely when all edges are pairwise Laplacian-cospectral. This example covers both multiplicity (if any) and the bridge case. revision: yes

Circularity Check

0 steps flagged

No significant circularity; equivalences rely on external SDP duality and combinatorial properties

full rationale

The paper defines k-conformal rigidity variationally via uniform weights optimizing eigenvalue sums, then proves equivalence to edge-rigidity (spectral embeddings being edge-isometric) and pairwise Laplacian-cospectrality using standard SDP duality and external facts about walks and cospectrality. No load-bearing step reduces by construction to a fitted input, self-definition, or self-citation chain; the central claims remain independent of the target result. A minor self-citation (if present in full text) is not load-bearing per the reader's assessment and does not trigger higher scores.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of the graph Laplacian and its spectrum together with duality in convex optimization. No numerical parameters are fitted to data. The new definitions (k-conformal rigidity, edge-rigidity) are introduced explicitly rather than postulated as unexplained entities.

axioms (2)

standard math Laplacian matrices of weighted graphs have well-defined eigenvalues, eigenspaces, and characteristic polynomials that behave predictably under edge removal.
Invoked throughout the definitions of conformal rigidity, cospectrality, and spectral embeddings.
domain assumption Semidefinite programming duality holds and yields exact certificates for the optimality conditions in the normalized weight space.
Used to establish the equivalence between the spectral optimality definition and the combinatorial edge-rigidity condition.

pith-pipeline@v0.9.0 · 5567 in / 1600 out tokens · 85264 ms · 2026-05-12T01:08:24.463517+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

[1]

Ben-Tal.Lectures on modern convex optimization : analysis, algorithms, and engineering applications

A. Ben-Tal.Lectures on modern convex optimization : analysis, algorithms, and engineering applications. en. MPS-SIAM series on optimization. Mathematical Programming Society, 2001

work page 2001
[2]

Bhatia.Matrix Analysis

R. Bhatia.Matrix Analysis. Graduate Texts in Mathematics 169. New York: Springer, 1997. 347 pp.isbn: 978-0-387-94846-1

work page 1997
[3]

Boyd and L

S.P. Boyd and L. Vandenberghe.Convex Optimization. Berichte über verteilte messysteme pt. 1. Cambridge University Press, 2004.isbn: 9780521833783. url:https://books.google.com.br/books?id=mYm0bLd3fcoC

work page 2004
[4]

Theuniquenessandnonuniquenessoftriangularassociationschemes

L.Chang.“Theuniquenessandnonuniquenessoftriangularassociationschemes”. In:Science Record (Peking)3.12 (1959), pp. 604–613

work page 1959
[5]

Onk-walk-regular graphs

C. Dalfó, M. A. Fiol, and E. Garriga. “Onk-walk-regular graphs”. In:Electron. J. Comb.16.1 (2009), R47. 20

work page 2009
[6]

Which graphs are determined by their spectrum?

E. R. van Dam and W. H. Haemers. “Which graphs are determined by their spectrum?” en. In:Linear Algebra Appl.373 (2003), pp. 241–272

work page 2003
[7]

On a theorem of Weyl concerning eigenvalues of linear transformations I

K. Fan. “On a theorem of Weyl concerning eigenvalues of linear transformations I”. en. In:Proc. Natl. Acad. Sci. U. S. A.35.11 (1949), pp. 652–655

work page 1949
[8]

Spectral embedding of weighted graphs

I. Gallagher et al. “Spectral embedding of weighted graphs”. en. In:J. Am. Stat. Assoc.(2023), pp. 1–10

work page 2023
[9]

Equiarboreal graphs

C. Godsil. “Equiarboreal graphs”. en. In:Combinatorica1.2 (1981), pp. 163– 167

work page 1981
[10]

Constructing cospectral graphs

C. Godsil and B. D. McKay. “Constructing cospectral graphs”. en. In:Aequa- tiones Math.25.1 (1982), pp. 257–268

work page 1982
[11]

Feasibility conditions for the existence of walk- regular graphs

C. Godsil and B. D. McKay. “Feasibility conditions for the existence of walk- regular graphs”. en. In:Linear Algebra Appl.30 (1980), pp. 51–61

work page 1980
[12]

Godsil and G.F

C. Godsil and G.F. Royle.Algebraic Graph Theory. Graduate Texts in Mathe- matics. Springer, 2001.isbn: 9780387952208.url: https://books.google. com.br/books?id=pYfJe-ZVUyAC

work page 2001
[13]

Godsil, W

C. Godsil, W. Sun, and X. Zhang.Cospectral graphs obtained by edge deletion

work page
[14]

arXiv: 2302.03854 [math.CO] .url: https://arxiv.org/abs/2302. 03854

work page arXiv
[15]

Gouveia, S

J. Gouveia, S. Steinerberger, and R. R. Thomas.Conformal Rigidity and Spectral Embeddings of Graphs. 2025. arXiv: 2506.20541 [math.CO] .url: https://arxiv.org/abs/2506.20541

work page arXiv 2025
[16]

Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen

Hs. H. Günthard and H. Primas. “Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen”. In:Helvetica Chimica Acta39.6 (1956), pp. 1645–1653.doi: https://doi.org/10.1002/ hlca.19560390623. eprint: https://onlinelibrary.wiley.com/doi/pdf/ 10.1002/hlca.19560390623 .url: https://onlinelibrary.wiley.com/ doi/abs/10.100...

work page doi:10.1002/hlca.19560390623 1956
[17]

On the sum of Laplacian eigenvalues of graphs

W H Haemers, A Mohammadian, and B Tayfeh-Rezaie. “On the sum of Laplacian eigenvalues of graphs”. en. In:Linear Algebra Appl.432.9 (2010), pp. 2214–2221

work page 2010
[18]

Anr-dimensional quadratic placement algorithm

K. M. Hall. “Anr-dimensional quadratic placement algorithm”. en. In:Manage. Sci.17.3 (1970), pp. 219–229

work page 1970
[19]

Horn and C.R

R.A. Horn and C.R. Johnson.Matrix Analysis. Cambridge University Press, 1990.isbn: 9780521386326.url: https://books.google.com.br/books?id= PlYQN0ypTwEC

work page 1990
[20]

Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird

G. Kirchhoff. “Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird”. In: Annalen der Physik148.12 (1847), pp. 497–508

work page
[21]

Resistance distance

D. J. Klein and M. Randić. “Resistance distance”. In:Journal of Mathematical Chemistry12.1 (1993), pp. 81–95.doi:10.1007/BF01164627. 21

work page doi:10.1007/bf01164627 1993
[22]

Diffusion Kernels on Graphs and Other Dis- crete Input Spaces

R. I. Kondor and J. D. Lafferty. “Diffusion Kernels on Graphs and Other Dis- crete Input Spaces”. In:Proceedings of the Nineteenth International Conference on Machine Learning. ICML ’02. Morgan Kaufmann Publishers Inc., 2002, pp. 315–322.isbn: 1558608737

work page 2002
[23]

Spectral embedding of graphs

B. Luo, R. C. Wilson, and E. R. Hancock. “Spectral embedding of graphs”. en. In:Pattern Recognit.36.10 (2003), pp. 2213–2230

work page 2003
[24]

Isoperimetric numbers of graphs

B. Mohar. “Isoperimetric numbers of graphs”. In:Journal of Combinatorial Theory, Series B47.3 (1989), pp. 274–291.issn: 0095-8956.doi: https://doi. org/10.1016/0095-8956(89)90029-4 .url: https://www.sciencedirect. com/science/article/pii/0095895689900294

work page doi:10.1016/0095-8956(89)90029-4 1989
[25]

The Laplacian spectrum of graphs

B. Mohar. “The Laplacian spectrum of graphs”. In:Graph Theory, Combina- torics, and Applications2 (1991), pp. 871–898

work page 1991
[26]

Nesterov.Interior-point polynomial algorithms in convex programming

Y. Nesterov.Interior-point polynomial algorithms in convex programming. Society for Industrial & Applied Mathematics, 1994

work page 1994
[27]

Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming

N. B. Proenca, M. K. de Carli Silva, and G. Coutinho. “Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming”. In:SIAM Journal on Discrete Mathematics35.4 (2021), pp. 2880–2907

work page 2021
[28]

R. T. Rockafellar.Convex analysis. Vol. 28. Princeton university press, 1997

work page 1997
[29]

A statistical interpretation of spectral embedding: The generalised random dot product graph

P. Rubin-Delanchy et al. “A statistical interpretation of spectral embedding: The generalised random dot product graph”. en. In:J. R. Stat. Soc. Series B Stat. Methodol.84.4 (2022), pp. 1446–1473

work page 2022
[30]

Almost all trees are cospectral

A. J. Schwenk. “Almost all trees are cospectral”. In:New Directions in the Theory of Graphs. Ed. by Frank Harary. Academic Press, 1973, pp. 275–307

work page 1973
[31]

Spectral Sparsification of Graphs

D. A. Spielman and S. Teng. “Spectral Sparsification of Graphs”. In:SIAM J. Comput.40.4 (2011), pp. 981–1025

work page 2011
[32]

Conformally rigid graphs

S. Steinerberger and R. R. Thomas. “Conformally rigid graphs”. en. In:J. Graph Theory109.3 (2025), pp. 366–386

work page 2025
[33]

Spectral embedding of signed networks

Q. Zheng and D. B. Skillicorn. “Spectral embedding of signed networks”. In:Proceedings of the 2015 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2015, pp. 55–63. 22

work page 2015