Pith. sign in

REVIEW 3 major objections 5 minor 109 references

On Spectral Graph Determination

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper's central claim is a new proof that every Turán graph is uniquely determined by its adjacency spectrum, based on a closed-form formula for the spectrum.

desk verdict A useful survey with one correct new proof (Turán graphs are A-DS) and one new proof that is wrong as written (the complete bipartite DS characterization), plus a misstated corollary. read the letter →

arxiv 2412.20775 v6 pith:6QJKEZQ5 submitted 2024-12-30 math.CO

Igal Sason , Noam Krupnik , Suleiman Hamud , Abraham Berman This is my paper · ORCID
classification math.CO MSC 05C5005C7505C76
keywords spectralgraphtheorydeterminationcospectralnonisomorphicgraphsHaemers'conjectureTuránoperationsadjacencyspectrumDS
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper surveys the field of spectral graph determination—the question of which graphs are uniquely identified, up to isomorphism, by their list of eigenvalues—and adds new proofs of three known results within it. Its central contribution is a new proof that every Turán graph $T(n,k)$, the complete $k$-partite graph on $n$ vertices with part sizes as equal as possible, is determined by its adjacency spectrum (A-DS). The proof rests on a closed-form formula for the spectrum of these graphs, and it offers a different route from the earlier proof of the same theorem. The paper also gives new proofs that complete bipartite graphs $K_{p,q}$ are A-DS exactly when the pair $\{p,q\}$ minimizes the arithmetic mean among factor pairs with product $pq$, and that the Petersen graph is A-DS.

What carries the argument

The load-bearing object is the closed-form adjacency spectrum of irregular Turán graphs (Eq. (4.15)). The derivation writes an uneven Turán graph as the join of the regular complete multipartite graphs $K_q^{k-s}$ and $K_{q+1}^s$ (with $k-s$ parts of size $q$ and $s$ parts of size $q+1$), so the join-spectrum formula (Lemma 4.17) converts their spectra into the spectrum of the join: the eigenvalues $[-q-1]^{s-1}$, $[-q]^{k-s-1}$, $[0]^{n-k}$, plus two further eigenvalues given by a radical expression, where $[x]^m$ means the eigenvalue $x$ with multiplicity $m$. The resulting spectral shape—one positive eigenvalue, many zero eigenvalues, and a controlled number of negative eigenvalues—lets the proof invoke the characterization of graphs with one positive eigenvalue and use Cauchy interlacing to rule out a clique of size $k+1$.

What would settle it

A direct check would diagonalize the adjacency matrix of an uneven Turán graph such as $T(17,7)$ and compare the result with Eq. (4.15), which predicts the eigenvalues $[-3]^2, [-2]^3, [0]^{10}, 6(1+\sqrt{2}), 6(1-\sqrt{2})$ for this case. A mismatch in any eigenvalue or multiplicity—for instance a different number of negative eigenvalues than the formula allows—would refute Theorem 4.18 and with it the proof of Theorem 4.21.

Watch

Extended reading notes

Core claim

The main new result, Theorem 4.21, asserts that every Turán graph $T(n,k)$ is determined by its adjacency spectrum: no non-isomorphic graph shares its eigenvalues. The engine is Theorem 4.18, which gives an explicit closed-form spectrum for $T(n,k)$ by viewing it as the join of two regular complete multipartite graphs and applying the join-spectrum formula. From that spectrum, a graph cospectral with $T(n,k)$ is shown to have exactly one positive eigenvalue and at most $k-1$ negative eigenvalues; the one-positive-eigenvalue characterization forces it to be a complete multipartite graph plus isolated vertices, Turán's theorem forces the part sizes to be the balanced sizes $q$ and $q+1$, and the vertex count recovers the number of large parts. Hence the cospectral graph is $T(n,k)$ itself. The same circle of ideas yields the AM-minimizer characterization for complete bipartite graphs and a short proof that the Petersen graph is A-DS.

Load-bearing premise

The argument rests on the closed-form spectrum for uneven Turán graphs being correct, in particular on its claim about how many negative and zero eigenvalues such a graph has; if that spectrum were wrong, the interlacing and one-positive-eigenvalue steps that identify a cospectral graph would no longer be forced.

Editorial extensions

If this is right

  • Every Turán graph $T(n,k)$ is A-DS: any graph whose adjacency spectrum matches $T(n,k)$ is isomorphic to it.
  • The closed-form spectrum in Theorem 4.18 makes the number of edges, triangles, and parts of a graph cospectral with $T(n,k)$ readable directly from eigenvalues.
  • For complete bipartite graphs, $K_{p,q}$ is A-DS exactly when $\{p,q\}$ is an AM-minimizer, so almost all complete bipartite graphs are not A-DS.
  • The Petersen graph is A-DS, as the complement of the DS line graph of $K_5$.
  • A connected strongly regular graph is A-DS exactly when no other strongly regular graph has its parameter vector $(n,d,\lambda,\mu)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same closed-form spectrum provides a direct testing ground for whether Turán graphs are determined by Laplacian, signless Laplacian, or normalized Laplacian spectra, a question the paper leaves open.
  • The AM-minimizer condition for complete bipartite graphs suggests a broader principle: among graphs assembled from equal blocks, spectral uniqueness may track how evenly the total size is split; testing this on other complete multipartite graphs with unequal parts is a natural next step.
  • The paper's closing speculation that symmetry anticorrelates with being DS could be checked against the full census of graphs up to order 12 by comparing automorphism-group size with DS status.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. This paper is a survey of spectral graph determination, focusing on adjacency spectra, with three advertised new proofs of known results: the characterization of A-DS complete bipartite graphs (Theorem 4.7), the proof that all Turán graphs are A-DS (Theorem 4.21), and a proof that the Petersen graph is DS (Corollary 4.32). The Turán proof is built on a claimed closed-form spectrum for Turán graphs (Theorem 4.18), which is in turn derived from Butler's join-spectrum formula. The paper also surveys cospectrality with respect to Laplacian, signless Laplacian, and normalized Laplacian matrices, and constructions of non-isomorphic cospectral graphs.

Significance. If the new proofs were all correct, the paper would provide a valuable alternative proof of the known theorem that every Turán graph is A-DS, based on a self-contained derivation of the Turán spectrum, and would offer new confirmatory proofs of other known characterizations. The Turán proof and the spectrum derivation appear sound and constitute a genuine contribution. However, the paper contains load-bearing errors in the complete bipartite section: the proposed cospectral witness in Theorem 4.7(2) is not cospectral, and Corollary 4.9 is false. In addition, Remark 4.19 misstates the negative-eigenvalue count for irregular Turán graphs. These defects undermine part of the paper's advertised new material, although the main Turán result survives.

major comments (3)
  1. [§4.2, Corollary 4.9] The asserted cospectral witness G = K_{a,b}∨K_r is not cospectral with K_{p,q}. K_{a,b} is not regular, so Lemma 4.17 does not apply; indeed K_{a,b}∨K_r is the complete tripartite graph K_{a,b,r}, whose adjacency matrix has p+q-3 zero eigenvalues when a,b,r are positive, not p+q-2, and whose nonzero spectrum is not {−√pq, [0]^{p+q-2}, √pq}. For example, with p=1, q=4, and (a,b,r)=(2,2,1), the graph K_{2,2}∨K_1 has spectrum {−2, [0]^2, 1±√5} and 8 edges, whereas K_{1,4} has spectrum {−2, [0]^3, 2} and 4 edges. Thus the proof of the 'only if' direction of Theorem 4.7(2) is invalid. The correct cospectral mate is the disjoint union K_{a,b}∪(rK_1).
  2. [§4.3.1, Remark 4.19] Corollary 4.9 is false as stated. For n=4, both K_{1,3} and K_{2,2} are A-DS; for n=6, all three of K_{1,5}, K_{2,4}, and K_{3,3} are A-DS. The proof conflates the vertex count n with the product pq. The AM-minimizer condition fixes the product pq, not the order p+q, so several complete bipartite graphs of the same order can each be AM-minimizers for their own products. This claim and its proof require substantive correction or replacement.
  3. [§4.2, Theorem 4.7(2)] Remark 4.19 states that an irregular Turán graph T(n,k) has k−2 negative eigenvalues, but this is inconsistent with Theorem 4.15 and with the paper's own Example 4.20: for T(17,7), the printed spectrum includes 6(1−√2) < 0, giving k−1 = 6 negative eigenvalues in total. Indeed, the smaller member of the special pair in Eq. (4.15) is negative, so the count is k−1. The proof of Theorem 4.21 uses only the bound 'at most k−1 negative eigenvalues', which remains true, but the remark must be corrected and its role in the referencing of Lemma 4.23 clarified.
minor comments (5)
  1. [§2.3.1] The word 'normialized' in the introductory sentence of Section 2.3.1 should be 'normalized'.
  2. [§4.2, Theorem 4.7(2)] In the corrected proof of Theorem 4.7(2), after using the disjoint union, the step 'both equalities GM(a,b)=GM(p,q) and AM(a,b)=AM(p,q) can be satisfied simultaneously if and only if {a,b}={p,q}' should be justified explicitly, though it is standard.
  3. [§4.3.1, Lemma 4.23] The proof of Lemma 4.23 refers to Remark 4.19 for the negative-eigenvalue count; since Remark 4.19 is incorrect, the reference should be replaced by a direct appeal to Theorem 4.18 or Theorem 4.15.
  4. [References] In reference [71], the title contains 'external problem' and should read 'extremal problem'.
  5. [§6.2] The speculative paragraph connecting automorphism group size with the DS property is explicitly hedged, but it may be better placed in a 'discussion' or 'outlook' section with a clearer caveat that it is not a theorem.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new proofs are self-contained derivations from external theorems.

full rationale

The paper's central contribution, the alternative proof that Turán graphs are A-DS (Theorem 4.21), derives the spectrum of T(n,k) (Theorem 4.18) from Butler's join-spectrum formula (Lemma 4.17) and the known spectrum of regular complete multipartite graphs (Corollary 4.16 via Esser–Harary), then proves uniqueness using Smith's theorem (Theorem 4.22), Turán's theorem (Theorem 4.13), Cauchy interlacing, and the paper's own Lemmas 4.23–4.27. None of these steps assumes the A-DS conclusion; the eigenvalue-count bound used in Lemma 4.23 is weaker than (and implied by) the derived spectrum, so the argument is not circular even where Remark 4.19 overcounts. The complete bipartite characterization (Theorem 4.7) is proved from the standard K_{p,q} spectrum and the AM-GM characterization of AM-minimizers, with no fitted parameter renamed as a prediction; its asserted cospectral mate in Eq. (4.6) is mathematically incorrect for irregular K_{a,b}, but that is a correctness defect, not a circularity. The Petersen graph proof (Corollary 4.32) rests on the known DS property of ℓ(K5) and the complement rule from the external literature. Self-citations in the survey (e.g., [14,25,31,41]) report prior results but are not load-bearing in the new derivations, which rely on independent, published external theorems. Consequently the derivation chain is self-contained and there is no circularity to report.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities. The new proofs rest on standard external theorems in matrix theory and extremal graph theory, all cited in the paper.

assumptions (4)
  • standard math Cauchy Interlacing Theorem (Theorem 2.3)
    Used to constrain eigenvalues of induced subgraphs in the proofs of Theorems 4.7 and 4.21.
  • domain assumption Turán's Graph Theorem (Theorem 4.13)
    Used to argue that a graph with more edges than T(n,k) must contain a (k+1)-clique, in Lemmas 4.23-4.27.
  • domain assumption Smith's theorem (Theorem 4.22): a graph with exactly one positive eigenvalue is a complete multipartite graph plus isolated vertices
    External black-box result that is the starting point of the Turán A-DS proof.
  • standard math Butler's join spectrum formula (Lemma 4.17)
    Used to derive the adjacency spectrum of Turán graphs in Theorem 4.18.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Spectral Graph Determination." pith.science (2026). https://pith.science/paper/6QJKEZQ5

@misc{pith2026241220775,
  author       = {Pith},
  title        = {Pith review of: On Spectral Graph Determination},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6QJKEZQ5}},
  note         = {Machine review of arXiv:2412.20775}
}
read the original abstract

The study of spectral graph determination is a fascinating area of research in spectral graph theory and algebraic combinatorics. This field focuses on examining the spectral characterization of various classes of graphs, developing methods to construct or distinguish cospectral nonisomorphic graphs, and analyzing the conditions under which a graph's spectrum uniquely determines its structure. This paper presents an overview of both classical and recent advancements in these topics, along with newly obtained proofs of some existing results, which offer additional insights.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

109 extracted references · 57 canonical work pages

  1. [1]

    A. E. Brouwer and W. H. Haemers, Spectra of Graphs , Springer Science & Business Media, 2011. https://doi.org/10.1007/978-1-4614-1939-6

    doi:10.1007/978-1-4614-1939-6 2011

  2. [2]

    F. R. K. Chung, Spectral Graph Theory, American Mathematical Society, 1997. https://doi.org/10.1090/cbms/092

    doi:10.1090/cbms/092 1997

  3. [3]

    D. M. Cvetkovi ´c, M. Doob, and H. Sacs.Spectra of Graphs: Theory and Applications, Johann Ambrosius Barth Verlag, third edition, 1995

    1995

  4. [4]

    D. M. Cvetkovi ´c, P. Rowlinson, and S. Simi´c, An Introduction to the Theory of Graph Spectra, Cambridge University Press,

  5. [5]

    Godsil and G

    C. Godsil and G. Royle, Algebraic Graph Theory , Graduate Texts in Mathematics, vol. 27, Springer, New York, 2001. https://doi.org/10.1007/978-1-4613-0163-9

    doi:10.1007/978-1-4613-0163-9 2001

  6. [6]

    Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen kon- jugierter Bindungen,

    H. H. G ¨unthard and H. Primas, “Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen kon- jugierter Bindungen,” Helv. Chim. Acta, vol. 39, no. 6, pp. 1645–1653, 1956. https://doi.org/10.1002/hlca.19560390623

    doi:10.1002/hlca.19560390623 1956

  7. [7]

    Are almost all graphs determined by their spectrum?,

    W. H. Haemers, “Are almost all graphs determined by their spectrum?,”Not. S. Afr. Math. Soc. 47.1 (2016): 42-45. Available at https://www.researchgate.net/publication/304747396

    arXiv 2016

  8. [8]

    Proving spectral uniqueness of graphs,

    W. H. Haemers, “Proving spectral uniqueness of graphs,” plenary talk in Combinatorics 2024, Carovigno, Italy, June 2024

    2024

Show all 109 references
  1. [9]

    Exponentially many graphs are determined by their spectrum,

    I. Koval and M. Kwan, “Exponentially many graphs are determined by their spectrum,” Quarterly Journal of Mathematics, vol. 75, no. 3, pp. 869–899, September 2024. https://doi.org/10.1093/qmath/haae030

    2024 doi

  2. [10]

    Haemers’ conjecture: an algorithmic perspective,

    W. Wang and W. Wang, “Haemers’ conjecture: an algorithmic perspective,” Experimental Mathematics, pp. 1–28, April

  3. [11]

    Almost all trees are cospectral,

    A. J. Schwenk, “Almost all trees are cospectral,” F . Harary (Ed.), New Directions in the Theory of Graphs, Academic Press, New York, pp. 275–307, 1973

    1973

  4. [12]

    Which graphs are determined by their spectrum?,

    E. R. van Dam and W. H. Haemers, “Which graphs are determined by their spectrum?,” Linear Algebra and Applications, vol. 343, pp. 241–272, November 2003. https://doi.org/10.1016/S0024-3795(03)00483-X

    2003 doi

  5. [13]

    Developments on spectral characterizations of graphs,

    E. R. van Dam and W. H. Haemers, “Developments on spectral characterizations of graphs,”Discrete Mathematics, vol. 309, no. 3, pp. 576–586, February 2009. http://dx.doi.org/10.1016/j.disc.2008.08.019

    2009 doi

  6. [14]

    A family of graphs that are deter- mined by their normalized Laplacian spectra,

    A. Berman, D. M. Chen, Z. B. Chen, W. Z. Liang, and X. D. Zhang, “A family of graphs that are deter- mined by their normalized Laplacian spectra,” Linear Algebra and its Applications , vol. 548, pp. 66–76, July 2018. https://doi.org/10.1016/j.laa.2018.03.001

    2018 doi

  7. [15]

    Signless Laplacian spectral characterization of the cones over some regular graphs,

    C. Bu and J. Zhou, “Signless Laplacian spectral characterization of the cones over some regular graphs,”Linear Algebra and its Applications, vol. 436, no. 9, pp. 3634–3641, 2012. https://doi.org/10.1016/j.laa.2011.12.035

    2012 doi

  8. [16]

    Starlike trees whose maximum degree exceed 4 are determined by their Q-spectra,

    C. Bu and J. Zhou, “Starlike trees whose maximum degree exceed 4 are determined by their Q-spectra,” Linear Algebra and its Applications, vol. 436, no. 1, pp. 143–151, January 2012. doi:10.1016/j.laa.2011.06.028

    2012 doi

  9. [17]

    Butler, A note about cospectral graphs for the adjacency and normalized Laplacian matrices

    S. Butler, A note about cospectral graphs for the adjacency and normalized Laplacian matrices. Linear and Multilinear Algebra, 2010, 58(3), 387–390. Taylor & Francis. https://doi.org/10.1080/03081080902722741

    2010 doi

  10. [18]

    A construction of cospectral graphs for the normalized Laplacian,

    S. Butler and J. Grout, “A construction of cospectral graphs for the normalized Laplacian,” Electronic Journal of Combina- torics, vol. 18, no. 1, paper P231, pp. 1–20, December 2011. https://doi.org/10.37236/718

    2011 doi

  11. [19]

    S. Butler. Algebraic aspects of the normalized Laplacian. Recent Trends in Combinatorics , pp. 295–315, Springer, 2016. doi:https://doi.org/10.1007/978-3-319-24298-9 13

    2016 doi

  12. [20]

    Butler and K

    S. Butler and K. Heysse, A cospectral family of graphs for the normalized Laplacian found by toggling. Linear Algebra and its Applications, vol. 507, pp. 499–512, October 2016. https://doi.org/10.1016/j.laa.2016.06.033

    2016 doi

  13. [21]

    Spectral characterizations of almost complete graphs,

    M. Camara and W. H. Haemers, “Spectral characterizations of almost complete graphs,” Discrete Applied Mathematics , vol. 176, pp. 19–23, October 2014. https://doi.org/10.1016/j.dam.2013.08.002

    2014 doi

  14. [22]

    Das and P

    A. Das and P. Panigrahi. Construction of simultaneous cospectral graphs for adjacency, Laplacian and normalized Laplacian matrices. Kragujevac Journal of Mathematics, 47(6):947-964 (2023) http://dx.doi.org/10.46793/KgJMat2306.947D

    2023 doi

  15. [23]

    Construction of cospectral graphs,

    S. Dutta and B. Adhikari, “Construction of cospectral graphs,” Journal of Algebraic Combinatorics, vol. 52, pp. 215–235, September 2020. https://doi.org/10.1007/s10801-019-00900-y

    2020 doi

  16. [24]

    Constructing cospectral graphs,

    C. Godsil and B. McKay, “Constructing cospectral graphs,” Aequationes Mathematicae, vol. 25, pp. 257–268, December

  17. [25]

    New constructions of nonregular cospectral graphs,

    S. Hamud and A. Berman, “New constructions of nonregular cospectral graphs,” Special Matrices, vol. 12, pp. 1–21, Febru- ary 2024. https://doi.org/10.1515/spma-2023-0109

    2024 doi

  18. [26]

    The lollipop graph is determined by its Q-spectrum

    H. Hamidzade and D. Kiani, Erratum to “The lollipop graph is determined by its Q-spectrum”, Discrete Mathematics, Discrete Mathematics, vol. 310, no. 10–11, p. 1649, June 2010. https://doi.org/10.1016/j.disc.2010.01.013

    2010 doi

  19. [27]

    Complete multipartite graphs are determined by their distance spectra,

    Y . L. Jin and X. D. Zhang, “Complete multipartite graphs are determined by their distance spectra,” Linear Algebra and its Applications, vol. 448, pp. 285–291, February 2014. https://doi.org/10.1016/j.laa.2014.01.029 44 IGAL SASON, NOAM KRUPNIK, SULEIMAN HAMUD, AND ABRAHAM BERMAN

    2014 doi

  20. [28]

    On the construction of cospectral nonisomorphic bipartite graphs,

    M. R. Kannan, S. Pragada, and H. Wankhede, “On the construction of cospectral nonisomorphic bipartite graphs,” Discrete Mathematics, vol. 345, no. 8, pp. 1–8, August 2022. https://doi.org/10.1016/j.disc.2022.112916

    2022

  21. [29]

    Hypercubes are determined by their distance spectra,

    J. H. Koolen, S. Hayat, and Q. Iqbal, “Hypercubes are determined by their distance spectra,” Linear Algebra and its Appli- cations, vol. 505, pp. 97–108, September 2016. http://dx.doi.org/10.1016/j.laa.2016.04.036

    2016 doi

  22. [30]

    Corrigendum to ’Hypercubes are determined by their distance spectra’,

    J. H. Koolen, S. Hayat, and Q. Iqbal, “Corrigendum to ’Hypercubes are determined by their distance spectra’,” Linear Algebra and its Applications, vol. 506, pp. 628–629, October 2016. http://dx.doi.org/10.1016/j.laa.2016.06.043

    2016 doi

  23. [31]

    The graphs of pyramids are determined by their spectrum,

    N. Krupnik and A. Berman, “The graphs of pyramids are determined by their spectrum,”Linear Algebra and its Applications,

  24. [32]

    Graphs determined by their Aα-spectra,

    H. Lin, X. Liu, and J. Xue, “Graphs determined by their Aα-spectra,” Discrete Mathematics, vol. 342, no. 2, pp. 441–450, February 2019. https://doi.org/10.1016/j.disc.2018.10.006

    2019 doi

  25. [34]

    Abiad, W

    A. Abiad, W. H. Haemers, Cospectral graphs and regular orthogonal matrices of level 2. Electron. J. Combin. vol 19, no. 3, paper P13, 2012. https://doi.org/10.37236/2383

    2012 doi

  26. [35]

    https://doi.org/10.1016/j.laa.2024.04.029

    2024 doi

  27. [36]

    The multi-fan graphs are determined by their Laplacian spectra,

    X. Liu, Y . Zhang, and X. Gui, “The multi-fan graphs are determined by their Laplacian spectra,” Discrete Mathematics, vol. 308, no. 18, pp. 4267–4271, September 2008. https://doi.org/10.1016/j.disc.2007.08.002

    2008 doi

  28. [37]

    On the spectral characterization of the union of complete multipartite graph and some isolated vertices,

    H. Ma and H. Ren, “On the spectral characterization of the union of complete multipartite graph and some isolated vertices,” Discrete Mathematics, vol. 310, pp. 3648–3652, September 2010. https://doi.org/10.1016/j.disc.2010.09.004

    2010 doi

  29. [38]

    Laplacian spectral determination of path- friendship graphs,

    M. R. Oboudi, A. Z. Abdian, A. R. Ashrafi, and L. W. Beineke, “Laplacian spectral determination of path- friendship graphs,” AKCE International Journal of Graphs and Combinatorics , vol. 18, no. 1, pp. 33–38, 2021. https://doi.org/10.1080/09728600.2021.1917321

    2021

  30. [39]

    Constructions of cospectral graphs with different zero forcing numbers,

    A. Abiad, B. Brimkov, J. Breen, T.R. Cameron, H. Gupta, and R. Villagran, “Constructions of cospectral graphs with different zero forcing numbers,”Electron. J. Linear Algebra, vol. 38, pp. 280–294, May 2022. https://doi.org/10.13001/ela.2022.6737

    2022

  31. [40]

    Starlike trees with maximum degree 4 are determined by their signless Laplacian spectra,

    G. R. Omidi and E. Vatandoost, “Starlike trees with maximum degree 4 are determined by their signless Laplacian spectra,” Electronic Journal of Linear Algebra, vol. 20, pp. 274–290, May 2010. https://doi.org/10.13001/1081-3810.1373

    2010

  32. [41]

    Observations on graph invariants with the Lov´aszϑ-function,

    I. Sason, “Observations on graph invariants with the Lov´aszϑ-function,” AIMS Mathematics, vol. 9, no. 6, pp. 15385–15468, June 2024. https://doi.org/10.3934/math.2024747

    2024 doi

  33. [42]

    Two classes of graphs determined by their signless Laplacian spectrum,

    J. Ye, M. Liu, and Z. Stani ´c, “Two classes of graphs determined by their signless Laplacian spectrum,” Linear Algebra and Its Applications, vol. 708, pp. 159–172, March 2025. https://doi.org/10.1016/j.laa.2024.10.029

    2025 doi

  34. [43]

    Starlike trees are determined by their Laplacian spectrum,

    G. R. Omidi and K. Tajbakhsh, “Starlike trees are determined by their Laplacian spectrum,” Linear Algebra and its Applica- tions, vol. 422, no. 2–, pp. 654–658, April 2007. https://doi.org/10.1016/j.laa.2006.11.028

    2007 doi

  35. [44]

    The lollipop graph is determined by its Q-spectrum,

    Y . Zhang, X. Liu, B. Zhang, and X. Yong, “The lollipop graph is determined by its Q-spectrum,” Discrete Mathematics, vol. 309, no. 10, pp. 3364–3369, May 2009. https://doi.org/10.1016/j.disc.2008.09.052

    2009 doi

  36. [45]

    Laplacian spectral characterization of some graphs obtained by product operation,

    J. Zhou and C. Bu, “Laplacian spectral characterization of some graphs obtained by product operation,” Discrete Mathemat- ics, vol. 312, pp. 1591–1595, May 2012. http://dx.doi.org/10.1016/j.disc.2012.02.002

    2012 doi

  37. [46]

    Schur, ¨Uber Potenzreihen, die im Innern des Einheitskreises beschr¨ankt sind

    J. Schur, ¨Uber Potenzreihen, die im Innern des Einheitskreises beschr¨ankt sind. (1917): vol. 147, pp. 205–232

    1917

  38. [47]

    Which wheel graphs are determined by their Laplacian spectra?

    Y . Zhang, X. Liu, X. Yong, “Which wheel graphs are determined by their Laplacian spectra?” Computers and Mathematics with Applications, vol. 58, pp. 1887–1890, November 2009. http://dx.doi.org/10.1016/j.camwa.2009.07.028

    2009 doi

  39. [48]

    Shaked-Monderer and A

    N. Shaked-Monderer and A. Berman, Copositive and Completely Positive Matrices , World Scientific Publishing Co. Pte. Ltd., 2021. https://doi.org/10.1142/11386

    2021 doi

  40. [49]

    There exists no (76 , 21, 2, 7) strongly regular graph,

    W. Haemers, “There exists no (76 , 21, 2, 7) strongly regular graph,” pp. 175–176 in Finite Geometry and Combina- torics, F. De Clerck and J. Hirschfeld editors, LMS Lecture Notes Series 191, Cambridge University Press, 1993. https://doi.org/10.1017/CBO9780511526336.018

    1993 doi

  41. [50]

    On the Shannon capacity of a graph,

    L. Lov ´asz, “On the Shannon capacity of a graph,”IEEE Transactions on Information Theory, vol. 25, no. 1, pp. 1–7, January

  42. [51]

    The symmetric eigenvalue problem,

    B. N. Parlett, “The symmetric eigenvalue problem,” Classics in Applied Mathematics , 1998. http://dx.doi.org/10.1137/1.9781611971163

    1998 doi

  43. [52]

    On the solution of the equations obtained from the investigation of the linear distribution of galvanic currents,

    G. Kirchho ff, “On the solution of the equations obtained from the investigation of the linear distribution of galvanic currents,” IRE Transactions on Circuit Theory, vol. 5, no. 1, pp. 4-7 (1958) https://doi.org/10.1109/TCT.1958.1086426

    1958

  44. [53]

    A. Cayley. A theorem on trees. Quart. J. Pure Appl. Math. 23: 376–378. (1889)

  45. [54]

    Bounds on the Q-spread of a graph,

    C. S. Oliveira, L. S. de Lima, N. M. M. de Abreu, and S. Kirkland, “Bounds on the Q-spread of a graph,” Linear Algebra and its Applications, vol. 432, no. 9, pp. 2342–2351, April 2010. https://doi.org/10.1016/j.laa.2009.06.011 ON SPECTRAL GRAPH DETERMINATION 45

    2010 doi

  46. [55]

    A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph,

    D. M. Cardoso, D. Cvetkovi ´c, P. Rowlinson, and S. Simi ´c, “A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph,” Linear Algebra and its Applications , vol. 429, no. 11-12, pp. 2770–2780, December

  47. [56]

    A. E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs, Cambridge University Press, (Encyclopedia of Mathemat- ics and its Applications, Series Number 182), 2022

    2022

  48. [57]

    Signless Laplacians of finite graphs,

    D. M. Cvetkovi ´c, P. Rowlinson, and S. Simi ´c, “Signless Laplacians of finite graphs,” Linear Algebra and Applications , vol. 423, no. 1, pp. 155–171, May 2007. https://doi.org/10.1016/j.laa.2007.01.009

    2007 doi

  49. [58]

    S. Butler. A gentle introduction to the normalized Laplacian, IMAGE 53, pp 19-27, Fall 2014. Online available fromhttps: //www.stevebutler.org/research/publications

    2014

  50. [59]

    Observations on Lov´aszϑ-function, graph capacity, eigenvalues, and strong products,

    I. Sason, “Observations on Lov´aszϑ-function, graph capacity, eigenvalues, and strong products,”Entropy, vol. 25, paper 104, pp. 1–40, January 2023. https://doi.org/10.3390/e25010104

    2023 doi

  51. [60]

    On a problem in graph theory,

    P. Erd ¨os, “On a problem in graph theory,” The Mathematical Gazette , vol. 47, pp. 220–223, October 1963. https://doi.org/10.2307/3613396

    1963 doi

  52. [61]

    Aigner, and G

    M. Aigner, and G. M. Ziegler, Proofs from the book , Sixth Edition, Springer, Berlin, Germany, 2018. Available from: https://link.springer.com/book/10.1007/978-3-662-57265-8

    2018 doi

  53. [62]

    A sharp lower bound on the least signless Laplacian eigenvalue of a graph,

    X. Chen and Y . Hou, “A sharp lower bound on the least signless Laplacian eigenvalue of a graph,”Bulletin of the Malaysian Mathematical Sciences Society, V olume 41, pages 2011–2018, October 2018. https://doi.org/10.1007/s40840-016-0440-1

    2011 doi

  54. [63]

    The graphs with all but two eigenvalues equal to±1,

    S. M. Cioab ˇa, W. H. Haemers, J. R. Vermette, and W. Wong, “The graphs with all but two eigenvalues equal to±1,” Journal of Algebraic Combinatorics, vol. 41, no. 3, pp. 887–897, May 2015. https://doi.org/10.1007/s10801-014-0557-y

    2015 doi

  55. [64]

    Spectral characterizations of sandglass graphs,

    P. Lu, X. Liu, Z. Yuan, and X. Yong, “Spectral characterizations of sandglass graphs,”Applied Mathematics Letters, vol. 22, no. 8, pp. 1225–1230, August 2009. http://dx.doi.org/10.1016/j.aml.2009.01.050

    2009 doi

  56. [65]

    A su fficient condition for a family of graphs being determined by their generalized spectra,

    W. Wang and C. X. Xu, “A su fficient condition for a family of graphs being determined by their generalized spectra,” European Journal of Combinatorics, vol. 27, no. 6, pp. 826–840, August 2006. https://doi.org/10.1016/j.ejc.2005.05.004

    2006 doi

  57. [66]

    Generalized spectral characterization of graphs revisited,

    W. Wang, “Generalized spectral characterization of graphs revisited,” The Electronic Journal of Combinatorics , vol. 20, no. 4, paper P4, pp. 1–13, October 2013. https://doi.org/10.37236/3748

    2013 doi

  58. [67]

    A simple arithmetic criterion for graphs being determined by their generalized spectra,

    W. Wang, “A simple arithmetic criterion for graphs being determined by their generalized spectra,”Journal of Combinatorial Theory, Series B, vol. 122, pp. 438–451, January 2017. https://doi.org/10.1016/j.jctb.2016.07.004

    2017 doi

  59. [68]

    The complement of the path is determined by its spectrum,

    M. Doob and W. H. Haemers, “The complement of the path is determined by its spectrum,” Linear Algebra and its Applica- tions, vol. 356, no. 1–3, pp. 57–65, November 2002. https://doi.org/10.1016/S0024-3795(02)00323-3

    2002 doi

  60. [69]

    Complete split graph determined by its (signless) Laplacian spectrum,

    K. Ch. Das and M. Liu, “Complete split graph determined by its (signless) Laplacian spectrum,” Discrete Applied Mathe- matics, vol. 205, pp. 45–51, May 2016. https://doi.org/10.1016/j.dam.2016.01.003

    2016 doi

  61. [70]

    J. Wang, F. Belardo, Q. Huang, and B. Borovi ´canin. On the two largest Q-eigenvalues of graphs. Discrete Mathematics, 310(21):2858–2866, November 2010. https://doi.org/10.1016/j.disc.2010.06.030

    2010 doi

  62. [71]

    On an external problem in graph theory,

    P. Tur ´an, “On an external problem in graph theory,”Mat. Fiz. Lapok, 48:436–452, 1941

    1941

  63. [72]

    On the spectrum of a complete multipartite graph,

    F. Esser and F. Harary, “On the spectrum of a complete multipartite graph,” European Journal of Combinatorics , vol. 1, no. 3, pp. 211–218, September 1980. https://doi.org/10.1016/S0195-6698(80)80004-7

    1980 doi

  64. [73]

    Butler, Eigenvalues and Structures of Graphs

    S. Butler, Eigenvalues and Structures of Graphs . University of California, San Diego, 2008. Available from https:// escholarship.org/uc/item/3qd9g26t

    2008

  65. [74]

    Disjoint unions of complete graphs characterized by their Laplacian spectrum,

    R. Boulet, “Disjoint unions of complete graphs characterized by their Laplacian spectrum,” Electronic Journal of Linear Algebra, vol. 18, no. 1, pp. 773–783, January 2009. https://doi.org/10.13001/1081-3810.1344

    2009

  66. [75]

    Some Propertice of the Spectrum of Graph,

    J. H. Smith, “Some Propertice of the Spectrum of Graph,” in: Combinatorial Structures and Their Applications, R. K. Guy, H. Hanani, N. Sauer, and J. Sch¨onheim (Eds.), Gordon and Breach, New York, pp. 403–406, 1970

    1970

  67. [76]

    L. W. Beineke and J. S. Bagga, Line Graphs and Line Digraphs, Springer, 2021. https://doi.org/10.1007/978-3-030-81386-4

    2021 doi

  68. [77]

    The uniqueness of the L 2 association scheme,

    S. S. Shrikhande, “The uniqueness of the L 2 association scheme,” The Annals of Mathematical Statistics , vol. 30, no. 3, pp. 781–791, September 1959. https://doi.org/10.1214/aoms/1177706207

    1959

  69. [78]

    Laplacian spectrum characterization of extensions of vertices of wheel graphs and multi-fan graphs,

    Y . Lin, J. Shu, and Y . Meng, “Laplacian spectrum characterization of extensions of vertices of wheel graphs and multi-fan graphs,” Computers & Mathematics with Applications , vol. 60, no. 7, pp. 2003–2008, October 2010. https://doi.org/10.1016/j.camwa.2010.07.035

    2003 doi

  70. [79]

    Strongly regular graphs with no triangles,

    P. J. Cameron and J. H. van Lindt, “Strongly regular graphs with no triangles,” in Graphs, Codes and Designs , Chapter 5, pp. 37–44, Cambridge University Press, 1980. https://doi.org/10.1017/CBO9780511662140.006

    1980 doi

  71. [80]

    The Sage Developers, SageMath, the Sage Mathematics Software System, Version 9.3, 2021

    2021

  72. [81]

    The uniqueness of the strongly regular graph on 77 points,

    A. E. Brouwer, “The uniqueness of the strongly regular graph on 77 points,”Journal of Graph Theory, vol. 7, no. 4, pp. 455– 461, December 1983. https://doi.org/10.1002/jgt.3190070411

    1983 doi

  73. [82]

    Structure and uniqueness of the (81 , 20, 1, 6) strongly regular graph,

    A. E. Brouwer and W. H. Haemers, “Structure and uniqueness of the (81 , 20, 1, 6) strongly regular graph,” Discrete Mathe- matics, vol. 106–107, pp. 77–82, September 1992. https://doi.org/10.1016/0012-365X(92)90532-K 46 IGAL SASON, NOAM KRUPNIK, SULEIMAN HAMUD, AND ABRAHAM BERMAN

    1992 doi

  74. [83]

    A spectral proof of the uniqueness of a strongly regular graph with parameters (81 , 20, 1, 6),

    D. Stevanovi ´c and M. Milo ˇsevi´c,“A spectral proof of the uniqueness of a strongly regular graph with parameters (81 , 20, 1, 6),” European Journal of Combinatorics , vol. 30, no. 4, pp. 957–968, May 2009. https://doi.org/10.1016/j.ejc.2008.07.021

    2009 doi

  75. [84]

    The uniqueness of the strongly regular graph srg(105, 32, 4, 12),

    K. Coolsaet, “The uniqueness of the strongly regular graph srg(105, 32, 4, 12),” Bulletin of the Belgian Mathematical Society - Simon Stevin, vol. 12, no. 5, pp. 707–718, January 2006. https://doi.org/10.36045/bbms/1136902608

    2006

  76. [85]

    D. M. Mesner, “An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types,” PhD dissertation, Department of Statistics, Michigan St...

    1956 doi

  77. [86]

    Random strongly regular graphs?,

    P. J. Cameron, “Random strongly regular graphs?,” Discrete Mathematics, vol. 273, no. 1–3, pp. 103–114, December 2003. https://doi.org/10.1016/S0012-365X(03)00231-0

    2003 doi

  78. [87]

    A. E. Brouwer, tables of paramters of strongly regular graphs. https://aeb.win.tue.nl/graphs/srg/

  79. [88]

    Clique complexes of strongly regular graphs and their eigenvalues,

    S. Cioaba, K. Guo, C. Ji, and M. Mim, “Clique complexes of strongly regular graphs and their eigenvalues,” in preparation, 2025

    2025

  80. [89]

    On the splitting graph of a graph,

    E. Sampathkumar and H. B. Walikar, “On the splitting graph of a graph,” Karnatak Univ. Sci, vol. 13, pp. 13–16, 1980. Available from https://www.researchgate.net/publication/269007309

    1980

  81. [90]

    On the corona of two graphs,

    R. Frucht and F. Harary, “On the corona of two graphs,” Aequationes Mathematicae , vol. 4, pp. 322-325, 1970. https://doi.org/10.1007/BF01844162

    1970 doi

  82. [91]

    Hou and W

    Y . Hou and W. C. Shiu, The spectrum of the edge corona of two graphs. The Electronic Journal of Linear Algebra, vol. 20, pp. 586–594, September 2010. https://doi.org/10.13001/1081-3810.1395

    2010

  83. [92]

    Struik and W

    T. Struik and W. Bosma, Seven known examples of triangle-free strongly-regular graphs, 2010. Available at https://www. math.ru.nl/OpenGraphProblems/Tjapko/30.html

    2010

  84. [93]

    On the spectrum of closed neighborhood corona product of graph and its application,

    B. Sonar and R. Srivastava, “On the spectrum of closed neighborhood corona product of graph and its application,” July

  85. [94]

    Pisanski and B

    T. Pisanski and B. Servatius, Configurations from a Graphical Viewpoint , Springer, 2013. https: //doi.org/10.1007/978-0- 8176-8364-1

    2013 doi

  86. [95]

    Spectra of graph operations based on splitting graph,

    Z. Lu, X. Ma, and M. Zhang, “Spectra of graph operations based on splitting graph,” Journal of Applied Analysis and Computation, vol. 13, no. 1, pp. 133–155, February 2023. https://doi.org/10.11948/20210446

    2023 doi

  87. [96]

    Hamud, Contributions to Spectral Graph Theory, Ph.D

    S. Hamud, Contributions to Spectral Graph Theory, Ph.D. dissertation, Technion-Israel Institute of Technology, Haifa, Israel, December 2023

    2023

  88. [97]

    Cospectral graphs on 12 vertices,

    A. E. Brouwer and E. Spence, “Cospectral graphs on 12 vertices,” Electronic Journal of Combinatorics , vol. 16, no. 1, paper 20, pp. 1–3, June 2009. https://doi.org/10.37236/258

    2009 doi

  89. [98]

    Spectra of some new graph operations and some new class of integral graphs,

    C. Adiga, B. R. Rakshith, and K. N. Subba Krishna, “Spectra of some new graph operations and some new class of integral graphs,” Iranian Journal of Mathematical Sciences and Informatics , vol. 13, no. 1, pp. 51–65, May 2018. Available from http://ijmsi.ir/article-1-755-en.html

    2018

  90. [99]

    A survey on distance spectra of graphs,

    L. Huiqiu, S. Jinlong, X. Jie, and Z. Yuke, “A survey on distance spectra of graphs,” Advances in Mathematics (China) , vol. 50, no. 1, January 2021. https://doi.org/10.11845/SXJZ.2020012A

    2021 doi

  91. [100]

    http://dx.doi.org/10.48550/arXiv.2407.05653

    doi arXiv

  92. [101]

    Spectra of variants of distance matrices of graphs and digraphs: a survey,

    L. Hogben and C. Reinhart, “Spectra of variants of distance matrices of graphs and digraphs: a survey,” La Matematica, vol. 1, pp. 186–224, January 2022. https://doi.org/10.1007/s44007-021-00012-9

    2022 doi

  93. [102]

    On the distance spectrum of graphs,

    H. Lin, Y . Hong, J. Wang, and J. Shu, “On the distance spectrum of graphs,” Linear Algebra and its Applications, vol. 439, pp. 1662–1669, May 2013. https://doi.org/10.1016/j.laa.2013.04.019

    2013 doi

  94. [103]

    Graphs whose normalized Laplacian has three eigenvalues,

    E. R. van Dam and G. R. Omidi, “Graphs whose normalized Laplacian has three eigenvalues,” Linear Algebra and its Applications, vol. 435, no. 10, pp. 2560–2569, November 2011. https://doi.org/10.1016/j.laa.2011.02.005

    2011 doi

  95. [105]

    Distance spectra of graphs: A survey,

    M. Aouchiche and P. Hansen, “Distance spectra of graphs: A survey,”Linear Algebra and its Applications, vol. 458, pp. 301– 386, June 2014. https://doi.org/10.1016/j.laa.2014.06.010

    2014 doi

  96. [107]

    Distance Laplacian spectra of various graph operations and its application to graphs on alge- braic structures,

    S. Banerjee, “Distance Laplacian spectra of various graph operations and its application to graphs on alge- braic structures,” Journal of Algebra and Its Applications , vol. 22, no. 1, paper 2350022, pp. 1–26, 2023. https://doi.org/10.1142/S0219498823500226

    2023 doi

  97. [1979]

    https://doi.org/10.1109/TIT.1979.1055985

    1979

  98. [1982]

    https://doi.org/10.1007/BF02189621

    doi

  99. [2008]

    https://doi.org/10.1016/j.laa.2008.05.017

    2008 doi

  100. [2009]

    https://doi.org/10.1017/CBO9780511801518

    doi

  101. [2024]

    https://doi.org/10.1080/10586458.2024.2337229

    2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.