{"id":"37551f4e-24b2-4c75-9923-b1782f7a3bb2","arxiv_id":"2412.20775","paper_version":6,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of spectral graph determination with new alternative proofs that Turán graphs and certain complete bipartite graphs are determined by their adjacency spectra.","lead":"This paper surveys what is known about when graphs are uniquely determined by their eigenvalues, and it adds new proofs of some classical results in that area. It is a useful reference for researchers studying spectral graph theory and cospectral graphs.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.18's Turán spectrum and the A-DS proof of Theorem 4.21 are correct, but Theorem 4.7(2)'s asserted cospectral mate K_{a,b}∨K_r is not cospectral with K_{p,q} (Eq. 4.6 fails; the disjoint union is the correct witness), and Corollary 4.9 is false — n=6 has three DS complete bipartite graphs.","rationale":"Good-faith reading: this is a survey of X-DS/cospectral graph theory whose original contributions are new proofs of three known results — Turán graphs are A-DS (Theorem 4.21) via an explicit spectrum (Theorem 4.18), the characterization of A-DS complete bipartite graphs (Theorem 4.7), and the Petersen graph being DS (Corollary 4.32). I stress-tested the Turán argument because it is the paper's centerpiece and the reader's weakest assumption. The spectrum formula in Theorem 4.18 is correct: re-deriving Eq. (4.15) from Butler's join formula (Lemma 4.17) with n1 = q(k−s), n2 = (q+1)s, r1 = q(k−s−1), r2 = (q+1)(s−1) reproduces the printed multiplicities of −q−1, −q, 0 and the two special eigenvalues; Example 4.20 is consistent. The proof of Theorem 4.21 is also sound: Lemma 4.23 only needs the true bound 'at most k−1 negative eigenvalues' (by interlacing, a principal submatrix has no more negative eigenvalues than the full matrix; K_{k+1} has k), and Lemmas 4.24–4.27 (Smith's theorem, Turán's theorem, pigeonhole rebalancing) are correct. So the central claim holds up. The real defects are elsewhere. (1) Theorem 4.7(2) is invalid as printed: the non-DS witness is built as G = K_{a,b}∨K_r and Eq. (4.6) asserts σ(G) = σ(K_{p,q}), but K_{a,b} is not regular (so Lemma 4.17 does not apply), the join is complete tripartite K_{a,b,r} with p+q−3 zero eigenvalues, and its nonzero eigenvalues satisfy λ³ − λ(ab+ar+br) − 2abr = 0, matching σ(K_{p,q}) only when abr = 0; the smallest case {1,4}, (a,b,r) = (2,2,1) gives σ(K_{2,2}∨K_1) = {−2, [0]², 1±√5} ≠ σ(K_{1,4}). The disjoint union K_{a,b}∪K_r is the correct witness, so the theorem's statement (known from [37]) stands but the printed proof does not. (2) Corollary 4.9 is false: on 6 vertices, K_{1,5}, K_{2,4}, and K_{3,3} are all DS since 5, 8, and 9 admit no factor pair with sum below the trivial one and feasible vertex bound; its proof also conflates the vertex count a+b with the product ab. (3) Remark 4.19's 'k−2 negative eigenvalues' for irregular T(n,k) is false: the smaller special eigenvalue in Eq. (4.15) is negative (the two quotient eigenvalues have product r1r2 − n1n2 < 0), so the count is k−1, contradicting the paper's own Theorem 4.15 and Example 4.20; this does not harm Theorem 4.21, which uses only 'at most k−1'. The Petersen proof is fine. Verdict: the reader's CONDITIONAL is confirmed; the Turán contribution is valid but the manuscript still contains one false corollary, one invalid new proof (easily fixed), and a false eigenvalue count, so it must be corrected before being treated as authoritative.","tokens_in":41119,"tokens_out":46429,"duration_ms":381565,"concrete_test":"Verify Eq. (4.6) on the smallest non-minimizer: take {p,q} = {1,4}, the factor pair (a,b) = (2,2) with ab = 4 = pq and a+b = 4 < 5, so r = 1. The printed witness G = K_{2,2}∨K_1 has 8 edges and spectrum {−2, [0]², 1±√5}, while σ(K_{1,4}) = {−2, [0]³, 2} has 4 edges; the spectra differ, so the asserted cospectrality fails. Recompute with the disjoint union K_{2,2}∪K_1, whose spectrum is {−2, [0]³, 2} = σ(K_{1,4}): this confirms the correct witness and the theorem's statement. Separately, for Remark 4.19, count negative eigenvalues in Eq. (4.15) for T(17,7) as in Example 4.20: the special eigenvalue 6(1−√2) ≈ −2.485 is negative, giving 2+3+1 = 6 = k−1 negatives, not k−2 = 5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's flagship result survives scrutiny: re-deriving Eq. (4.15) from Butler's join formula (Lemma 4.17) with n1 = q(k−s), n2 = (q+1)s, r1 = q(k−s−1), r2 = (q+1)(s−1) reproduces the printed spectrum, and Lemmas 4.23–4.27 prove Theorem 4.21 correctly; the interlacing step needs only the true bound that a cospectral G has at most k−1 negative eigenvalues. The load-bearing defect is in the second advertised new proof. In Theorem 4.7(2), the non-DS witness is G = K_{a,b}∨K_r and Eq. (4.6) asserts σ(G) = σ(K_{p,q}) = {−√pq, [0]^{p+q−2}, √pq}. This is false: K_{a,b} is not regular (Lemma 4.17 is inapplicable), K_{a,b}∨K_r = K_{a,b,r} has p+q−3 zero eigenvalues, and its three nonzero eigenvalues satisfy λ³ − λ(ab+ar+br) − 2abr = 0, which matches σ(K_{p,q}) only if abr = 0. For {p,q} = {1,4}, (a,b,r) = (2,2,1), the printed witness K_{2,2}∨K_1 has spectrum {−2, [0]², 1±√5} and 8 edges, while σ(K_{1,4}) = {−2, [0]³, 2} has 4 edges, so Eq. (4.6) fails; the disjoint union K_{2,2}∪K_1 is the true mate. Hence the printed proof of Theorem 4.7(2) is invalid, and Corollary 4.9 is false as stated: on 6 vertices all of K_{1,5}, K_{2,4}, K_{3,3} are DS. Separately, Remark 4.19's count of k−2 negative eigenvalues for irregular T(n,k) is wrong: the smaller member of the special pair in Eq. (4.15) is negative (quotient eigenvalues have product r1r2 − n1n2 < 0), so the count is k−1, contradicting the paper's Theorem 4.15 and Example 4.20; Theorem 4.21 is unaffected since it uses only 'at most k−1'.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":41722,"tokens_out":11369,"duration_ms":93277,"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":[{"comment":"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).","section":"§4.2, Corollary 4.9"},{"comment":"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.","section":"§4.3.1, Remark 4.19"},{"comment":"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.","section":"§4.2, Theorem 4.7(2)"}],"minor_comments":[{"comment":"The word 'normialized' in the introductory sentence of Section 2.3.1 should be 'normalized'.","section":"§2.3.1"},{"comment":"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.","section":"§4.2, Theorem 4.7(2)"},{"comment":"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.","section":"§4.3.1, Lemma 4.23"},{"comment":"In reference [71], the title contains 'external problem' and should read 'extremal problem'.","section":"References"},{"comment":"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.","section":"§6.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is a survey with new proofs, and the Turán proof appears correct, but the complete bipartite section contains substantive errors that are fixable: Theorem 4.7(2) can be repaired by using the disjoint union witness, and Corollary 4.9 must be corrected or removed. I recommend major revision and a careful proofreading of the newly claimed results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nHere's my read. The paper is a broad survey of spectral graph determination with two advertised new proofs. The Turán part holds up: Theorem 4.18 derives the explicit spectrum of irregular Turán graphs from Butler's join formula, and the stress-test re-derivation reproduces it. Lemmas 4.23–4.27 then prove Theorem 4.21 correctly; the interlacing argument only needs the true bound that a cospectral graph has at most k−1 negative eigenvalues. That is a genuinely useful alternative proof of a known result, and the closed-form spectrum for irregular Turán graphs is a nice addition.\n\nThe complete bipartite section has real problems. Theorem 4.7(2) claims that when {p,q} is not an AM-minimizer, the graph G = K_{a,b}∨K_r is cospectral with K_{p,q} (Eq. 4.6). That is false. The join is a complete multipartite graph with p+q−3 zero eigenvalues and characteristic polynomial λ(λ² − (ab+ar+br)λ − 2abr) up to the zero part; it matches the spectrum of K_{p,q} only when abr=0. The correct cospectral witness is the disjoint union K_{a,b}∪K_r, which is exactly what part (1) of the theorem already produces. So part (2) is invalid as written, even though the intended characterization is the known Corollary 3.1 of Ma–Ren. Corollary 4.9 is worse: it claims exactly one DS complete bipartite graph on n vertices, but for n=6 the graphs K_{1,5}, K_{2,4}, and K_{3,3} are all DS, since each has a unique AM-minimizer factorization. The “almost all” conclusion is right, but the uniqueness statement is not.\n\nThere is also a minor error in Remark 4.19: for irregular T(n,k) the negative eigenvalue count is k−1, not k−2, because the smaller of the two special eigenvalues in Eq. (4.15) is negative. This does not affect Theorem 4.21, which only uses the bound “at most k−1”.\n\nThe survey itself is solid and well-referenced. The authors are explicit about which results are new proofs rather than new theorems, and the citation pattern is honest; the load-bearing new proof (Turán) does not rely on the results it proves. The Petersen graph corollary is a standard application but correctly stated.\n\nWho is this for? Someone wanting a compact overview of DS/NICS results and a clean derivation of the Turán spectrum. It deserves a serious referee, but the referee should require the complete bipartite section to be fixed before publication.\n\nRecommendation: send to peer review; the paper is worth the referee's time, and the errors are repairable.","headline":"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.","tokens_in":42282,"tokens_out":2192,"would_cite":true,"duration_ms":23221,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C75","05C76"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["spectral graph theory","spectral graph determination","cospectral nonisomorphic graphs","Haemers' conjecture","Turán graphs","graph operations","adjacency spectrum","DS graphs"],"falsifier":"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.","tokens_in":40929,"feed_emoji":"📐","tokens_out":16637,"duration_ms":141734,"temperature":0.7,"pith_summary":"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.","feed_headline":"New proof shows every Turán graph is uniquely fixed by its spectrum","feed_subtitle":"A closed-form eigenvalue formula rules out every graph with matching eigenvalues, a concrete step toward Haemers' conjecture.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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)$."],"supporting_citations":[{"why":"Provides the earlier proof that Turán graphs are A-DS (its Theorem 3.3), the result the paper reproves by a different route.","marker":"[37]"},{"why":"Supplies the characterization of graphs with exactly one positive eigenvalue used to conclude a cospectral graph is complete multipartite plus isolated vertices.","marker":"[75]"},{"why":"Supplies the join-spectrum formula used to derive the closed-form spectrum of irregular Turán graphs from two regular complete multipartite graphs.","marker":"[73]"},{"why":"Gives the spectrum of complete multipartite graphs, the starting point for the regular-case spectrum and for the join components.","marker":"[72]"},{"why":"Turán's theorem, used in the extremal edge-count arguments that force the part sizes of a cospectral graph to be q and q+1.","marker":"[71]"},{"why":"Supplies Cauchy's interlacing theorem, used to rule out a clique of size k+1 in a graph cospectral with T(n,k).","marker":"[47]"}],"fun_headline_variants":["Every Turán graph is uniquely fixed by its spectrum","New proof: Turán graphs have no cospectral twins","Closed-form spectrum shows Turán graphs are A-DS","Spectrum determines Turán graphs: a step toward Haemers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Every Turán graph is uniquely fixed by its spectrum","New proof: Turán graphs have no cospectral twins","Closed-form spectrum shows Turán graphs are A-DS","Spectrum determines Turán graphs: a step toward Haemers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000568,"raw_usage":{"total_tokens":2621,"prompt_tokens":809,"completion_tokens":1812,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":425,"completion_tokens_details":{"reasoning_tokens":1745}},"tokens_in":425,"tokens_out":1812,"duration_ms":13595,"temperature":1.0,"reasoning_tokens":1745,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:11:58.750515+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On the spectral characterization of the union of complete multipartite graph and some isolated vertices,","cited_arxiv_id":null,"evidence_quote":"Provides the earlier proof that Turán graphs are A-DS (its Theorem 3.3), the result the paper reproves by a different route."},{"cited_title":"Which wheel graphs are determined by their Laplacian spectra?","cited_arxiv_id":null,"evidence_quote":"Supplies Cauchy's interlacing theorem, used to rule out a clique of size k+1 in a graph cospectral with T(n,k)."}],"review_version":1}