A characterization of all graphs cospectral to the double star $P_2(1,n)$

Emily Barranca; Michael D. Barrus

REVIEW 1 major objections 6 minor 10 references

A characterization of all graphs cospectral to the double star $P_2(1,n)$

T0 review · 1 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that $P_2(1,n)$ is determined by its adjacency spectrum exactly when $n$ is odd or $n=2$, and it enumerates all nonisomorphic cospectral graphs for even $n$.

desk verdict Smart, likely correct classification of cospectral mates for P2(1,n), but the written proof has a load-bearing gap: Theorem 3.6 never rules out A–D edges, and Lemma 3.8 depends on their absence. read the letter →

arxiv 2506.06934 v1 pith:EX6KN2I6 submitted 2025-06-07 math.CO

Emily Barranca , Michael D. Barrus This is my paper

classification math.CO MSC 05C5005C05

keywords doublestarcospectralgraphsdeterminedbyspectrumadjacencycharacteristicpolynomialSachscoefficientstreespectraP_2(1n)

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 gives a complete spectral classification for one family of diameter-three trees, the double stars $P_2(1,n)$ formed by joining one leaf to one center of a star with $n$ leaves. It proves that if a graph $G$ has the same adjacency spectrum as $P_2(1,n)$, then $G$ is isomorphic to $P_2(1,n)$ whenever $n$ is odd or $n=2$; for even $n>2$, $G$ is one of the explicitly constructed graphs $A_{n/2}+(n/2-1)K_1$, with a second graph $B_{n/4}+(3n/4-2)K_1$ appearing exactly when $4$ divides $n$ and $n\ge 8$. Consequently $P_2(1,n)$ is determined by its spectrum in the odd case and for $n=2$, and in every even case the nonisomorphic cospectral mates are explicitly listed. This answers a natural question left open by the classical result that almost all trees are not determined by their spectrum.

What carries the argument

The machinery is the Sachs-coefficient expansion of the characteristic polynomial, stated in the paper as Theorem 3.1: coefficients are sums over subgraphs whose components are cycles or single edges. Eigenvalue interlacing, Theorem 3.2, rules out induced subgraphs $2K_2$, $R$, and $P_2(2,2)$, which forces the four-part $A$-$B$-$C$-$D$ chain. Inside that chain, the third nonzero coefficient of $\phi(G')$ counts 2-matchings pairing an edge from a vertex of $A$ with an edge from a vertex of $D$, giving the term $abcd$ in the polynomial. Equating the resulting polynomial with $\phi(P_2(1,n))$ is what selects the two surviving structural families.

What would settle it

Construct the four-layer configuration with $|A|=1$, $|B|=2$, $|C|=2$, $|D|=2$ and add a single edge joining $A$ to $D$. The Sachs count behind the third coefficient changes from $8$ to $6$, so the characteristic polynomial would differ from the claimed formula; checking whether such a graph is cospectral to any $P_2(1,n)$ would show whether the missing edge-exclusion hides an unlisted cospectral graph.

Watch

Extended reading notes

Core claim

The central claim is that cospectrality to $P_2(1,n)$ is extremely restrictive. For $n\ge 3$, any graph cospectral to $P_2(1,n)$ has a unique nontrivial component $G'$ whose nonisolated vertices split into four nonempty layers $A,B,C,D$, with the induced subgraphs on $A\cup B$, $B\cup C$, and $C\cup D$ complete bipartite. The characteristic polynomial of $G'$ is forced to be $x^{a+b+c+d} - (ab+bc+cd)x^{a+b+c+d-2} + abcd x^{a+b+c+d-4}$, where $a,b,c,d$ are the layer sizes. Matching this with the double-star polynomial $x^{n+3} - (n+2)x^{n+1} + n x^{n-1}$ leaves only two structural families, the $A$-construction with $c=1,d=2$ and the $B$-construction with $b=2,d=2$. For odd $n$ neither family is realizable, which is the paper's proof that $P_2(1,n)$ is itself the only graph with that spectrum; for even $n>2$ the surviving parameters produce the listed one or two nonisomorphic cospectral mates.

Load-bearing premise

The classification rests on the structural assertion that no edges join the outermost layers $A$ and $D$ of the four-part component; the proof establishes only that the three adjacent layer pairs induce complete bipartite graphs, and if an $A$-$D$ edge existed the characteristic-polynomial count in Lemma 3.8 would no longer hold.

Editorial extensions

If this is right

For every odd $n$ and for $n=2$, any graph with the same adjacency spectrum as $P_2(1,n)$ is isomorphic to the double star itself, so $P_2(1,n)$ is a graph determined by its spectrum in those cases.
For even $n>2$, the paper's classification states that there is exactly one nonisomorphic cospectral graph when $n=4$ or $n$ is congruent to $2$ modulo $4$, and exactly two nonisomorphic cospectral graphs when $4$ divides $n$ and $n\ge 8$.
Consequently the adjacency spectrum of $P_2(1,n)$ fixes the isomorphism type except for these explicitly listed exceptions, so no hidden cospectral mates exist outside the two construction families.
All constructed cospectral mates are disconnected graphs of the form a connected piece plus isolated vertices, so within this family the spectrum cannot distinguish connectedness even though it pins the nontrivial component to one of two shapes.
The proof supports the broader pattern that graphs cospectral to double stars contain complete bipartite subgraphs $K_{2,k}$; in this family the pattern appears as the $B\cup C$ or $C\cup D$ layer.

Reading between the lines

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

The proof as written leaves open whether an edge between the outermost layers $A$ and $D$ can exist; because such an edge changes the 2-matching count in Lemma 3.8, the classification would need an additional argument excluding it, and a graph with one such edge would be the natural place to look for a missed cospectral mate.
The same four-layer coefficient comparison could be attempted for other double stars $P_2(a,b)$ with $a>1$; the paper's conjecture that cospectral mates will contain some $K_{2,k}$ substructure could be tested by writing the analogous parameter equations.
If the characterization survives the missing edge-exclusion step, it yields a cheap recognition test: a graph is cospectral to $P_2(1,n)$ exactly when its nontrivial component is one of the three listed shapes with matching layer sizes, so checking cospectrality reduces to counting vertices and edges rather than computing eigenvalues.

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.

Desk Editor's Note

read the letter

The paper gives a clean answer to a natural question: P2(1,n) is determined by its spectrum exactly when n is odd or n=2, and for even n it exhibits the cospectral mates (A_a and B_a with isolated vertices). The constructions are explicit and the characteristic polynomial computations for A_a and B_a check out. The strategy — force a chain structure from forbidden induced subgraphs, then count coefficients — is coherent and standard, and the writing is clear. The result is new and would be a nice completion of the DS story for the P2(1,n) family.

The soft spot is real and it sits between Theorem 3.6 and Lemma 3.8. Theorem 3.6 partitions the non-path vertices into A, B, C, D and proves that G[A∪B], G[B∪C], and G[C∪D] are complete bipartite. It never addresses edges between A and D. Lemma 3.8 then asserts that a vertex in A and a vertex in D are not adjacent, and uses that to count 2-matchings contributing abcd to the x^{a+b+c+d-4} coefficient. If an A–D edge exists, that count changes, and the displayed characteristic polynomial is no longer justified. This is not a pedantic worry: there are graphs satisfying all the structural conclusions of Theorem 3.6 that do contain an A–D edge (for example, a=1,b=1,c=1,d=2 with one such edge), and their Sachs counts differ. Since Theorem 3.9 derives the parameter equations from Lemma 3.8's polynomial, the parity conclusion in Theorem 3.10 is currently unsupported.

The gap is probably repairable — the theorem itself is plausible and the rest of the argument is solid — but as written the proof is incomplete. I would not desk-reject this; it deserves referee time, provided the authors are asked to either prove nonadjacency of A and D or redo the coefficient count allowing such edges. The classification is the kind of concrete result the DS community cares about.

One small note: the abstract omits the n=2 exceptional case from the DS statement, even though the main theorem includes it. The stray 'Posthumously' in the author line is odd but presumably a tribute and not a mathematical issue.

Referee Report

1 major / 6 minor

Summary. The paper studies the adjacency spectrum of double stars P2(a,b), focusing on P2(1,n). Section 2 gives explicit graphs A_a and B_a such that A_a+(a-1)K_1 is cospectral to P2(1,2a) and B_a+(3a-2)K_1 is cospectral to P2(1,4a), proving that P2(1,2k) is not DS for k>1. Section 3 attempts to prove the converse: any graph cospectral to P2(1,n) for odd n (or n=2) is isomorphic to P2(1,n). The proof strategy is to use eigenvalue interlacing to force the nontrivial component into a four-part A,B,C,D chain, compute its characteristic polynomial from Sachs coefficients, and solve the resulting parameter equations. The main result is stated as Theorem 3.11: P2(1,n) is DS if and only if n is odd or n=2.

Significance. If the proof is completed, the paper would provide a complete characterization of all graphs cospectral to P2(1,n), including the exact number of nonisomorphic cospectral mates for even n. This is a valuable addition to the spectral graph theory literature, where complete characterizations of cospectral graphs for infinite families are rare. The constructions in Section 2 are explicit and their characteristic-polynomial computations are checkable. The central obstruction is the missing exclusion of A-D edges in the structural theorem; until that gap is repaired or the Sachs count is modified, the characterization is not established. With a correct proof of that point, the result would merit publication.

major comments (1)

[Theorem 3.6 and Lemma 3.8] The proof of Theorem 3.6 establishes only that G[A∪B], G[B∪C], and G[C∪D] are complete bipartite; it never rules out edges between A and D. The claimed conclusion in Figure 3.3 therefore does not follow. This is not a stylistic gap: the graph with A={a}, B={b}, C={c}, D={d1,d2} and edges ab, bc, cd1, cd2, ad1 is bipartite, 2K2-free, R-free, P5-free, and satisfies the three complete-bipartite conclusions of Theorem 3.6, yet it contains an A-D edge and has characteristic polynomial x^5 - 5x^3 + 2x, so Theorem 3.6 is false as stated. The missing exclusion is load-bearing because Lemma 3.8 explicitly asserts 'v_a and v_d are not adjacent in G′' and uses that assertion to count the coefficient of x^{a+b+c+d-4} as abcd. With an A-D edge present, both the edge count and the 2-matching contribution change (for example, with a=1,b=2,c=2,d=2 and one A-D edge, the Sachs coefficient is 6 rather than the abcd=8 asserted by Lemma 3.8). Since Lemma 3.8 supplies the only characteristic polynomial used in Theorem 3.9 to derive the identities n=bcd and n+2=ab+bc+cd, the parity conclusion in Theorem 3.10 and the main theorem rest on an unproved structural premise. Please add a proof that A-D edges cannot occur, or extend Lemma 3.8 to include their contribution and re-derive the parameter equations.

minor comments (6)

[Abstract] The abstract states that P2(1,n) is DS when n is odd, but Theorem 3.11 adds the exceptional case n=2; please update the abstract to match the theorem.
[Section 1] The statement that P2(0,n) is DS if and only if n+1 is prime is false for n=0, since P2(0,0)=K2 is DS while 1 is not prime; the statement should be restricted to n≥1.
[Theorem 3.6 proof] The sentence 'We will omit the C∪D case, which is similar to A∪B' leaves one of the three claimed structural conclusions without a written argument; in light of the A-D gap, the proof of this part should be spelled out.
[Lemma 3.5 proof] The sentence 'By symmetry, the preceding paragraph also shows that we can assume t is not adjacent to z4' is not self-evident; when t is adjacent to z2, symmetry of the path would normally treat z3 analogously to z1, not z4.
[Theorem 2.4 proof] In the displayed computation of ϕ(B_a), the term 'G{v,d,u1,w,u2,y,u3,c}' is missing a backslash and should read 'G\{v,d,u1,w,u2,y,u3,c}'.
[Conclusion] The sentence 'It is tempting to conjecture that P2(1,n) for odd values of n are the only DS double stars, but we recall that P2(5,5) is DS' is self-contradictory as written; please rephrase to state that P2(5,5) is an exception to the tempting conjecture.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the derivation is self-contained, and the notable A-D adjacency gap is a non-circular missing proof, not a definitional reduction.

full rationale

The derivation is not circular. The main result Theorem 3.11 is obtained by taking a graph G cospectral to P2(1,n), using eigenvalue interlacing (Theorems 3.1-3.2) to forbid certain induced subgraphs (Corollary 3.4), proving a structural partition (Theorem 3.6), computing the characteristic polynomial of the nontrivial component from edge counts and 2-matching counts (Lemma 3.8), and then equating coefficients with the known double-star polynomial to constrain the parameters (Theorems 3.9-3.10). The cospectral assumption is an input, not a renamed conclusion, and the coefficient equalities are standard constraints, not fitted parameters renamed as predictions. The only self-citation is Theorem 2.3, whose full proof is deferred to the first author's thesis; that result is background for non-DS double stars and is not needed to prove Theorem 3.11, since Theorem 2.4 is proved independently in the text. The genuine gap identified by a close reading is non-circular: Lemma 3.8 asserts that v_a and v_d are not adjacent in G' without proving that Theorem 3.6 forbids A-D edges, and the 2-matching count abcd depends on that assertion. This is a missing structural proof, i.e., a correctness risk, not an equivalence-by-construction or a fitted-input-as-prediction, so it does not raise the circularity score. The score of 1 reflects only the presence of one background self-citation, which is not load-bearing.

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

The central claim rests on standard spectral graph theory tools and one implicit structural lemma not stated in the paper. No free parameters are fitted, and no new entities are introduced.

assumptions (5)

standard math Schwenk's recursive formula for characteristic polynomials (Theorem 2.2)
Used in Section 2 to compute phi(A_a) and phi(B_a).
standard math Sachs coefficient formula (Theorem 3.1)
Used in Lemma 3.7 and Lemma 3.8 to compute characteristic polynomial coefficients.
standard math Eigenvalue interlacing theorem (Theorem 3.2)
Used in Corollary 3.4 to exclude induced subgraphs with second largest eigenvalue at least 1 or with more than two positive eigenvalues.
domain assumption A connected bipartite graph with no induced 2K2 and no induced P4 is complete bipartite (implicit)
Used in Theorem 3.6 to conclude G[A union B] and G[B union C] are complete bipartite from P4-freeness; the paper does not state this lemma explicitly.
standard math Spectrum of a graph determines number of vertices and edges
Used implicitly when equating characteristic polynomials of cospectral graphs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A characterization of all graphs cospectral to the double star $P_2(1,n)$." pith.science (2026). https://pith.science/paper/EX6KN2I6

@misc{pith2026250606934,
  author       = {Pith},
  title        = {Pith review of: A characterization of all graphs cospectral to the double star $P_2(1,n)$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EX6KN2I6}},
  note         = {Machine review of arXiv:2506.06934}
}

abstract

We examine the adjacency spectrum of trees with diameter three, also referred to as double stars. Using $P_2(a,b)$ to denote a double star with $ a$ and $b$ leaves at its respective endpoints, we discuss graphs which are cospectral to double stars for various parameters $a$ and $b$. In particular, we give constructions for graphs cospectral to $P_2(1,2k)$ for integers $k$. Lastly, we show that the double star $P_2(1,n)$ is determined by its spectrum when $n$ is odd. That is, if a graph $G$ cospectral to $P_2(1,n)$ for odd $n$, then $G$ is isomorphic to $P_2(1,n)$.

Figures

Figures reproduced from arXiv: 2506.06934 by the authors.

**Figure 1.1.** The graph K1,4 pictured on the left is cospectral to C4 + K1, pictured on the right. a1 a2 . . . am b1 b2 . . . bn [PITH_FULL_IMAGE:figures/full_fig_p002_1_1.png] view at source ↗

**Figure 1.2.** The double star P2(m, n) remains open for double stars. We start by considering the smallest cases of double stars. Note that P2(0, n) is isomorphic to the star graph K1,n+1, which has spectrum { √ n + 1(1) , 0 (n) , − √ n + 1(1)}. Then P2(0, n) is DS if and only if n+ 1 is prime. Let G be a graph cospectral to K1,n+1; then G has only one positive eigenvalue and hence one nontrivial component. Furthermore G is P4-fr… view at source ↗

**Figure 2.1.** The graphs Aa and Ba. Thus for a ≥ 2, the double star P2(1, 2a) is cospectral to the graph Aa + (a − 1)K1. We give another construction for a nonisomorphic graph cospectral to the double star P2(1, 4a) for integers a ≥ 1. By Theorem 2.1, the double star P2(1, 4a) has characteristic polynomial ϕ(P2(1, 4a)) = x 4a+3 − (4a + 2)x 4a+1 + 4ax4a−1 . Let Ba be the graph obtained by taking a copy of the complete bipartite gr… view at source ↗

Figures from the paper (5 more)

**Figure 3.1.** Figure 3.1: The graph R has approximate eigenvalues {2.247, 0.802, 0.555, −0.555, −0.802, −2.247}. component is a cycle or is isomorphic to K2. Then the characteristic polynomial ϕ(G) of G is given by ϕ(G) = |V X (G)| n=0 anx |V (G)|−n , where an = X H∈Gn (−1)k(H) 2 c(H) . Theor…

**Figure 3.2.** Figure 3.2: The graph R present as an induced subgraph of the graph H, a contradiction. u x v y A B C D [PITH_FULL_IMAGE:figures/full_fig_p006_3_2.png]

**Figure 3.3.** Figure 3.3: General structure of a the nontrivial component [PITH_FULL_IMAGE:figures/full_fig_p006_3_3.png]

**Figure 3.4.** Figure 3.4: The graph G′ such that c = 1, d = 2, and b is greater than 2. This corresponds to structure (i) given in Theorem 3.6. u x v y A B C D [PITH_FULL_IMAGE:figures/full_fig_p009_3_4.png]

**Figure 3.5.** Figure 3.5: The graph G′ with b = 2, d = 2, and c greater than 1. This graph has structure (ii) defined in Theorem 3.6. Such a graph is isomorphic to P2(1, d). To be cospectral to P2(1, n), it must be the case that d = n, and this graph is isomorphic to our original graph. Lastl…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

W. H. Haemers A.E. Brouwer.Spectra of Graphs. New York, NY: Springer, 2011

work page 2011
[2]

Recognizing the P4-structure of bipartite graphs

L. Babel, A. Brandst¨ adt, and V.B. Le. “Recognizing the P4-structure of bipartite graphs”. In:Discrete Applied Mathematics93.2 (1999), pp. 157–168.issn: 0166-218X

work page 1999
[3]

Recognizing induced subgraph and tree structure from the adjacency spectrum of a graph

E. Barranca. “Recognizing induced subgraph and tree structure from the adjacency spectrum of a graph”. PhD thesis. University of Rhode Island, 2024

work page 2024
[4]

G. Royle C. Godsil.Algebraic Graph Theory: volume 207 of Graduate Texts in Mathematics. Springer, 2001

work page 2001
[5]

Simi´ c D

S. Simi´ c D. Cvetkovi´ c P. Rowlinson.An Introduction to the Theory of Graph Spectra (London Mathe- matical Society Student Texts). Cambridge University Press, 2009

work page 2009
[6]

Which graphs are determined by their spectrum?

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

work page 2003
[7]

No starlike trees are cospectral

M. Lepovi´ c and I. Gutman. “No starlike trees are cospectral”. In:Discrete Mathematics242 (2002), pp. 291–296

work page 2002
[8]

On the spectral radii of weighted double stars

F. Liu, Q. Huang, and X. Tao. “On the spectral radii of weighted double stars”. In:Appl. Math. Lett. 25 (Apr. 2012), pp. 667–671

work page 2012

Show all 10 references

[9]

Almost All Trees Are Cospectral

A. J. Schwenk. “Almost All Trees Are Cospectral”. In:New Directions in the Theory of Graphs(1973), pp. 275–307

1973
[10]

Computing the Characteristic polynomial of a graph

A.J. Schwenk. “Computing the Characteristic polynomial of a graph”. In:Graphs and Combinatorics. Lecture Notes in Mathematics406 (1974). 10

1974

Pith tools

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

[1] [1]

W. H. Haemers A.E. Brouwer.Spectra of Graphs. New York, NY: Springer, 2011

work page 2011

[2] [2]

Recognizing the P4-structure of bipartite graphs

L. Babel, A. Brandst¨ adt, and V.B. Le. “Recognizing the P4-structure of bipartite graphs”. In:Discrete Applied Mathematics93.2 (1999), pp. 157–168.issn: 0166-218X

work page 1999

[3] [3]

Recognizing induced subgraph and tree structure from the adjacency spectrum of a graph

E. Barranca. “Recognizing induced subgraph and tree structure from the adjacency spectrum of a graph”. PhD thesis. University of Rhode Island, 2024

work page 2024

[4] [4]

G. Royle C. Godsil.Algebraic Graph Theory: volume 207 of Graduate Texts in Mathematics. Springer, 2001

work page 2001

[5] [5]

Simi´ c D

S. Simi´ c D. Cvetkovi´ c P. Rowlinson.An Introduction to the Theory of Graph Spectra (London Mathe- matical Society Student Texts). Cambridge University Press, 2009

work page 2009

[6] [6]

Which graphs are determined by their spectrum?

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

work page 2003

[7] [7]

No starlike trees are cospectral

M. Lepovi´ c and I. Gutman. “No starlike trees are cospectral”. In:Discrete Mathematics242 (2002), pp. 291–296

work page 2002

[8] [8]

On the spectral radii of weighted double stars

F. Liu, Q. Huang, and X. Tao. “On the spectral radii of weighted double stars”. In:Appl. Math. Lett. 25 (Apr. 2012), pp. 667–671

work page 2012