Pith. sign in

REVIEW 4 major objections 5 minor 164 references

Contributions in Algebraic Graph Theory

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read This paper proves that for a prime power $q$ and $2 \le d \le n$, the generalized-Hamming graph $G_{q,n,d}$ is edge-transitive if and only if it is distance-transitive, with the precise parameter list $d=2$, $(q,d)=(2,3)$, or…

desk verdict A mostly honest thesis-compilation: the transitivity classification is the real contribution, but the arXiv version has repairable proof gaps and does not itself advance the field beyond the author's own published papers. read the letter →

arxiv 2607.17829 v1 pith:TAUUWUJQ submitted 2026-07-20 math.CO cs.DM

Noam Krupnik This is my paper · ORCID
classification math.COcs.DM MSC 05C5005C2505E3005C12
keywords spectralgraphtheorygraphsdeterminedbyspectrumgeneralized-Hammingedge-transitivitydistance-transitivityassociationschemesKrawtchoukpolynomialsLovászthetafunction
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

The thesis has two strands. In spectral determination it proves that graphs of pyramids are determined by their adjacency spectrum, that the star $S_n$ is determined by its spectrum exactly when $n-1$ is prime, and gives new proofs that complete bipartite and Turán graphs are spectrally determined. In the transitivity strand, the central result is a complete classification: the generalized-Hamming graph $G_{q,n,d}$ is edge-transitive if and only if it is distance-transitive, and this happens exactly for $d=2$, $(q,d)=(2,3)$, or $(q,d)=(2,n)$. For the complements the two notions separate: edge-transitivity holds for $(q,d)=(2,n-1)$ with $n$ even or $d=n$, while distance-transitivity holds for a strictly smaller set, namely $(q,d)=(2,n-1)$ with $n$ even, or $d=n$ with $q=2$ or $n=2$. Whenever either graph or its complement is edge-transitive, the paper gives closed formulas for the Lovász theta function of both, computed from the Hamming scheme's spectrum in quadratic time instead of exponential-time SDP.

What carries the argument

The argument runs on two mechanisms. For the graphs themselves, edge-transitivity is probed by the invariant $F(v)=|N(v)\setminus N(0)|$ counting neighbors of a neighbor $v$ that are not neighbors of $0$; if the graph were edge-transitive this count would be constant on $N(0)$, but explicit binomial counts for the vectors $(1,0,\ldots,0)$, $(1,1,0,\ldots,0)$ and, in the binary case, $(1,1,1,0,\ldots,0)$ force an impossible equality, leaving only the three listed parameter sets, whose positive transitivity comes from known distance-regularity of the Hamming graph, a known proof for $G_{2,n,3}$, and a parity automorphism for $G_{2,n,n}$ constructed in Lemma 4.3.1. For the complements, the machinery is the Hamming association scheme: the adjacency matrix decomposes as $\sum_j \gamma_j E_j$ with $\gamma_j = -K_{d-1}(j-1;n-1,q)$ in terms of $q$-ary Krawtchouk polynomials, and the key spectral fact is the strict inequality $\gamma_1 < \gamma_m$ for $2 \le m \le n-1$, proved by the character-theoretic representation of Krawtchouk polynomials. That inequality makes the interpolating polynomials $p(t)$ that isolate $E_1$ (or $E_1+E_n$) well defined; applying such a polynomial to the adjacency matrix produces a matrix that must be invariant under every automorphism, but its $(0,u)$-entries for vectors of different weights take different values, a contradiction that rules out all but the exceptional parameter sets.

What would settle it

A direct automorphism search on $\overline{G}_{2,5,4}$ (the complement of the generalized-Hamming graph with $q=2$, $n=5$, $d=4$) should find no automorphism sending the edge from $00000$ to $11111$ onto the edge from $00000$ to $11110$, since this parameter set is excluded; finding one would refute the classification.

Watch

Extended reading notes

Core claim

On the paper's own terms, the main discovery is Theorem 4.1.1 and Theorem 4.1.2: for a prime power $q$ and $2 \le d \le n$, the generalized-Hamming graph $G_{q,n,d}$ — the Cayley graph on $\mathbb{F}_q^n$ connecting vectors at Hamming distance less than $d$ — is edge-transitive exactly when it is distance-transitive, which occurs precisely when $d=2$, or $(q,d)=(2,3)$, or $(q,d)=(2,n)$. Its complement is edge-transitive exactly for $(q,d)=(2,n-1)$ with $n$ even or $d=n$, and distance-transitive exactly for $(q,d)=(2,n-1)$ with $n$ even, or $d=n$ with $q=2$ or $n=2$; hence the distance-transitive parameters form a proper subset of the edge-transitive ones. As a corollary, every edge-transitive case yields closed-form Lovász $\theta$ values for both the graph and its complement, since all these graphs are vertex-transitive and the equality conditions of the spectral $\theta$ bounds are met.

Load-bearing premise

The proofs that the non-listed graphs lack edge-transitivity rest on a strict inequality between two eigenvalues of the complement graph, and that inequality holds only because a nonzero additive character cannot be constantly 1 on all vectors of a fixed nonzero weight.

Editorial extensions

If this is right

  • Every edge-transitive generalized-Hamming graph is distance-transitive, so the stronger symmetry comes for free in exactly the parameters $d=2$, $(q,d)=(2,3)$, and $(q,d)=(2,n)$.
  • For complements, edge-transitivity no longer implies distance-transitivity; the gap is witnessed by $d=n$ with $q\ge 3$ and $n\ge 3$, which is edge- but not distance-transitive.
  • In all edge-transitive cases, the Lovász theta value of the graph and of its complement is given in closed form from the eigenvalues in (4.4.15), computed in $O(n^2)$ time rather than by solving the exponential-size SDP.
  • If both a generalized-Hamming graph and its complement are edge-transitive, the parameters are $(q,d)=(2,n)$ or $(q,n,d)=(2,3,4)$ (Corollary 4.1.3).

Reading between the lines

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

  • The same polynomial-isolating technique — build a polynomial of the adjacency matrix that acts as an idempotent and then show no automorphism can commute with it — should apply to other Cayley graphs whose association scheme has a known eigenmatrix, e.g., graphs built from the Johnson scheme.
  • The classification suggests that for this family the size of the automorphism group is a poor predictor of spectral determination: the most symmetric cases are exactly the structured ones with known spectra, while random graphs, which are spectrally determined generically, are far less symmetric.
  • A testable extension: for parameters outside the three listed sets, computer search for small $q,n,d$ should find a pair of edges with different $F$-values (respectively different $(E_1)$ entries for the complement), giving an explicit certificate of non-edge-transitivity independent of the proof.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. This Master's thesis treats two themes in algebraic graph theory. The first part surveys spectral graph determination and contains new proofs that complete bipartite graphs and Turán graphs are determined by their adjacency spectrum, together with a proof that the 'graphs of pyramids' T_{n,k}=K_k∨\overline{K_{n-k}} are DS. The second part classifies the parameters (q,n,d) for which the generalized-Hamming graph G_{q,n,d} and its complement are edge-transitive or distance-transitive, and derives closed-form Lovász theta values in the edge-transitive cases. The main results are largely reproduced from the author's published or submitted papers with his co-authors, and the thesis adds a survey of cospectral constructions and open problems.

Significance. If the proof gaps are repaired, the transitivity classification in Theorems 4.1.1 and 4.1.2 is a useful contribution: it completely identifies the highly symmetric members of the generalized-Hamming family and feeds directly into the closed-form Lovász theta computations of Theorem 4.7.1, which are genuinely valuable because the SDP formulation on q^n vertices is exponential in n. The pyramid-graph DS theorem is a small but elegant result, proved with Schur complements and interlacing. The survey portions are broad and generally accurate. On the other hand, the thesis's own proofs contain several load-bearing errors, and the corollary on complete bipartite DS graphs is plainly false; the current version is not acceptable without revision.

major comments (4)
  1. [§2.4.2, Theorem 2.4.7(2)] The proof of the 'only if' direction defines G=K_{a,b}∨K_r with r=p+q−a−b and asserts in (2.4.6) that its adjacency spectrum equals that of K_{p,q}. This is false: for r>0 the join contains triangles, so G is not bipartite and cannot be cospectral with a complete bipartite graph; moreover the displayed spectrum has zero multiplicity pq−2, which should be p+q−2. The intended construction must be the disjoint union K_{a,b}∪\overline{K_r}, whose spectrum is {−√pq, [0]^{p+q−2}, √pq}. As written, the proof of Theorem 2.4.7(2) does not establish the characterization.
  2. [§2.4.2, Theorem 2.4.7(1)] The proof states that A(P_3) has rank 3; the adjacency matrix of P_3 has rank 2, so the interlacing argument used to exclude P_3 as an induced subgraph is invalid. The subsequent conclusion that a graph cospectral with K_{p,q} has the form K_{a,b}∪H with H empty is not derived: one needs an explicit argument, for example via Theorem 2.4.22 or via the fact that the spectrum has only two nonzero eigenvalues, that a connected bipartite graph with exactly one positive eigenvalue is complete bipartite. This is a load-bearing step for Theorem 2.4.7.
  3. [§2.4.2, Corollary 2.4.9] The corollary is false as stated. On n=6 vertices both K_{1,5} and K_{2,4} are DS: for K_{1,5}, {1,5} is the unique minimizing factor pair of 5, and for K_{2,4}, {2,4} is the unique minimizing factor pair of 8. The proof conflates the number n of vertices with the product pq; the DS condition of Theorem 2.4.7 involves factorizations of pq, not factorizations of n. The corollary and its proof should be corrected or removed.
  4. [§4.4.4, Theorem 4.4.10(2)] The proof of the strict inequality γ_1<γ_m asserts that a nontrivial additive character cannot be identically 1 on all vectors of a fixed positive weight. This is false in general: over F_2, for x=1^N and even weight d−1, every y of weight d−1 has trivial inner product with x. In the application one has 1≤w_H(x)=m−1≤n−2, so the all-ones obstruction is absent, but the written proof does not invoke this restriction. Since the denominators in (4.5.1) and (4.5.10) depend on γ_1−γ_m, the non-transitivity proofs in Lemmas 4.5.1 and 4.5.2, and hence the corresponding direction of Theorem 4.1.2, rest on an unproved assertion. The gap is repairable by proving K_{d−1}(s;n−1,q)<K_{d−1}(0;n−1,q) for 1≤s≤n−2, but the current text is incomplete.
minor comments (5)
  1. [§2.4.10 / notation] In Definition 2.4.10 and throughout the join constructions, K_r is used for the edgeless graph, while the notation list defines K_n as the complete graph. Please introduce \overline{K_n} and use it consistently; this ambiguity contributes to the error in the proof of Theorem 2.4.7.
  2. [§3.4, Lemma 3.4.6(3)] The claim that G has one eigenvalue strictly smaller than −1 is false for k=n−1, where T_{n,k}≅K_n has no eigenvalue below −1. The proof of Lemma 3.4.10 only needs the 'at most one' version, so the statement should be weakened accordingly.
  3. [§4.5, Lemma 4.5.1] The proof uses connectivity of the complement graph to conclude that γ_0 is a simple eigenvalue, but this connectivity is not proved or referenced. It should be stated explicitly for the parameter range considered.
  4. [§4.5, completion of Theorem 4.1.2] In the final summary of cases, the text attributes the case 'q=2 and 1<d<n−1' to Lemma 4.5.1, but the odd-d subcase is handled by Lemma 4.5.2; the attribution should be adjusted for clarity.
  5. [§4.5, Lemma 4.5.4] The proof that the map φ is an automorphism of G checks that edges are mapped to edges but leaves implicit that a bijective edge-preserving map preserves non-edges; this should be stated for completeness.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the thesis reproduces and proves its authors' prior results; all load-bearing derivations are self-contained proofs, not fits or renamed inputs.

full rationale

The claimed derivations are self-contained rather than circular. The spectral determination of graphs of pyramids (Theorem 3.4.4) is proved directly from the Schur complement computation of the spectrum, Cauchy interlacing, and edge/component counting arguments; the prior publication [90] is cited for provenance but the proof is reproduced in the thesis. The same holds for the complete bipartite and Turán graph characterizations in Chapter 2, where new proofs are given from spectral and extremal arguments. In Chapter 4, the edge- and distance-transitivity classifications are proved by explicit combinatorial invariants (the F(u) counting argument for Theorem 4.1.1) and by spectral idempotent polynomials built from the Hamming association scheme (Lemmas 4.5.1 and 4.5.2), rather than by quoting the classification. The Lovász theta application combines these classifications with an external, independently stated bound from [125]; no fitted parameter is renamed as a prediction, no ansatz is smuggled in via self-citation, and no result is defined in terms of the claim it is supposed to establish. The skeptical note about the additive-character argument in Theorem 4.4.10(2) is a proof-gap concern about correctness, not a demonstration that the theorem reduces to its own input; even if that intermediate inequality needed a repaired proof, that would not make the derivation circular. The self-citations that appear are chapter provenance statements (e.g., 'This chapter reproduces, with minor modifications, the results of [90]' and '[91]') and are not load-bearing because the essential arguments appear in the manuscript itself. Accordingly, the circularity score is 0.

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

The central claims rest on standard results in matrix analysis, association scheme theory, and finite field character theory, all cited to external textbooks or papers. No free parameters are fitted to data. The only newly named object, the graphs of pyramids, is explicitly defined and its properties are proved rather than postulated, so it is not a hidden entity.

assumptions (6)
  • standard math Cauchy interlacing theorem and Schur determinant theorem
    Used throughout Chapters 2 and 3 to derive spectra, bound eigenvalues of induced subgraphs, and prove the pyramid graphs are DS.
  • standard math Krawtchouk polynomial generating function, summation identities, and character-theoretic representation
    Used in Theorem 4.4.10 to derive the spectrum of the complement of generalized-Hamming graphs and to establish the strict eigenvalue inequalities needed in Lemmas 4.5.1 and 4.5.2.
  • standard math The Hamming scheme is a symmetric association scheme with eigenmatrix entries given by q-ary Krawtchouk polynomials
    Assumed in Section 4.4.3 as background; the thesis cites [56, Example 1] for the eigenmatrix values and uses them in the spectral decomposition of the complement graph.
  • domain assumption A graph with exactly one positive eigenvalue is the disjoint union of a nonempty complete multipartite graph and isolated vertices
    Theorem 2.4.22 from [134] is used in the proof of Theorem 2.4.21 that Turán graphs are DS.
  • domain assumption A graph is completely positive if and only if it contains no long odd cycle, equivalently its line graph is perfect
    Theorem 3.2.6 from [86] is used in Section 3.5 to classify the pyramid graphs according to complete positivity and to answer Question 3.5.1.
  • domain assumption q is a prime power so that the additive characters of F_q and the trace map have the stated properties
    Theorem 4.4.8 and Lemma 4.5.1 require a nontrivial additive character of F_q that is not identically 1 on vectors of a fixed positive weight; this is why the transitivity theorems are restricted to prime powers q.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Contributions in Algebraic Graph Theory." pith.science (2026). https://pith.science/paper/TAUUWUJQ

@misc{pith2026260717829,
  author       = {Pith},
  title        = {Pith review of: Contributions in Algebraic Graph Theory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TAUUWUJQ}},
  note         = {Machine review of arXiv:2607.17829}
}
abstract

This thesis investigates two central directions in algebraic graph theory, with an emphasis on spectral methods: spectral determination of graphs and transitivity properties of generalized-Hamming graphs and their complements. The first part focuses on graphs that are determined by the spectra of associated matrices. We study spectral determination with respect to the adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, with particular emphasis on the adjacency spectrum. We survey existing results on graphs determined by their spectrum and develop new proof techniques for establishing spectral uniqueness. In particular, we present new proofs for the spectral characterization of complete bipartite graphs and Tur\'{a}n graphs, as well as some new results related to the spectral characterization of the important family of strongly regular graphs. In addition, we introduce a new family of graphs, called \emph{the graphs of pyramids}, and prove that they are determined by their adjacency spectrum using tools from matrix analysis, such as Cauchy's interlacing theorem and Schur complements. The second part of the thesis studies generalized-Hamming graphs, a family of Cayley graphs that generalize the sub-family of Hamming graphs, and their complements. We classify the parameters for which these graphs are edge-transitive or even distance-transitive. Our analysis combines spectral methods, group-theoretic arguments, and techniques from the theory of association schemes. As an application, we derive closed-form expressions for the Lov\'{a}sz $\vartheta$-function of generalized-Hamming graphs and their complements whenever either the graph or its complement is edge-transitive. Overall, the results demonstrate how spectral methods provide powerful tools for understanding the structure and symmetry of graphs, and they suggest several directions for further research.

Figures

Figures reproduced from arXiv: 2607.17829 by the authors.

Figure 2.1
Figure 2.1. The graphs S4 = K1,4 and C4 ∪˙ K1 (i.e., a union of a 4-length cycle and an isolated vertex) are cospectral and nonisomorphic graphs (A-NICS graphs) on five vertices. These two graphs therefore cannot be determined by their adjacency matrix. computationally that all the connected nonisomorphic graphs on five vertices can be distinguished by their A-spectrum (see [49, Appendix A1]). Theorem 2.3.6. [50] All the regula… view at source ↗
Figure 2.2
Figure 2.2. {A, L, Q, L}-NICS regular graphs with 10 vertices. These cospectral graphs are noni￾somorphic because each of the two blue edges in G belongs to three triangles, whereas no such an edge exists in H. Example 2.3.7. [50] The following two regular graphs in [PITH_FULL_IMAGE:figures/full_fig_p036_2_2.png] view at source ↗
Figure 2.3
Figure 2.3. The friendship (windmill) graph F4 has 9 vertices, 12 edges, and 4 triangles. The term friendship graph in Definition 2.3.9 originates from the Friendship Theorem [59]. This theorem states that if G is a finite graph where any two vertices share exactly one common neighbor, then there exists a vertex that is adjacent to all other vertices. In this context, the adja￾cency of vertices in the graph can be interpreted s… view at source ↗
Figures from the paper (21 more)
Figure 2
Figure 2. Figure 2: ). The last observation follows from a property of a generalized friendship graph, which [PITH_FULL_IMAGE:figures/full_fig_p053_2.png]
Figure 2.4
Figure 2.4. Figure 2.4: The duplication graph Du(C5) (see Definition 2.5.11). Definition 2.5.12. [64] Let G1 and G2 be graphs on disjoint vertex sets of n1 and n2 vertices, and with m1 and m2 edges, respectively. The corona of G1 and G2, denoted by G1 ◦ G2, is a graph on n1 + n1n2 vertices …
Figure 2.5
Figure 2.5. Figure 2.5: The corona graph C4 ◦ (2 K1) (see Definition 2.5.12) consists of a single copy of C4 (represented by the black vertices) and four copies of 2 K1 (represented by the red vertices). Definition 2.5.13. [77] The edge corona of G1 and G2, denoted by G1♢G2, is defined as t…
Figure 2
Figure 2. Figure 2: ) [PITH_FULL_IMAGE:figures/full_fig_p060_2.png]
Figure 2.6
Figure 2.6. Figure 2.6: The edge-corona graph C4♢P3 (see Definition 2.5.13 [PITH_FULL_IMAGE:figures/full_fig_p061_2_6.png]
Figure 2.7
Figure 2.7. Figure 2.7: The duplication corona graph C4 ⊟ K2 (see Definition 2.5.14). Definition 2.5.15. Let G1 and G2 be graphs with disjoint vertex sets of n1 and n2 vertices, re￾spectively. Let Du(G1) be the duplication graph of G1 with the vertex set V(G1) ∪ U(G1), where V(G1) = {v1, . …
Figure 2.8
Figure 2.8. Figure 2.8: The duplication neighborhood corona K3 k K2 (see Definition 2.5.15). Definition 2.5.16. Let G1 and G2 be graphs with disjoint vertex sets of n1 and n2 vertices, re￾51 [PITH_FULL_IMAGE:figures/full_fig_p061_2_8.png]
Figure 2.9
Figure 2.9. Figure 2.9: The duplication edge corona K3 ⊞ K2 (see Definition 2.5.16). Definition 2.5.17. Consider two graphs G1 and G2 with n1 and n2 vertices and, respectively. The closed neighborhood corona of G1 and G2, denoted by G1 ⊠ G2, is a new graph obtained by cre￾ating n1 copies of…
Figure 2.10
Figure 2.10. Figure 2.10: The closed neighborhood corona of the 4-length cycle [PITH_FULL_IMAGE:figures/full_fig_p062_2_10.png]
Figure 2.11
Figure 2.11. Figure 2.11: The subdivision graph of a 4-length cycle, denoted by S( [PITH_FULL_IMAGE:figures/full_fig_p063_2_11.png]
Figure 2.12
Figure 2.12. Figure 2.12: The bipartite incidence graph of a length-4 cycle [PITH_FULL_IMAGE:figures/full_fig_p064_2_12.png]
Figure 2.13
Figure 2.13. Figure 2.13: The graph S(C4) ∨¨ B(P3) (see Definition 2.5.24). The black vertices represent the vertices of the length-4 cycle C4 and the vertices of the path P3. The additional vertices in the subdivision graph S(C4) are the four red vertices located at the bottom of this figur…
Figure 2.14
Figure 2.14. Figure 2.14: The graph S(C4) = ∨ B(P3) (see Definition 2.5.25). In comparison to [PITH_FULL_IMAGE:figures/full_fig_p065_2_14.png]
Figure 2.15
Figure 2.15. Figure 2.15: The graph S(C4) · ∨ B(P3) (see Definition 2.5.26). In comparison to [PITH_FULL_IMAGE:figures/full_fig_p066_2_15.png]
Figure 2.16
Figure 2.16. Figure 2.16: The graph S(C4) · ∨ B(P3) (see Definition 2.5.27). In comparison to [PITH_FULL_IMAGE:figures/full_fig_p066_2_16.png]
Figure 2
Figure 2. Figure 2: shows the NS and NNS joins of [PITH_FULL_IMAGE:figures/full_fig_p067_2.png]
Figure 2.17
Figure 2.17. Figure 2.17: The neighbors splitting (NS) and nonneighbors splitting (NNS) joins of the path [PITH_FULL_IMAGE:figures/full_fig_p068_2_17.png]
Figure 3.1
Figure 3.1. Figure 3.1: the graphs T6,3 , T6,2 and T6,1 3.2 Completely positive matrices and graphs A matrix A is completely positive if there exists a nonnegative matrix B s.t. A = BBT (see Defini￾tion 2.2.4). The readers are referred to [16] and [130] for the properties and the many appli…
Figure 3.2
Figure 3.2. Figure 3.2: The graphs B5 and B6. A characterization of completely positive graphs is : Theorem 3.2.6. [86] The following properties of a graph G are equivalent : 1. G is CP. 2. G does not contain a long odd cycle 3. The line graph of G is perfect. The equivalence between 2 and …
Figure 3.3
Figure 3.3. Figure 3.3: H3 Hence, H3 has 2 eigenvalues strictly smaller than −1, contradicting Theorem 3.4.5. If (v2, v3) < E2, there exists a vertex u3 ∈ V1 s.t. (v3, u3) < E. Assume that there exists u3 < {u1, u2} such that (v1, u3) ∈ E and (v2, u3) ∈ E (otherwise one of the previous cond…
Figure 3.5
Figure 3.5. Figure 3.5: Two cospectral graphs with 7 vertices G1 and G2 solution. The two graphs in [PITH_FULL_IMAGE:figures/full_fig_p084_3_5.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

164 extracted references · 21 canonical work pages

  1. [2]

    Con- structions of cospectral graphs with different zero forcing numbers,

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

    arXiv 2022

  2. [3]

    Abiad, W

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

    doi:10.37236/2383 2012

  3. [4]

    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 fromhttp: //ijmsi.ir/article-1-755-en.html

    2018

  4. [5]

    Automorphisms group of generalized Ham- ming graphs,

    F. Affif Chaouche and A. Berrachedi, “Automorphisms group of generalized Ham- ming graphs,”Electronic Notes in Discrete Mathematics, vol. 24, pp. 9–15, 2006. https://doi.org/10.1016/j.endm.2006.06.003

    work page doi:10.1016/j.endm.2006.06.003 2006

  5. [6]

    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

  6. [7]

    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 103

    doi:10.1016/j.laa.2014.06.010 2014

  7. [8]

    λ 1, isoperimetric inequalities for graphs, and supercon- centrators,

    N. Alon and V . D. Milman, “λ 1, isoperimetric inequalities for graphs, and supercon- centrators,”Journal of Combinatorial Theory, Series B, vol. 38, no. 1, pp. 73–88,

  8. [9]

    On MaxCut and the Lov ´asz theta function,

    I. Balla, O. Janzer, and B. Sudakov, “On MaxCut and the Lov ´asz theta function,” Proceedings of the American Mathematical Society, vol. 152, no. 5, pp. 1871–1879, 2024

    2024

Show all 164 references
  1. [10]

    Distance Laplacian spectra of various graph operations and its application to graphs on algebraic structures,

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

    2023 doi

  2. [11]

    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

  3. [12]

    A family of graphs that are determined by their normalized Laplacian spec- tra,

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

    2018 doi

  4. [13]

    Bipartite completely positive matrices,

    A. Berman and R. Grone, “Bipartite completely positive matrices,”Mathematical Proceedings of the Cambridge Philosophical Society, vol. 103, pp. 269–276, 1988. https://doi.org/10.1017/S0305004100064927

    1988 doi

  5. [14]

    Combinatorial results on completely positive matrices,

    A. Berman and D. Hershkowitz, “Combinatorial results on completely positive matrices,”Linear Algebra and its Applications, vol. 95, pp. 111–125, 1987. https://doi.org/10.1016/0024-3795(87)90234-1

    1987 doi

  6. [15]

    Completely positive house matrices,

    A. Berman and D. Shasha, “Completely positive house matrices,”Lin- ear Algebra and its Applications, vol. 436, no. 1, pp. 12–26, 2012. https://doi.org/10.1016/j.laa.2011.06.041

    2012 doi

  7. [16]

    Berman and N

    A. Berman and N. Shaked-Monderer,Completely Positive Matrices, World Scientific,

  8. [17]

    Disjoint unions of complete graphs characterized by their Laplacian spec- trum,

    R. Boulet, “Disjoint unions of complete graphs characterized by their Laplacian spec- trum,”Electronic Journal of Linear Algebra, vol. 18, no. 1, pp. 773–783, January

  9. [18]

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

  10. [19]

    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

  11. [20]

    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

    2011 doi

  12. [21]

    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 Mathematics, vol. 106–107, pp. 77–82, September

  13. [22]

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

    2022

  14. [23]

    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

  15. [24]

    Butler,Eigenvalues and Structures of Graphs

    S. Butler,Eigenvalues and Structures of Graphs. University of California, San Diego,

  16. [25]

    Butler, A note about cospectral graphs for the adjacency and normalized Laplacian matrices.Linear and Multilinear Algebra, 2010, 58(3), 387–390

    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

  17. [26]

    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

  18. [27]

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

    2016 doi

  19. [28]

    Butler and K

    S. Butler and K. Heysse, A cospectral family of graphs for the normalized Lapla- cian 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

  20. [29]

    A construction of cospectral graphs for the normalized Lapla- cian,

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

    2011 doi

  21. [30]

    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

  22. [31]

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

    C. Bu and J. Zhou, “Starlike trees whose maximum degree exceed 4 are determined by theirQ-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

  23. [32]

    Spectral characterizations of almost com- plete graphs,

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

    2014 doi

  24. [33]

    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

  25. [34]

    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

  26. [35]

    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 2008. https://doi.org/10.1016/j.laa....

    2008 doi

  27. [36]

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

  28. [37]

    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

  29. [38]

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

    1997 doi

  30. [39]

    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

  31. [40]

    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 106

    2015 doi

  32. [41]

    S. M. Cioab ˇa and M. R. Murty,A First Course in Graph Theory and Combinatorics, 2nd ed., Springer, 2021

    2021

  33. [42]

    Theory of Distance-Regular Graphs,

    A. M. Cohen, A. E. Brouwer, and A. Neumaier, “Theory of Distance-Regular Graphs,” inDistance-Regular Graphs, Springer, Berlin/Heidelberg, 1989, pp. 126–166

    1989

  34. [43]

    On Krawtchouk polynomials,

    R. Coleman, “On Krawtchouk polynomials,” 2011. Available athttps://hal. archives-ouvertes.fr/hal-00554167

    2011

  35. [44]

    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),”Bul- letin of the Belgian Mathematical Society - Simon Stevin, vol. 12, no. 5, pp. 707–718, January 2006. https://doi.org/10.36045/bbms/1136902608

    2006

  36. [45]

    D. M. Cvetkovi ´c, M. Doob, I. Gutman, and A. Torgaˇsev,Recent Results in the Theory of Graph Spectra, Elsevier, 1988

    1988

  37. [46]

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

    1995

  38. [47]

    A table of connected graphs on six vertices,

    D. Cvetkovi ´c and M. Petri ´c, “A table of connected graphs on six vertices,”Discrete Mathematics, vol. 50, pp. 37–49, 1984. https://doi.org/10.1016/0012-365X(84)90122- 4

    1984 doi

  39. [48]

    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

  40. [49]

    D. M. Cvetkovi ´c, P. Rowlinson, and S. Simi ´c,An Introduction to the Theory of Graph Spectra, Cambridge University Press, 2009. https://doi.org/10.1017/CBO9780511801518

    2009 doi

  41. [50]

    Which graphs are determined by their spec- trum?,

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

    2003 doi

  42. [51]

    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

  43. [52]

    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 107

    2011 doi

  44. [53]

    Complete split graph determined by its (signless) Lapla- cian spectrum,

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

    2016 doi

  45. [54]

    Das and P

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

    2023 doi

  46. [55]

    An algebraic approach to the association schemes of coding theory,

    P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Res. Rep. Suppl., 10:vi+97, 1973

    1973

  47. [56]

    Association schemes and coding theory,

    P. Delsarte and V . I. Levenshtein, “Association schemes and coding theory,”IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2477–2504, 1998

    1998

  48. [57]

    The complement of the path is determined by its spec- trum,

    M. Doob and W. H. Haemers, “The complement of the path is determined by its spec- trum,”Linear Algebra and its Applications, vol. 356, no. 1–3, pp. 57–65, November

  49. [58]

    Construction of cospectral graphs,

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

    2020 doi

  50. [59]

    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

  51. [60]

    On the spectrum of a complete multipartite graph,

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

    1980 doi

  52. [61]

    Fritz, A unified construction of semiring-homomorphic graph invariants,Journal of Algebraic Combinatorics, vol

    T. Fritz, A unified construction of semiring-homomorphic graph invariants,Journal of Algebraic Combinatorics, vol. 54, pp. 693–718, 2021.https://doi.org/10. 1007/s10801-020-00983-y

    2021

  53. [62]

    Frankl and R

    P. Frankl and R. L. Graham,Old and new proofs of the Erd¨ os-Ko-Rado Theorem, DIMACS, Center for Discrete Mathematics and Theoretical Computer Science, 1989

    1989

  54. [63]

    On the addressing problem for loop switch- ing,

    R. L. Graham and H. O. Pollak, “On the addressing problem for loop switch- ing,”The Bell System Technical Journal, vol. 50, no. 8, pp. 2495–2519, 1971. https://doi.org/10.1002/j.1538-7305.1971.tb02618.x

    1971

  55. [64]

    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 108

    1970 doi

  56. [65]

    Constructing cospectral graphs,

    C. Godsil and B. McKay, “Constructing cospectral graphs,”Aequationes Mathemati- cae, vol. 25, pp. 257–268, December 1982. https://doi.org/10.1007/BF02189621

    1982 doi

  57. [66]

    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

    2001 doi

  58. [67]

    Godsil and G

    C. Godsil and G. Royle,Algebraic Graph Theory, Springer-Verlag, New York, 2001

    2001

  59. [68]

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

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

    1956 doi

  60. [69]

    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 athttps://www.researchgate.net/ publication/304747396

    2016

  61. [70]

    Proving spectral uniqueness of graphs,

    W. H. Haemers, “Proving spectral uniqueness of graphs,” plenary talk inCombina- torics 2024, Carovigno, Italy, June 2024

    2024

  62. [71]

    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 inFinite Geometry and Combinatorics, 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

  63. [72]

    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

  64. [73]

    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

  65. [74]

    New constructions of nonregular cospectral graphs,

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

    2024 doi

  66. [75]

    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

  67. [76]

    R. A. Horn and C. R. Johnson,Matrix Analysis, 2nd ed., Cambridge University Press,

  68. [77]

    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

  69. [78]

    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

  70. [79]

    Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes,

    T. Jiang and A. Vardy, “Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes,”IEEE Transactions on Information Theory, vol. 50, no. 8, pp. 1655–1664, 2004. https://doi.org/10.1109/TIT.2004.832073

    2004

  71. [80]

    Complete multipartite graphs are determined by their dis- tance spectra,

    Y . L. Jin and X. D. Zhang, “Complete multipartite graphs are determined by their dis- tance spectra,”Linear Algebra and its Applications, vol. 448, pp. 285–291, February

  72. [81]

    Can one hear the shape of a drum?,

    M. Kac, “Can one hear the shape of a drum?,”The American Mathematical Monthly, vol. 73, no. 4, Part 2: Papers in Analysis, pp. 1–23, April 1966. Available fromhttp: //www.jstor.org/stable/2313748

    1966

  73. [82]

    On the construction of cospectral non- isomorphic bipartite graphs,

    M. R. Kannan, S. Pragada, and H. Wankhede, “On the construction of cospectral non- isomorphic bipartite graphs,”Discrete Mathematics, vol. 345, no. 8, pp. 1–8, August

  74. [83]

    Semi-supervised classification with graph convo- lutional networks,

    T. N. Kipf and M. Welling, “Semi-supervised classification with graph convo- lutional networks,” arXiv preprinthttps://arxiv.org/abs/1609.02907, 2016. https://doi.org/10.48550/arXiv.1609.02907

    2016 doi arXiv

  75. [84]

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

    G. Kirchhoff, “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

  76. [85]

    D. E. Knuth, The sandwich theorem,Electronic Journal of Combinatorics, vol. 1, 1994, pp. 1–48.https://doi.org/10.37236/1193

    1994 doi

  77. [86]

    Characterization of completely positive graphs,

    N. Kogan and A. Berman, “Characterization of completely positive graphs,”Discrete Mathematics, vol. 114, no. 1–3, pp. 297–304, 1993. https://doi.org/10.1016/0012- 365X(93)90302-D

    1993 doi

  78. [87]

    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 Applications, vol. 505, pp. 97–108, September 2016. http://dx.doi.org/10.1016/j.laa.2016.04.036 110

    2016 doi

  79. [88]

    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

  80. [89]

    Exponentially many graphs are determined by their spec- trum,

    I. Koval and M. Kwan, “Exponentially many graphs are determined by their spec- trum,”Quarterly Journal of Mathematics, vol. 75, no. 3, pp. 869–899, September

  81. [90]

    The graphs of pyramids are deter- mined by their spectrum,

    N. Krupnik and A. Berman, “The graphs of pyramids are deter- mined by their spectrum,”Linear Algebra and its Applications, 2024. https://doi.org/10.1016/j.laa.2024.04.029

    2024 doi

  82. [91]

    On the Transitivity of Generalized-Hamming Graphs and Their Complements,

    N. Krupnik, I. Sason, and A. Berman, “On the Transitivity of Generalized-Hamming Graphs and Their Complements,”In preparation, 2026

    2026

  83. [92]

    The square of some generalized Hamming graphs,

    Y . Li, J. Zhang, and M. Wang, “The square of some generalized Hamming graphs,”Mathematics, vol. 11, no. 11, paper 2487, 2023. https://doi.org/10.3390/math11112487

    2023 doi

  84. [93]

    Lidl and H

    R. Lidl and H. Niederreiter,Finite Fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1996

    1996

  85. [94]

    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

  86. [95]

    Graphs determined by theirA α-spectra,

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

    2019 doi

  87. [96]

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

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

    2003 doi

  88. [97]

    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

  89. [99]

    On the Shannon capacity of a graph,

    L. Lov ´asz, “On the Shannon capacity of a graph,”IEEE Transac- tions on Information Theory, vol. 25, no. 1, pp. 1–7, January 1979. https://doi.org/10.1109/TIT.1979.1055985

    1979

  90. [100]

    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

  91. [101]

    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

  92. [102]

    F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes, vol. 16, Elsevier, 1977

    1977

  93. [103]

    An introduction to coding for constrained systems,

    B. H. Marcus, R. M. Roth, and P. H. Siegel, “An introduction to coding for constrained systems,” Lecture notes, 2001

    2001

  94. [104]

    On the spectral characterization of the union of complete multi- partite graph and some isolated vertices,

    H. Ma and H. Ren, “On the spectral characterization of the union of complete multi- partite 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

  95. [105]

    On the matrix equationX ′X=A,

    J. E. Maxfield and H. Minc, “On the matrix equationX ′X=A,”Proceed- ings of the Edinburgh Mathematical Society, vol. 13, no. 2, pp. 125–129, 1962. https://doi.org/10.1017/S0013091500025672

    1962 doi

  96. [106]

    The Lov ´asz bound and some generalizations,

    R. J. McEliece, E. R. Rodemich, and H. C. Rumsey, “The Lov ´asz bound and some generalizations,”J. Combin. Inform. Syst. Sci., vol. 3, pp. 134–152, 1978

    1978

  97. [107]

    D. M. Mesner, “An investigation of certain combinatorial properties of partially bal- anced 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 ...

    1956 doi

  98. [108]

    Some remarks on the square graph of the hypercube,

    S. M. Mirafzal, “Some remarks on the square graph of the hypercube,”arXiv preprint arXiv:2101.01615, 2021. https://doi.org/10.48550/arXiv.2101.01615

    2021 doi arXiv

  99. [109]

    On spectral clustering: Analysis and an algo- rithm,

    A. Y . Ng, M. I. Jordan, and Y . Weiss, “On spectral clustering: Analysis and an algo- rithm,”Advances in Neural Information Processing Systems, vol. 14, 2001

    2001

  100. [110]

    Lapla- cian spectral determination of path-friendship graphs,

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

    2021

  101. [111]

    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

    2010 doi

  102. [112]

    Starlike trees are determined by their Laplacian spec- trum,

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

    2007 doi

  103. [113]

    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

  104. [114]

    The core of a complementary prism,

    M. Orel, “The core of a complementary prism,”Journal of Algebraic Combinatorics, vol. 58, pp. 589–609, 2023. https://doi.org/10.1007/s10801-023-01236-4

    2023 doi

  105. [115]

    The PageRank Citation Ranking: Bringing Order to the Web,

    L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank Citation Ranking: Bringing Order to the Web,”Stanford InfoLab, Tech. Rep. 1999-66, Jan. 1998,https: //ilpubs.stanford.edu/422/

    1999

  106. [116]

    The symmetric eigenvalue problem,

    B. N. Parlett, “The symmetric eigenvalue problem,”Classics in Applied Mathematics,

  107. [117]

    Pisanski and B

    T. Pisanski and B. Servatius,Configurations from a Graphical Viewpoint, Springer,

  108. [118]

    Hypercontractivity of spherical averages in Hamming space,

    Y . Polyanskiy, “Hypercontractivity of spherical averages in Hamming space,”SIAM Journal on Discrete Mathematics, 33(2):731–754, 2019

    2019

  109. [119]

    Phylogeny numbers of generalized Hamming graphs,

    C. Qian, Y . Wu, and Y . Xiong, “Phylogeny numbers of generalized Hamming graphs,” Bulletin of the Malaysian Mathematical Sciences Society, vol. 45, pp. 2733–2744,

  110. [120]

    Conic formulations of graph homomorphisms,

    D. E. Roberson, “Conic formulations of graph homomorphisms,”Journal of Algebraic Combinatorics, vol. 43, no. 4, pp. 877–913, 2016. https://doi.org/10.1007/s10801- 016-0665-y

    2016 doi

  111. [121]

    S. Y . El Rouayheb, C. N. Georghiades, E. Soljanin and A. Sprintson, Bounds on Codes Based on Graph Theory,Proceedings of the 2007 IEEE International Symposium on Information Theory, pp. 1876–1879, Nice, France, June 2007.https://doi.org/ 10.1109/ISIT.2007.4557151 113 [122]The...

    2007

  112. [123]

    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 fromhttps://www.researchgate. net/publication/269007309

    1980

  113. [124]

    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

  114. [125]

    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

  115. [126]

    An example showing that Schrijver’sϑ-function need not upper bound the Shannon capacity of a graph,

    I. Sason, “An example showing that Schrijver’sϑ-function need not upper bound the Shannon capacity of a graph,”AIMS Mathematics, vol. 10, no. 7, pp. 15294–15301,

  116. [127]

    On Spectral Graph Determination,

    I. Sason, N. Krupnik, S. Hamud, and A. Berman, “On Spectral Graph Determination,” Mathematics, 2025,13, 549. https://doi.org/10.3390/math13040549

    2025 doi

  117. [128]

    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

  118. [129]

    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

  119. [130]

    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

  120. [131]

    Normalized cuts and image segmentation,

    J. Shi and J. Malik, “Normalized cuts and image segmentation,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888–905, 2000. https://doi.org/10.1109/34.868688

    doi

  121. [132]

    The uniqueness of the L 2 association scheme,

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

    1959

  122. [133]

    https://doi.org/10.1007/s40840-022-01338-5

    doi

  123. [134]

    Some Propertice of the Spectrum of Graph,

    J. H. Smith, “Some Propertice of the Spectrum of Graph,” in:Combinatorial Struc- tures 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

  124. [135]

    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 2024. http://dx.doi.org/10.48550/arXiv.2407.05653

    2024 doi arXiv

  125. [136]

    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

  126. [137]

    Struik and W

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

    2010

  127. [138]

    L. M. Tolhuizen, The generalized Gilbert–Varshamov bound is implied by Tur ´an’s theorem,IEEE Transactions on Information Theory, vol. 43, no. 5, pp. 1605–1606, 1997.https://doi.org/10.1109/18.623158

    1997 doi

  128. [139]

    Line perfect graphs,

    L. E. Trotter Jr., “Line perfect graphs,”Mathematical Programming, vol. 12, no. 1, pp. 255–259, 1977. https://doi.org/10.1007/BF01593742

    1977 doi

  129. [140]

    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

  130. [141]

    How to distinguish cospectral graphs,

    S. Wananiyakul, J. Steuding, and J. Tongsomporn, “How to distinguish cospectral graphs,”Mathematics, vol. 10, no. 24, paper 4802, 2022. https://doi.org/10.3390/math10244802

    2022 doi

  131. [142]

    Generalized spectral characterization of graphs revisited,

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

    2013 doi

  132. [143]

    A simple arithmetic criterion for graphs being determined by their gen- eralized spectra,

    W. Wang, “A simple arithmetic criterion for graphs being determined by their gen- eralized 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

  133. [144]

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

    2010 doi

  134. [145]

    Haemers’ conjecture: an algorithmic perspective,

    W. Wang and W. Wang, “Haemers’ conjecture: an algorithmic perspective,”Experimental Mathematics, pp. 1–28, April 2024. https://doi.org/10.1080/10586458.2024.2337229

    2024

  135. [146]

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

    W. Wang and C. X. Xu, “A sufficient 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

  136. [147]

    Expander codes,

    M. Sipser and D. A. Spielman, “Expander codes,”IEEE Transactions on Information Theory, vol. 42, no. 6, pp. 1710–1722, 2002. 114

    2002

  137. [148]

    Improving the Gilbert- Varshamov bound by graph spectral method,

    Z. Ye, H. Zhang, R. Li, J. Wang, G. Yan, and Z. Ma, “Improving the Gilbert- Varshamov bound by graph spectral method,”arXiv preprint arXiv:2104.01403, 2021. https://doi.org/10.48550/arXiv.2104.01403

    2021 doi arXiv

  138. [149]

    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

  139. [150]

    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

  140. [151]

    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

  141. [152]

    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 Mathematics, vol. 312, pp. 1591–1595, May 2012. http://dx.doi.org/10.1016/j.disc.2012.02.002 116

    2012 doi

  142. [161]

    Treewidth of generalized Hamming graph, bipartite Kneser graph and generalized Petersen graph,

    Y . Wang, M. Cao, Z. Lv, and M. Lu, “Treewidth of generalized Hamming graph, bipartite Kneser graph and generalized Petersen graph,”The Electronic Journal of Combinatorics, vol. 33, no. 1, paper P1.7, 2026. https://doi.org/10.37236/12892

    2026 doi

  143. [1985]

    https://doi.org/10.1016/0095-8956(85)90092-9

    doi

  144. [1992]

    https://doi.org/10.1016/0012-365X(92)90532-K

    doi

  145. [1998]

    http://dx.doi.org/10.1137/1.9781611971163

    doi

  146. [2002]

    https://doi.org/10.1016/S0024-3795(02)00323-3

    doi

  147. [2003]

    https://doi.org/10.1142/5153

    doi

  148. [2008]

    Available fromhttps://escholarship.org/uc/item/3qd9g26t

  149. [2009]

    https://doi.org/10.13001/1081-3810.1344

  150. [2012]

    https://doi.org/10.1017/CBO9781139020411 109

    doi

  151. [2013]

    https://doi.org/10.1007/978-0-8176-8364-1

    doi

  152. [2014]

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

    2014 doi

  153. [2022]

    https://doi.org/10.1016/j.disc.2022.112916

    2022

  154. [2023]

    https://doi.org/10.11948/20210446

    doi

  155. [2024]

    https://doi.org/10.1093/qmath/haae030

    doi

  156. [2025]

    https://doi.org/10.3934/math.2025685

    doi

Pith tools

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