Pith. sign in

REVIEW 4 major objections 2 minor 1 cited by

When Are Standard Graph Products Isomorphic?

T0 review · 4 major / 2 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read 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

desk verdict A plausible classification claim that I cannot verify because the supplied text is corrupted; worth sending to a referee with a readable copy. read the letter →

arxiv 2508.04137 v1 pith:LMY5SWN5 submitted 2025-08-06 math.CO

Priti Prasanna Mondal , M. Rajesh Kannan , Fouzul Atik This is my paper · ORCID
classification math.CO MSC 05C6005C7605C5005C12
keywords graphproductsCartesianproductKroneckerstronglexicographicisomorphismdistance-regulargraphsdistanceeigenvalues
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 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].

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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.

Referee Report

4 major / 2 minor

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.

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 (4)
  1. [Full text (Sections 1–5)] 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.
  2. [Abstract / theorem statement] 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.
  3. [Spectral by-product] 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.
  4. [Embedded header (p. 1–2)] 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.
minor comments (2)
  1. [References] The abstract cites [2] but no readable bibliography is available. A full reference list must be included in a clean version.
  2. [Tables/examples] Several fragments appear to be tables or example arrays, but they are not decipherable in mojibake. Ensure these render correctly in the resubmitted version.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation identifiable in the supplied text; proof body is unreadable, but circularity requires exhibited reduction and none is present.

full rationale

The abstract presents a complete characterization and a spectral by-product as theorem and consequence, with no indication that conclusions are fed back as assumptions. The full text is mostly mojibake, and the embedded header 'arXiv:2508.04120v1 [cs.CV]' is unrelated to the stated math.CO topic, so no equation or lemma can be parsed to exhibit a specific reduction of the kind required by the circularity rules. There is no readable fitted parameter later renamed as a prediction, no load-bearing self-citation, and no imported uniqueness theorem. The unreadable proof body is a verifiability and correctness-risk concern, not circularity: per the rules, circularity may only be flagged when the paper can be quoted to exhibit the exact reduction (e.g., Eq. X = Eq. Y by construction). Since none can be exhibited from this copy, the honest finding is no significant circularity.

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

Abstract-only review. No free parameters or invented entities are reported in the abstract; the listed axioms are the background facts the stated claims presuppose. The principal unverifiable input is the proof body, which the corrupted supplied text does not expose.

assumptions (3)
  • domain assumption Standard definitions of the four graph products: Cartesian, Kronecker (direct), strong, lexicographic.
    The whole classification is stated over these four products, presupposing the standard product constructions and their elementary properties (see abstract).
  • standard math Standard spectral graph theory background: distance eigenvalues, distance-regular graphs, and the role of the bound d+1 on distinct distance eigenvalues, where d is the diameter.
    The by-product claims a family of non-distance-regular graphs with fewer than d+1 distinct distance eigenvalues, which presupposes these definitions and known results; inferred from the abstract because the body is unreadable.
  • domain assumption Prior results cited as [2], specifically Problem 4.3, and their correct integration into the paper's argument.
    The abstract explicitly frames the by-product as addressing Problem 4.3 of [2]; whether the cited problem is stated correctly and whether the authors of [2] overlap with the current authors could not be checked because the reference list is unreadable.

how reviews work

0 comments
Cite this review

Pith. "Pith review of When Are Standard Graph Products Isomorphic?." pith.science (2026). https://pith.science/paper/LMY5SWN5

@misc{pith2026250804137,
  author       = {Pith},
  title        = {Pith review of: When Are Standard Graph Products Isomorphic?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LMY5SWN5}},
  note         = {Machine review of arXiv:2508.04137}
}
read the original abstract

This article investigates the isomorphism problem for graphs derived from the four standard graph products: Cartesian, Kronecker (direct), strong, and lexicographic product. We provide a complete characterization of all simple connected graphs for which their corresponding products are isomorphic. As a by-product, we identify a novel family of non-distance-regular graphs that possess fewer than d+1 distinct distance eigenvalues, where d represents the diameter of the graph. This result offers a new perspective on Problem 4.3 posed in [2], moving beyond the current approaches.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Taxonomy of integrable and ground-state solvable models: Jastrow wave functions on graphs and parent Hamiltonians

    quant-ph 2026-02 conditional novelty 6.0 of 10

    A graph-based generalization of the Jastrow ansatz yields parent Hamiltonians with two-body edge interactions and three-body 2-path interactions, specifying exact ground states and energies for many new many-body models.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · cited by 1 Pith paper

  1. [2]

    Fouzul Atik and Pratima Panigrahi, On the distance spectrum of distance regular graphs, Linear Algebra and its Applications 478 (2015), 256--273

    work page 2015

  2. [1]

    Ghodratollah Aalipour, Aida Abiad, Zhanar Berikkyzy, Jay Cummings, Jessica De Silva, Wei Gao, Kristin Heysse, Leslie Hogben, Franklin HJ Kenter, Jephian C-H Lin, et al., On the distance spectra of graphs, Linear Algebra and its Applications 497 (2016), 66--87

    work page 2016

  3. [3]

    Panigrahi, Families of graphs having few distinct distance eigenvalues with arbitrary diameter, Electron

    Fouzul Atik and Pratima. Panigrahi, Families of graphs having few distinct distance eigenvalues with arbitrary diameter, Electron. J. Linear Algebra 29 (2016), 194--205

    work page 2016

  4. [4]

    27, Springer, 2010

    Ravindra B Bapat, Graphs and matrices, vol. 27, Springer, 2010

    work page 2010

  5. [5]

    Norman Biggs, Algebraic graph theory, Cambridge Tracts in Mathematics, vol. No. 67, Cambridge University Press, London, 1974. 347649

    work page 1974

  6. [6]

    A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. 1002568

    work page 1989

  7. [7]

    Richard Hammack, Wilfried Imrich, and Sandi Klav zar, Handbook of product graphs, second ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011, With a foreword by Peter Winkler. 2817074

    work page 2011

  8. [8]

    Frank Harary, On the group of the composition of two graphs, Duke Math. J. 26 (1959), 29--34. 110648

    work page 1959

Show all 38 references
  1. [9]

    2, 121--127

    Fu-Tao Hu and Jun-Ming Xu, On the diameter of the kronecker product graph, Mathematical Science Letters 2 (2013), no. 2, 121--127

    2013

  2. [10]

    Wilfried Imrich and Sandi Klavzar, Product graphs: Structure and recognition, Wiley, 2000

    2000

  3. [11]

    Wilfried Imrich, Sandi Klavzar, and Douglas F Rall, Topics in graph theory: Graphs and their cartesian product, CRC Press, 2008

    2008

  4. [12]

    Gopalapillai Indulal, Distance spectrum of graph compositions., Ars Math. Contemp. 2 (2009), no. 1, 93--100

    2009

  5. [13]

    439 (2013), no

    Huiqiu Lin, Yuan Hong, Jianfeng Wang, and Jinlong Shu, On the distance spectrum of graphs, Linear Algebra Appl. 439 (2013), no. 6, 1662--1669. 3073894

    2013

  6. [14]

    Gert Sabidussi, Graph multiplication, Math. Z. 72 (1959/60), 446--457. 209177

    1959

  7. [15]

    van Dam, Jack H

    Edwin R. van Dam, Jack H. Koolen, and Hajime Tanaka, Distance-regular graphs, Electron. J. Combin. DS22 (2016), 156. 4336224

    2016

  8. [16]

    1, 47--52

    Paul M Weichsel, The kronecker product of graphs, Proceedings of the American Mathematical Society 13 (1962), no. 1, 47--52

    1962

  9. [17]

    De., Gao, W., Heysse, K., Hogben, L., Kenter, F

    Aalipour, G., Abiad, A., Berikkyzy, Z., Cummings, J., Silva, J. De., Gao, W., Heysse, K., Hogben, L., Kenter, F. H., Lin, J. C. H., Tait, M.: On the distance spectra of graphs. Linear Algebra and its Applications, 497 , 66-87 (2016). DOI: 10.1016/j.laa.2016.02.018

    2016 doi

  10. [18]

    Atik, F., Panigrahi, P.: On the distance spectrum of distance regular graphs, Linear Algebra and its Applications, 478 , 256-273 (2015)

    2015

  11. [19]

    Atik, F., Panigrahi, P.: Families of graphs having few distinct distance eigenvalues with arbitrary diameter, Electronic Journal of Linear Algebra 29 , 194–205 (2016)

    2016

  12. [20]

    P., Parveen, F.: On the distance spectra of m -generation n -prism graph, AKCE International Journal of Graphs and Combinatorics 19 (3), 276-281 (2022)

    Atik, F., Mondal, P. P., Parveen, F.: On the distance spectra of m -generation n -prism graph, AKCE International Journal of Graphs and Combinatorics 19 (3), 276-281 (2022)

    2022

  13. [21]

    T., Ciubotariu, D., Medeleanu, M.: Topological indices and real number vertex invariants based on graph eigenvalues or eigenvectors, J

    Balaban, A. T., Ciubotariu, D., Medeleanu, M.: Topological indices and real number vertex invariants based on graph eigenvalues or eigenvectors, J. Chem. Inf. Sci., 31 , 517-523 (1991)

    1991

  14. [22]

    Barik, S., Sahoo, G.: On the distance spectra of coronas, Linear and Multilinear Algebra, 65 (8), 1617-1628 (2017)

    2017

  15. [23]

    E., Cohen, A

    Brouwer, A. E., Cohen, A. M., Neumaier, A.: Distance-regular graphs, Springer-Verlag, Berlin, 1989

    1989

  16. [24]

    Deza, M., Laurent, M.: Geometry of Cuts and Metrics, Springer, Berlin (1997)

    1997

  17. [25]

    R., Graham, R

    Edelberg, M., Garey, M. R., Graham, R. L.: On the distance matrix of trees, Discrete Math., 14 , 23-39 (1976)

    1976

  18. [26]

    J., Gregory, D

    Elzinga, R. J., Gregory, D. A., Vander Meulen, K. N.: Addressing the Petersen graph, Discrete Math., 286 , 241-244 (2004)

    2004

  19. [27]

    L.: New bounds on the complexity of the shortest path problem, SIAM J

    Fredman, M. L.: New bounds on the complexity of the shortest path problem, SIAM J. Comput., 5 , 83-89 (1976)

    1976

  20. [28]

    Tee.: Eigenvectors of block circulant and alternating circulant matrices, New Zealand Journal of Mathematics, 8 123-142 (2005)

    Garry J. Tee.: Eigenvectors of block circulant and alternating circulant matrices, New Zealand Journal of Mathematics, 8 123-142 (2005)

    2005

  21. [29]

    L., Pollak, H

    Graham, R. L., Pollak, H. O.: On the addressing problem for loop switching, Bell System Tech. J. 50 , 2495-2519 (1971)

    1971

  22. [30]

    Graovac, A., Jashari, G., Strunje, M.: On the distance spectrum of a cycle, Aplikace matematiky 30 , 286-290 (1985)

    1985

  23. [31]

    T., Xu, J

    Hu, F. T., Xu, J. M.: On the diameter of the Kronecker product graph, Math. Sci. Lett. 2 (2), 121-127 (2013)

    2013

  24. [32]

    F.: Topics in Graph Theory: Graphs and their Cartesian Products, Wellesley, MA: A.K

    Imrich, W., Klavzar, S., Rall, D. F.: Topics in Graph Theory: Graphs and their Cartesian Products, Wellesley, MA: A.K. Peters Ltd., 2008

    2008

  25. [33]

    Commun., 13 , 123-131 (2008)

    Indulal, G., Gutman, I.: On the distance spectra of some graphs, Math. Commun., 13 , 123-131 (2008)

    2008

  26. [34]

    Contemp., 2 , 93-100 (2009)

    Indulal, G.: The distance spectrum of graph compositions, Ars Math. Contemp., 2 , 93-100 (2009)

    2009

  27. [35]

    Indulal, G., Balakrishnan, R.: Distance spectrum of Indu–Bala product of graphs, AKCE International Journal of Graphs and Combinatorics, 13 , 230-234 (2016)

    2016

  28. [36]

    N., Powers, D

    Ruzieh, S. N., Powers, D. L.: The distance spectrum of the path P_ n and the first distance eigenvector of connected graphs. Linear and Multilinear Algebra. 28 , 75-81 (1990)

    1990

  29. [37]

    M.: The Kronecker product of graphs, Proceedings of the American Mathematical Society, 13 , 47-52 (1962)

    Weichesel, P. M.: The Kronecker product of graphs, Proceedings of the American Mathematical Society, 13 , 47-52 (1962)

    1962

  30. [38]

    Zhou, B., Trinajstic, N.: Mathematical properties of molecular descriptors based on distances, Croat. Chem. Acta, 83 , 227-242 (2010)

    2010

Pith tools

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