REVIEW 1 major objections 5 minor 10 references
Cartesian Prime Graphs and Cospectral Families
T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Cartesian products of cospectral graphs yield larger cospectral families.
desk verdict Main Cartesian-product method for cospectral families is correct; the triplet-counting corollary overcounts and the Omega bound is unsupported. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the Cartesian product $G \square H$, whose spectrum is the sum of the two factor spectra: every eigenvalue of the product is $\lambda + \mu$ for eigenvalues $\lambda$ of $G$ and $\mu$ of $H$. This makes cospectrality automatic once all seed graphs in a family share a spectrum. The non-isomorphism half of the proof is carried by the unique Cartesian prime factorization theorem, which says a connected graph factors into primes in essentially one way. The three conditions in Theorem 2.1 are precisely the hypotheses that force an isomorphism between two products to align the factors, so duplicate graphs cannot appear.
What would settle it
Search exhaustively through connected graphs up to a modest vertex count, computing spectra and Cartesian prime factorizations: if no pair of cospectral families with different spectra satisfies one of the three conditions, or no mutually coprime cospectral seed family appears, the construction cannot be instantiated. Alternatively, one explicit pair of seed families satisfying a condition whose $pq$ Cartesian products contain two isomorphic graphs would refute Theorem 2.1.
Extended reading notes
Core claim
The central claim is Theorem 2.1: if $G = \{G_1,\dots,G_p\}$ and $H = \{H_1,\dots,H_q\}$ are families of connected mutually cospectral graphs whose spectra differ between families, and at least one of three conditions holds—all graphs are Cartesian prime, all vertex counts between the two families are coprime, or no prime factor is shared—then $F = \{G_i \square H_j : 1 \le i \le p,\, 1 \le j \le q\}$ is a connected cospectral family of size $pq$. The proof combines eigenvalue addition across Cartesian products with the uniqueness of Cartesian prime factorization; the conditions eliminate exactly the isomorphisms that could make two products the same graph. The paper also proves a relaxed version that yields at least $p+q-1$ graphs when only one coprime pair exists, counts the resulting new cospectral triples, and shows that a seed family of $p$ mutually coprime cospectral graphs on $n$ vertices yields a family of size $\binom{k+p-1}{k}$ on $nk$ vertices for every $k \ge 1$.
Load-bearing premise
The construction presumes that seed families actually exist: two connected cospectral families satisfying one of the three factor conditions, or, for the size-amplification theorem, one family of $p$ mutually coprime cospectral graphs on $n$ vertices; the paper does not exhibit such seed families and notes that they are rare.
Editorial extensions
If this is right
- If one of the three conditions holds, two seed families of sizes $p$ and $q$ yield a connected cospectral family of size $pq$, so repeated use can multiply family sizes whenever suitable seeds exist.
- If only one pair of graphs, one from each family, is coprime, the construction still produces a connected cospectral family of size at least $p+q-1$.
- The relaxed construction produces at least $(p-1)(q-1) + (p-1)\binom{q}{3} + (q-1)\binom{p}{3} + \binom{p+q-1}{3}$ new connected cospectral triples, giving $\Omega(pq^3 + qp^3)$ under the relaxed conditions.
- A single connected cospectral family of $p$ mutually coprime graphs on $n$ vertices is enough to generate a connected cospectral family of size $\binom{k+p-1}{k}$ on $nk$ vertices for every integer $k \ge 1$.
- Condition 3 is the most general of the three: whenever Condition 1 or Condition 2 holds, Condition 3 holds as well, so the $pq$ result applies to the widest class of inputs.
Reading between the lines
- The true bottleneck is finding seed families: a targeted computer search for even one cospectral family of mutually coprime connected graphs would immediately activate Theorem 2.4 and produce families for every $k$; the paper leaves that search as future work.
- Because cospectrality of products is inherited from eigenvalue addition, the same product idea may extend to other matrices such as the Laplacian or to other product operations, though the non-isomorphism part would need new conditions matched to those settings.
- The triplet count in Corollary 2.3 suggests the method is a strong generator of cospectral triples even in the relaxed regime, so the practical value may lie less in the largest family size and more in the abundance of new cospectral triples produced from small seeds.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a construction of larger cospectral graph families using Cartesian products. Given two connected mutually cospectral families G and H with different spectra, the family F = {G□H} is shown to be connected and cospectral of size pq under each of three conditions: all factors Cartesian prime; vertex counts of cross-pairs coprime; or no shared Cartesian prime factor. A relaxed setting (one coprime cross-pair) yields a subfamily of size p+q−1. A corollary attempts to count newly generated cospectral triplets, claiming an Ω(pq^3+qp^3) lower bound. A separate theorem states that a cospectral family of p mutually coprime graphs on n vertices yields a family of size C(k+p−1,k) on nk vertices for every k.
Significance. The main construction (Theorems 2.1 and 2.2) is sound and exploits unique Cartesian factorization in a clean way; if seed families exist, it gives a useful method for producing cospectral graphs with guaranteed non-isomorphism. Theorem 2.4 is a valid conditional amplification statement, and the observation that Cartesian-prime cospectral families satisfy its hypothesis gives it substance. The paper's headline quantitative claim, however, rests on Corollary 2.3, which is flawed: its counting ignores isomorphisms among the generated graphs and is false as stated. The paper would be publishable after a substantial revision of the counting claims and abstract.
major comments (1)
- [§2, Corollary 2.3] The proof counts index-labelled triplets but does not establish that these correspond to distinct isomorphism classes. Under the hypotheses of Theorem 2.2, F_{ij} outside F'' may be isomorphic to a member of F''. For instance, let T1 and T2 be non-isomorphic cospectral trees and set G1=T1□K2, G2=T2□K2, H1=T2□K3, H2=T1□K3. Then G and H satisfy the hypotheses of Theorem 2.2, but F22=(T2□K2)□(T1□K3) ≅ (T1□K2)□(T2□K3)=F11. The corollary counts {F21,F12,F22} as a new triplet from the (p−1)(q−1) term, yet as an isomorphism class it is the same as the 3-subset {F11,F21,F12} already counted by C(p+q−1,3). For p=q=2 the formula gives 2 triplets while only 1 exists. Similar overlaps are not excluded among the row/column terms either. Hence the Ω(pq^3+qp^3) lower bound advertised in the abstract is not established by the given proof.
minor comments (5)
- [Abstract] The abstract says 'Under the strictest condition, our method generates O(p^3q^3) new cospectral triplets'; since Theorem 2.1 gives a family of size pq, the number of triplets is Θ(p^3q^3). Please replace O with Θ or Ω to state a lower bound.
- [§2, Theorem 2.4] Theorem 2.4 is stated conditionally, but the abstract claims to 'use the existence of specific cospectral families.' Please name at least one such family (for example, cospectral trees, which are Cartesian prime) to make the application concrete.
- [§3, Conclusion] The conclusion claims that the Godsil–McKay switching method 'involves an NP-hard condition verification step.' No proof or reference is given for this assertion; please clarify or cite a source.
- [§2, proof of Theorem 2.2] The phrase 'for any nontrivial choice of b and c' should be stated more formally as 'for all b,c > 1'.
- [§2, Theorem 2.4] The term 'Cartesian prime factorizations' is misleading when the U_i are not themselves prime; 'factorizations into the U_i' would be more accurate.
Circularity Check
No significant circularity: the construction is conditional on explicitly stated seed families and relies on external classical theorems.
full rationale
The paper's derivations are conditional constructions, not circular ones. Theorem 2.1 takes two mutually cospectral families with different spectra plus one of three factorization conditions and proves that the Cartesian-product family is cospectral and non-isomorphic. The proof invokes external results: Sabidussi's unique Cartesian prime factorization [6], spectral additivity of Cartesian products [7], and the cancellation law for Cartesian products [7]. None of these results is supplied by the present authors, and the non-isomorphism arguments do not assume the conclusion. Theorem 2.2 explicitly assumes the existence of coprime members G and H in the input families and constructs a subset of size p+q-1; the size bound follows directly from mutual cospectrality and the coprimality of G1 and H1, with non-isomorphism argued via the cancellation law. Corollary 2.3 is a counting statement about triplets within the constructed family; the skeptic's objection that some counted triplets may be isomorphic to previously counted ones is a potential overcounting error in the enumeration, not a circularity, because the lower bound is not obtained by assuming the existence of the new triplets it claims to produce. Theorem 2.4 is explicitly conditional on the existence of a connected cospectral family of p mutually coprime graphs on n vertices; the construction then counts multisets of Cartesian factors using a standard stars-and-bars formula [10], and mutual coprimality ensures distinct multisets give non-isomorphic graphs. The closing remark that a family of connected, cospectral, Cartesian prime graphs satisfies the condition is offered as a sufficient condition, not as evidence that such families exist. No fitted parameters are renamed as predictions, no target result is smuggled into hypotheses, and no load-bearing self-citation appears; references [6]-[10] are to independent classical literature. The central claims are conditional and would stand or fall on the existence of suitable seed families, which the authors explicitly acknowledge as rare. Hence the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- standard math Every connected graph has a unique Cartesian prime factorization (Sabidussi 1959).
- standard math The spectrum of a Cartesian product is the multiset sum of the spectra of its factors.
- standard math For connected nontrivial graphs, G1□H ~= G2□H implies G1 ~= G2.
- standard math Cospectral graphs have the same number of vertices.
- domain assumption The input families G and H are connected, pairwise non-isomorphic, mutually cospectral, and the spectra of G differ from those of H.
Cite this review
Pith. "Pith review of Cartesian Prime Graphs and Cospectral Families." pith.science (2026). https://pith.science/paper/DPKKV46F
@misc{pith2026250524358,
author = {Pith},
title = {Pith review of: Cartesian Prime Graphs and Cospectral Families},
year = {2026},
howpublished = {\url{https://pith.science/paper/DPKKV46F}},
note = {Machine review of arXiv:2505.24358}
}
abstract
We introduce a method for constructing larger families of connected cospectral graphs from two given cospectral families of sizes $p$ and $q$. The resulting family size depends on the Cartesian primality of the input graphs and can be one of $pq$, $p + q - 1$, or $\max(p, q)$, based on the strictness of the applied conditions. Under the strictest condition, our method generates $O(p^3q^3)$ new cospectral triplets, while the more relaxed conditions yield $\varOmega(pq^3 + qp^3)$ such triplets. We also use the existence of specific cospectral families to establish that of larger ones.
Reference graph
Works this paper leans on
-
[1]
Godsil, C.D. and McKay, B.D., 1982. Constructing cospec tral graphs. Aequationes Mathematicae, 25, pp.257-268
work page 1982
-
[2]
Abiad, A., van de Berg, N. and Simoens, R., 2024. Switchin g methods of level 2 for the construction of cospectral graphs. arXiv preprint arXi v:2410.07948
arXiv 2024
-
[3]
Bapat, R.B. and Karimi, M., 2016. Construction of cospec tral regular graphs. Mat. Vesnik, 68(1), pp.66-76
work page 2016
-
[4]
Haythorpe, M. and Newcombe, A., 2020. Constructing fami lies of cospectral regular graphs. Combinatorics, Probability and Computing, 29(5), pp.664-671
work page 2020
-
[5]
Van Dam, E.R. and Haemers, W.H., 2003. Which graphs are de termined by their spectrum?. Linear Algebra and its applications, 373, pp.24 1-272
work page 2003
-
[6]
Sabidussi, G., 1959. Graph multiplication. Mathematis che Zeitschrift, 72(1), pp.446- 457
work page 1959
-
[7]
Imrich, W., Klavzar, S. and Rall, D.F., 2008. Topics in gr aph theory: Graphs and their Cartesian product. CRC Press
work page 2008
-
[8]
Imrich, W. and Peterin, I., 2007. Recognizing Cartesian products in linear time. Dis- crete mathematics, 307(3-5), pp.472-483
work page 2007
Show all 10 references
-
[9]
Graph isomorphism in quasipolyno mial time
Babai, L., 2016, June. Graph isomorphism in quasipolyno mial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Comput ing (pp. 684-697)
2016
-
[10]
Introduction to combinatorics
Erickson, M.J., 2013. Introduction to combinatorics. John Wiley & Sons. 5
2013
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.