{"id":"a72e8213-5308-4350-8b7c-8516549c78d0","arxiv_id":"2508.04137","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper claims a complete classification of connected graphs whose Cartesian, Kronecker, strong, and lexicographic products coincide, plus a spectral graph theory by-product.","lead":"This math paper claims to characterize every connected graph for which the four standard graph products (Cartesian, Kronecker, strong, lexicographic) are isomorphic to one another, and it reports a new family of non-distance-regular graphs with an unusual eigenvalue property. A specialist would care if the characterization is correct, but only the abstract was readable in the supplied copy, so the proofs could not be checked.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No specific mathematical flaw found; proof body is unreadable, so the universal completeness claim is unverifiable as supplied.","rationale":"The reader's UNVERDICTED verdict is appropriate. The abstract could be correct, and the claimed results are sufficiently concrete to be testable, but they are not testable from the corrupted copy. I did not find a specific mathematical inconsistency, but there is no machine-checked proof, no reproducible code, and no readable proof body to credit; the central claim rests entirely on unreadable text. An exhaustive small-graph check would catch typical completeness errors and would materially change my assessment if it fails. If it passes, the classification would still need proof inspection for full certification, but the risk of a simple missed edge case would drop. Therefore I recommend leaving the verdict unchanged as UNVERDICTED with low confidence.","tokens_in":16681,"tokens_out":4116,"duration_ms":54881,"concrete_test":"Retrieve the uncorrupted LaTeX source from arXiv (or request a clean copy from the authors), then use nauty to exhaustively test the theorem's characterization for all connected graphs on at most 7 vertices: for every pair (G,H), compute the four products and verify that the paper's stated conditions exactly match which products are isomorphic. Any mismatch—especially involving K1, K2, C4, K_{m,n}, or equal-factor cases—would falsify the 'complete' classification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—a complete classification of connected simple graphs whose standard products are isomorphic, plus a new family with fewer than d+1 distinct distance eigenvalues—cannot be checked from the supplied text. The proof sections are mojibake, and an unrelated arXiv header (2508.04120, cs.CV) is embedded, so no lemma or edge-case discussion is readable. I find no internal contradiction in the abstract, but the theorem is universal: it asserts a classification for every connected simple graph. Such claims are fragile to missed cases (small orders, complete multipartite graphs, factor graphs with nontrivial automorphisms or equal factors) and to whether 'isomorphic' for the Kronecker product is intended only when both products are connected. Without a readable proof, the most serious issue is not a known falsehood but the inability to rule out such an omission. This is a verifiability/evidence concern, not an identified mathematical error. The spectral by-product has the same status: the claimed eigenvalue count requires exact distance-matrix computations that are not visible.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The abstract claims a complete classification of all simple connected graphs for which the Cartesian, Kronecker (direct), strong, and lexicographic products are isomorphic, and a by-product identification of a novel family of non-distance-regular graphs with fewer than d+1 distinct distance eigenvalues, where d is the diameter. If true, this would resolve, for all connected simple graphs, the isomorphism relations among the four standard products and would give a new data point on Problem 4.3 of [2]. However, the supplied full text is almost entirely corrupted: the body is mojibake, only fragments of definitions, statements, and table-like arrays are decipherable, and an unrelated arXiv header (2508.04120v1, cs.CV) is embedded mid-manuscript. Consequently, no proof, lemma, or edge-case discussion can be inspected, and the central claims cannot be verified from the supplied version.","tokens_in":16845,"tokens_out":2554,"duration_ms":31276,"significance":"If the classification theorem and the spectral by-product are correct, the paper would be a substantial contribution to the theory of graph products: complete characterizations of when standard products coincide are rare, and the proposed family would address a recognized open problem (Problem 4.3 of [2]). The abstract's framing is plausible and consistent with existing results that product isomorphisms are highly restrictive. However, the contribution is unverifiable as submitted because the proof body is unreadable. The novelty claim, the completeness of the classification, and the exact distance-eigenvalue count all depend on technical arguments that are not visible. No internal contradiction is apparent from the abstract, but a universal claim of this type is fragile to missed edge cases, so the lack of readable proof is a load-bearing deficiency.","major_comments":[{"comment":"The proof body is corrupted mojibake. After the abstract, the text becomes largely unreadable; only isolated fragments of definitions and statements survive, and no proof can be followed. The central completeness theorem is therefore uncheckable. The authors must provide a clean, readable version in which every lemma, proof, and edge-case discussion can be inspected.","section":"Full text (Sections 1–5)"},{"comment":"The abstract's 'complete characterization' is not precisely specified in the readable portion. It is unclear whether the isomorphism is between the four products formed from the same pair of factors, whether disconnected products are included, and how trivial cases such as K1 or equal factors are treated. The unreadable body does not resolve these points. A precise theorem statement with all hypotheses and edge cases is needed.","section":"Abstract / theorem statement"},{"comment":"The claimed new family of non-distance-regular graphs with fewer than d+1 distinct distance eigenvalues requires exact distance-matrix computations. None of these computations are visible in the corrupted text. Since this is a separate advertised contribution, the construction and verification must be readable and checkable.","section":"Spectral by-product"},{"comment":"An unrelated arXiv identifier, 2508.04120v1 [cs.CV], appears embedded in the manuscript. This indicates a corrupted source or compilation problem rather than a mathematical argument. It must be removed, and the actual paper text supplied intact.","section":"Embedded header (p. 1–2)"}],"minor_comments":[{"comment":"The abstract cites [2] but no readable bibliography is available. A full reference list must be included in a clean version.","section":"References"},{"comment":"Several fragments appear to be tables or example arrays, but they are not decipherable in mojibake. Ensure these render correctly in the resubmitted version.","section":"Tables/examples"}],"recommendation":"uncertain","confidential_remarks":"There is no identifiable mathematical error, but the submission cannot be evaluated: the proof text is unreadable and even contains an unrelated cs.CV header. This looks like a rendering/encoding failure of the source file rather than a deliberate defect in the mathematics. I recommend asking the authors to resubmit a correctly compiled PDF, after which a full technical review will be possible."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the one-line take: this is a plausible and potentially clean classification result, but the copy I can actually read is unusable, so nobody should certify anything from it yet.\n\nWhat's actually new, judging from the abstract: the authors claim a complete characterization of connected simple graphs for which the four standard products—Cartesian, Kronecker, strong, lexicographic—are isomorphic, and they use that to construct a family of non-distance-regular graphs with fewer than d+1 distinct distance eigenvalues, which is exactly the kind of counterexample that Problem 4.3 in [2] asks for. That's a natural question and the abstract is written in a focused, falsifiable way. If the theorem is right, it's a genuine contribution.\n\nThe problem is that the supplied full text is corrupted. It's mojibake, and it even has an unrelated header from arXiv:2508.04120v1 (cs.CV). So I could not inspect a single proof step. The stress-test note did not find a specific flaw either. So the soft spot is not a known error; it is that the universal claim—'for all connected simple graphs'—is unverifiable from what I have. I'd want a referee to check small orders, K1, disconnected cases (or the connectedness conventions for Kronecker products), and equal factors. The spectral by-product requires exact distance-matrix computations that are also invisible.\n\nOn the citation pattern: the abstract references Problem 4.3 of [2] and positions itself against 'current approaches,' but I can't see the bibliography or prior work relation. No sign of circularity from the abstract.\n\nWho this is for: people working on product graph isomorphism or distance-regular graphs and spectral questions. If the proof checks out, it's a nice paper for a graph theory journal. But as things stand, the right verdict is 'needs the actual manuscript.' This is not a takedown; it's a request for readable evidence.\n\nMy recommendation: send it to peer review. The claim is significant enough to merit referee time, and the editors should obtain a clean copy. If the proofs are solid, accept; if they have gaps, that's what referees are for. I would not cite it from this version.","headline":"A plausible classification claim that I cannot verify because the supplied text is corrupted; worth sending to a referee with a readable copy.","tokens_in":17375,"tokens_out":4343,"would_cite":false,"duration_ms":41257,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C60","05C76","05C50","05C12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a complete classification of the connected simple graphs whose Cartesian, Kronecker, strong, or lexicographic products are isomorphic, and exhibits a new family of non-distance-regular graphs with fewer than $d+1$ distinct","keywords":["graph products","Cartesian product","Kronecker product","strong product","lexicographic product","graph isomorphism","distance-regular graphs","distance eigenvalues"],"falsifier":"Enumerate all connected graphs up to order 8, form all pairs of the four products, and test isomorphism with a canonical-labeling program; any isomorphism outside the paper's listed families would falsify the classification. For the spectral by-product, take the smallest members of the new family, compute the distance matrix, count its distinct eigenvalues, and compare with $d+1$; a member that is distance-regular or has at least $d+1$ distinct distance eigenvalues would falsify that claim.","tokens_in":16530,"feed_emoji":"","tokens_out":7888,"duration_ms":89069,"temperature":0.7,"pith_summary":"The paper asks when two of the four standard graph products—Cartesian, Kronecker (direct), strong, and lexicographic—are isomorphic as graphs, given that the factors are simple and connected. The authors claim a complete characterization: all pairs $(G,H)$ for which any two of $G \\square H$, $G \\times H$, $G \\boxtimes H$, and $G[H]$ are isomorphic are explicitly described. If true, this settles a basic recognition question, because whether two product graphs coincide can be read off from the factors rather than checked case by case. A by-product of the same construction is a new infinite family of graphs that are not distance-regular but have fewer than $d+1$ distinct distance eigenvalues, with $d$ their diameter; this bears on the open Problem 4.3 in [2].","feed_headline":"Four graph products: isomorphism fully classified","feed_subtitle":"For every connected simple graph the exceptions are listed, plus a new family with few distance eigenvalues.","key_machinery":"The central objects are the four product constructions themselves, each defined on the same vertex set $V(G) \\times V(H)$ with different adjacency rules: Cartesian ($G \\square H$), Kronecker/direct ($G \\times H$), strong ($G \\boxtimes H$), and lexicographic ($G[H]$). The classification argument works through invariants that distinguish the products—degrees, diameters, bipartiteness, and spectral information—and reduces isomorphism possibilities to conditions on the factors. For the spectral by-product, the carrying object is the distance matrix of the newly constructed graphs: the authors count its distinct eigenvalues and compare the count with the diameter $d$, using distance-regularity as","core_discovery":"The paper's central claim is that the isomorphism problem for the four standard graph products has a complete answer: for simple connected graphs $G$ and $H$, an isomorphism between any two of $G \\square H$, $G \\times H$, $G \\boxtimes H$, and $G[H]$ occurs if and only if the pair $(G,H)$ belongs to one of the explicitly listed families. The proof builds the products, compares structural invariants, and isolates every exceptional pair. As a separate but related discovery, the paper constructs a new family of graphs, obtained from these products, whose members are not distance-regular but whose distance matrices have fewer than $d+1$ distinct eigenvalues, where $d$ is the diameter; the paper r","pith_inferences":["The paper's classification is stated for connected factors; a direct extension to disconnected graphs, or to products of more than two factors, is likely to involve additional finite exceptions but has the same invariant-based structure.","The new family suggests that the gap between the number of distinct distance eigenvalues and $d+1$ can be controlled by product parameters; one could search for members with a prescribed gap.","The explicit nature of the characterization would allow a computational check: the isomorphism type of a product graph built from two connected factors can be recognized from factor properties alone, without directly solving a graph isomorphism instance."],"forward_implications":["For any two connected simple graphs, whether the Cartesian and Kronecker products are isomorphic—and similarly for any other pair of the four products—is decided by checking a short list of conditions on the factors.","The classification covers all simple connected graphs, so the earlier case-by-case examples become instances of a single complete description.","The by-product family gives an explicit infinite set of non-distance-regular graphs with fewer than $d+1$ distinct distance eigenvalues, providing a new test case for Problem 4.3 in [2].","Because the constructed family is explicit, its distance spectra can be computed and used to study how the number of distinct distance eigenvalues relates to diameter."],"supporting_citations":[],"fun_headline_variants":["Graph product isomorphism: all exceptions listed","When are graph products isomorphic? Answer inside","New non-distance-regular graphs from products","Complete isomorphism test for all 4 products"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The load-bearing premise is that the case analysis in the proof is complete: every lemma is correct, and no edge case involving trivial, complete, bipartite, or one-vertex graphs has been missed.","fun_headline_variants_meta":{"raw":{"variants":["Graph product isomorphism: all exceptions listed","When are graph products isomorphic? Answer inside","New non-distance-regular graphs from products","Complete isomorphism test for all 4 products"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000681,"raw_usage":{"total_tokens":2862,"prompt_tokens":607,"completion_tokens":2255,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":351,"completion_tokens_details":{"reasoning_tokens":2201}},"tokens_in":351,"tokens_out":2255,"duration_ms":20352,"temperature":1.0,"reasoning_tokens":2201,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:51:20.226198+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all connected graphs up to order 8, form all pairs of the four products, and test isomorphism with a canonical-labeling program; any isomorphism outside the paper's listed families would falsify the classification. For the spectral by-product, take the smallest members of the new family, compute the distance matrix, count its distinct eigenvalues, and compare with $d+1$; a member that is distance-regular or has at least $d+1$ distinct distance eigenvalues would falsify that claim.","supporting_citations":[],"review_version":1}