pith. sign in

arxiv: 1907.11874 · v1 · pith:YLODA65Bnew · submitted 2019-07-27 · 🧮 math.CO · math.SP

ell¹-Cospectrality of graphs

Alireza Abdollahi , Niloufar Zakeri This is my paper

Pith reviewed 2026-05-24 15:06 UTC · model grok-4.3

classification 🧮 math.CO math.SP
keywords cospectralitygraph spectraℓ¹ distancecomplete graphscomplete bipartite graphsspectral distance
0
0 comments X

The pith

The ℓ¹-cospectrality is computed exactly for complete graphs, empty graphs, near-stars, and complete bipartite graphs K_{n,n} and K_{n,n+1}.

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

The paper takes up a workshop problem that defines cs(G_n) as the smallest ℓ¹ distance from the ordered spectrum of G_n to the ordered spectrum of any non-isomorphic graph on the same number of vertices. It computes this minimum distance for the complete graph K_n, the empty graph nK_1, the graph K_2 joined to n-2 isolated vertices, and the two families of complete bipartite graphs K_{n,n} and K_{n,n+1}. A sympathetic reader would care because the resulting numbers give a precise metric measure of how isolated these standard spectra are inside the set of all possible spectra on n vertices.

Core claim

The authors determine the exact values of cs(K_n), cs(nK_1), cs(K_2+(n-2)K_1) for n≥2, cs(K_{n,n}), and cs(K_{n,n+1}) when distance is measured by the sum of absolute differences between correspondingly ordered eigenvalues.

What carries the argument

The function cs(G_n) defined as the minimum ℓ¹ distance between the non-increasingly sorted spectrum of G_n and the sorted spectrum of any non-isomorphic graph on n vertices.

If this is right

  • The spectrum of K_n lies at a known positive ℓ¹ distance from every other spectrum on n vertices.
  • The spectrum of the empty graph nK_1 likewise has a known positive minimum ℓ¹ distance to all non-isomorphic spectra.
  • The spectra of K_{n,n} and K_{n,n+1} each have explicitly determined minimum ℓ¹ distances to the nearest non-isomorphic spectra.
  • The value cs(K_2+(n-2)K_1) is known for every n≥2.

Where Pith is reading between the lines

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

  • The same computational approach might be applied to other small families such as cycles or paths to obtain further explicit cs values.
  • The ℓ¹ metric may identify different nearest-neighbor graphs than the squared-distance version of the same problem.
  • These exact distances supply concrete test cases for any future algorithm that enumerates or searches over graphs by spectral proximity.

Load-bearing premise

The eigenvalues are always sorted in non-increasing order and the distance is computed directly on this fixed ordering without any other pairing or multiplicity adjustment.

What would settle it

Any graph on n vertices not isomorphic to K_n whose ordered spectrum yields a strictly smaller sum of absolute differences from the spectrum of K_n than the value stated for cs(K_n).

read the original abstract

The following problem has been proposed in [Research problems from the Aveiro workshop on graph spectra, {\em Linear Algebra and its Applications}, {\bf 423} (2007) 172-181.]:\\ (Problem AWGS.4) Let $G_n$ and $G'_n$ be two nonisomorphic graphs on $n$ vertices with spectra $$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \;\;\;\text{and}\;\;\; \lambda'_1 \geq \lambda'_2 \geq \cdots \geq \lambda'_n,$$ respectively. Define the distance between the spectra of $G_n$ and $G'_n$ as $$\lambda(G_n,G'_n) =\sum_{i=1}^n (\lambda_i-\lambda'_i)^2 \;\;\; \big(\text{or use}\; \sum_{i=1}^n|\lambda_i-\lambda'_i|\big).$$ %Let $\epsilon$ be a nonnegative number. Graphs $G_n$ and $G'_n$ are $\epsilon$-cospectral if $\lambda(G_n,G'_n)\leq \epsilon$. Thus, $G_n$ %and $G'_n$ are $0$-cospectral if and only if $G_n$ and $G'_n$ are cospectral. Define the cospectrality of $G_n$ by $$\text{cs}(G_n) = \min\{\lambda(G_n,G'_n) \;:\; G'_n \;\;\text{not isomorphic to} \; G_n\}.$$ %Thus $\text{cs}(G_n) = 0$ if and only if $G_n$ has a cospectral mate. %This function measures how far apart the spectrum of a graph with $n$ vertices can be from the %spectrum of any other graph with $n$ vertices.\\ {\bf Problem A.} Investigate $\text{cs}(G_n)$ for special classes of graphs. In this paper we study Problem A for certain graphs with respect to the $\ell^1$-norm, i.e. $\sigma(G_n,G'_n)=\sum_{i=1}^n|\lambda_i-\lambda'_i|$. We find $\text{cs}(K_n)$, $\text{cs}(nK_1)$, $\text{cs}(K_2+(n-2)K_1)$ ($n\geq 2$), $\text{cs}(K_{n,n})$ and $\text{cs}(K_{n,n+1})$, where $K_n, nK_1, K_2+(n-2)K_1, K_{n,m} $ denote the complete graph on $n$ vertices, the null graph on $n$ vertices, the disjoint union of the $K_2$ with $n-2$ isolated vertices ($n\geq 2$), and the complete bipartite graph with parts of sizes $n$ and $m$, respectively.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript solves Problem A from the Aveiro workshop by determining the exact values of the ℓ¹-cospectrality cs(G_n) (minimal sum of absolute differences between sorted eigenvalue tuples) for the families K_n, nK_1, K_2+(n-2)K_1 (n≥2), K_{n,n} and K_{n,n+1}. The results are obtained by direct comparison of the known spectra of these graphs against all non-isomorphic graphs on the same vertex count.

Significance. The explicit determinations supply concrete, parameter-free benchmark values for cs under the ℓ¹ distance. Because the spectra of the listed graphs are classical and the distance is applied directly to the ordered tuples (thereby incorporating multiplicities by position), the claims rest on standard linear-algebraic facts rather than new numerical search or fitting; this strengthens their utility for subsequent work on spectral separation.

minor comments (3)
  1. [Abstract] Abstract: the numerical values of cs(K_n), cs(nK_1), etc., are asserted to have been found but are not displayed; stating the closed-form expressions in the abstract would improve immediate readability.
  2. [Introduction] §1 (or wherever the distance is redefined): the symbol σ is introduced for the ℓ¹ distance while the workshop problem uses λ; a single consistent symbol should be adopted throughout.
  3. The manuscript should include a short table or explicit list of the obtained cs values together with the graphs that realize the minimum, to facilitate verification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive evaluation of the manuscript, including the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper directly computes the ℓ¹-cospectrality values cs(G) for the listed families (complete graphs, empty graphs, near-complete graphs with one edge, and complete bipartite graphs) by evaluating the defined distance σ on sorted eigenvalue tuples against all non-isomorphic competitors on the same vertex count. The distance definition (sum of absolute differences on non-increasing spectra) is applied verbatim to known closed-form spectra of these graphs and their potential mates; no parameter fitting, self-referential definitions, or load-bearing self-citations appear in the derivation chain. The results are explicit evaluations of the min-distance problem statement rather than reductions to prior author results or ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard facts about real symmetric adjacency matrices having real eigenvalues that can be ordered; no new entities or fitted parameters are introduced in the abstract.

axioms (1)
  • standard math Adjacency matrices of undirected graphs are real symmetric and therefore have real eigenvalues that can be ordered decreasingly.
    Invoked by the problem definition that assumes ordered spectra λ1 ≥ … ≥ λn.

pith-pipeline@v0.9.0 · 6114 in / 1133 out tokens · 22250 ms · 2026-05-24T15:06:48.909664+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Abdollahi, Sh

    A. Abdollahi, Sh. Janbaz and M. R. Oboudi, Distance betwe en spectra of graphs, Linear Algebra Appl., 466 (2015), 401– 408

    work page 2015

  2. [2]

    Abdollahi and M

    A. Abdollahi and M. R. Oboudi, Cospectrality of graphs, L inear Algebra Appl., 451 (2014), 169–181

    work page 2014

  3. [3]

    Afkhami, M

    M. Afkhami, M. Hassankhani and K. Khashyarmanesh, Dista nce between the spectra of graphs with respect to normalized Laplacian spectra, Georgian Math. J., 26 (2017), No. 2, 227–234

    work page 2017

  4. [4]

    Cao and H

    D. Cao and H. Yuan, Graphs characterized by the second eig envalue, J. Graph Theory, 17 (1993), No. 3, 325–331

    work page 1993

  5. [5]

    Caporossi, D

    G. Caporossi, D. Cvetković, I. Gutman and P. Hansen, Vari able neighbourhood search for extermal graphs. 2. Finding g raphs with extremal energy, J. Chem. Inf. Comput. Sci., 39 (1999), 984– 996

    work page 1999

  6. [6]

    H. Choi, H. Lee, Y. Shen and Y. Shi, Comparing large-scale graphs based on quantum probability theory, Appl. Math. Com put., 358 (2019), 1–15

    work page 2019

  7. [7]

    D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, T heory and Application, Academic Press, Inc., New York, 1979

    work page 1979

  8. [8]

    K. Ch. Das and S. Sun, Distance between the normalized Lap lacian spectra of two graphs, Linear Algebra Appl., 530 (201 7), 305–321

    work page

  9. [9]

    H. Lin, D. Li and K. Ch. Das, Distance between distance spe ctra of graphs, Linear Multilinear Algebra, 65 (2017), No. 1 2, 2538–2550

    work page 2017

  10. [10]

    Godsil and G

    C. Godsil and G. Royle, Algebraic Graph Theory, Springe r, New York, 2001

    work page 2001

  11. [11]

    J. Gu, B. Hua and S. Liu, Spectral distances on graphs, Di screte Appl. Math., 190/191 (2015), 56–74

    work page 2015

  12. [12]

    Hakimi-Nezhaad and A

    M. Hakimi-Nezhaad and A. R. Ashrafi, Laplacian and norma lized Laplacian spectral distances of graphs, Southeast As ian Bull. Math., 37 (2013), No. 5, 731–744

    work page 2013

  13. [13]

    Jovanović, Some results on spectral distances of gra phs, Rev

    I. Jovanović, Some results on spectral distances of gra phs, Rev. Un. Mat. Argentina, 56 (2015), No. 2, 95–117

    work page 2015

  14. [14]

    Jovanović and Z

    I. Jovanović and Z. Stanić, Spectral distances of graph s, Linear Algebra Appl., 436 (2012), No. 5, 1425–1435. ℓ1-COSPECTRALITY OF GRAPHS 7

    work page 2012

  15. [15]

    Jovanović and Z

    I. Jovanović and Z. Stanić, Spectral distances of graph s based on their different matrix representations, Filomat, 28 (2014), No. 4, 723–734

    work page 2014

  16. [16]

    M. R. Oboudi, Cospectrality of complete bipartite grap hs, Linear Multilinear Algebra, 64 (2016), No. 12, 2491–249 7

    work page 2016

  17. [17]

    Petrović, On graphs whose second largest eigenvalue does not exceed √ 2 − 1, Univ

    M. Petrović, On graphs whose second largest eigenvalue does not exceed √ 2 − 1, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 4 (1993), 70–75

    work page 1993

  18. [18]

    J. H. Smith, Symmetry and multiple eigenvalues of graph s, Glasnik Mat., Ser. III, 12 (1977) No. 1, 3–8

    work page 1977

  19. [19]

    Stevanović, Research problems from the A veiro W orks hop on Graph Spectra, Linear Algebra Appl., 423 (2007), No

    D. Stevanović, Research problems from the A veiro W orks hop on Graph Spectra, Linear Algebra Appl., 423 (2007), No. 1 , 172–181

    work page 2007

  20. [20]

    Wilson and P

    R.C. Wilson and P. Zhu, A study of graph spectra for compa ring graphs and trees, Pattern Recogn., 41 (2008), 2833–284 1

    work page 2008

  21. [21]

    ZajÄĚc and J

    K. ZajÄĚc and J. Piersa, Eigenvalue Spectra of Function al Networks in fMRI Data and Artificial Models. In: Rutkowski L., Korytkowski M., Scherer R., Tadeusiewicz R., Zadeh L.A., Zu rada J.M. (eds) Artificial Intelligence and Soft Computing. ICAISC

    work page

  22. [22]

    Springer , Berlin, Heidelberg, 2013

    Lecture Notes in Computer Science, vol 7894. Springer , Berlin, Heidelberg, 2013. Department of Mathematics, University of Isf ahan, Isf ahan 81746-73441, Iran; and School of Mathematics, Insti- tute for Research in Fundamental Sciences (IPM), P.O. Box 19 395-5746, Tehran, Iran E-mail address : a.abdollahi@math.ui.ac.ir Department of Mathematics, Universi...

    work page 2013