Pith. sign in

REVIEW 3 major objections 5 minor 23 references

Exploring Graphs with Distinct $M$-Eigenvalues: Product Operation, Wronskian Vertices, and Controllability

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read This paper proves that rooted products preserve distinct M-eigenvalues exactly when the base graph is M-separable and the root is an M-Wronskian vertex, and it derives a controllability criterion plus infinite cospectral-pair…

desk verdict The general separability criterion for the new product is false as stated because it omits a needed hypothesis on G, but the rooted-product and controllability results are solid enough to warrant a serious referee. read the letter →

arxiv 2412.18759 v1 pith:UENBTMJ6 submitted 2024-12-25 math.CO

Haiying Shan , Xiaoqi Liu This is my paper · ORCID
classification math.CO MSC 05C5005C76
keywords ProductofgraphsDistinctM-eigenvaluesM-cospectralgraphM-controllableWronskianvertexRootedSeparablepolynomialspectra
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 answers a structural question: when does gluing copies of a rooted graph H onto the vertices of G preserve the property that the whole graph has distinct eigenvalues for the adjacency, Laplacian, normalized Laplacian, $A_{\alpha}$, or universal matrix. For the rooted product $G \circ H$, the answer is one neat condition: $G \circ H$ is $M$-separable if and only if $G$ is $M$-separable and the chosen root vertex of $H$ is an $M$-Wronskian vertex, meaning the characteristic polynomial of $M(H)$ is coprime to that of the vertex-deleted matrix. The paper proves that this coprimality is equivalent to strict interlacing of the two spectra, so the condition is checkable. This machinery yields a characterization of $M$-controllability for rooted products and a recursive scheme that produces infinite pairs of non-isomorphic $M$-cospectral graphs inside the class of graphs with distinct eigenvalues. The payoff is a transfer principle: spectral-separation, cospectrality, and controllability properties of large graphs can be read off from small factors.

What carries the argument

The engine is the Kronecker-product decomposition $A(G \circ_C H)=C\otimes A(G)+A(H)\otimes I_n$. For the rooted-product case $C=E_{u,u}$, this gives $\operatorname{Spec}_M(G\circ H)=\bigcup_{\mu\in\operatorname{Spec}_M(G)}\{\text{roots of }\varphi(M(H),x)-\mu\varphi(M_u(H),x)\}$. The named object carrying the argument is the $M$-Wronskian vertex of $H$, defined by the nonvanishing of the Wronskian of $\varphi(M(H),x)$ and $\varphi(M_u(H),x)$; it guarantees that each member polynomial in the union is square-free and that no two distinct members share a root. The proof that this is equivalent to $\gcd(\varphi(M(H),x),\varphi(M_u(H),x))=1$ uses Cauchy interlacing plus a lemma on positive partial-fraction expansions of interlacing polynomials, and that equivalence is what turns the separability question into a simple gcd computation.

What would settle it

Take a small weighted graph $H$, such as a 3-vertex weighted path, and compute both $\varphi(M(H),x)$ and $\varphi(M_u(H),x)$; if $\gcd(\varphi(M(H),x),\varphi(M_u(H),x))=1$ but the Wronskian $\varphi(M(H),x)\varphi'(M_u(H),x)-\varphi'(M(H),x)\varphi(M_u(H),x)$ has a real root for some choice of weights, then Theorem 3.4 and the main separability criterion Theorem 3.6 are refuted.

Watch

Extended reading notes

Core claim

The central result is Theorem 3.6: for weighted graphs $G$ and $H$ with root vertex $u$ of $H$, the rooted product $G \circ H$ is $M$-separable if and only if $G$ is $M$-separable and $u$ is an $M$-Wronskian vertex of $H$. An $M$-Wronskian vertex is one for which the Wronskian $$\varphi(M(H),x)\varphi'(M_u(H),x)-\varphi'(M(H),x)\varphi(M_u(H),x)$$ never vanishes; Theorem 3.4 identifies this exactly with $\gcd(\varphi(M(H),x),\varphi(M_u(H),x))=1$, i.e. with the root-deleted spectrum strictly interlacing the full spectrum. The paper also proves a matching controllability statement, Theorem 6.1: $G \circ H$ is $M$-controllable exactly when $G$ is $M$-controllable, the same gcd condition holds, and every matrix $B(\mu)=M(H)+\mu E_{u,u}$ with $\mu$ in the $M$-spectrum of $G$ is controllable. Alongside these, the paper shows that appending a pendant path to a graph preserves the $M$-Wronskian property of the terminal vertex, and uses that to build infinite families of non-isomorphic $M$-cospectral graphs inside the class of $M$-separable graphs.

Load-bearing premise

The main criterion assumes a technical converse: whenever the two spectra interlace strictly, the deleted characteristic polynomial can be written as a positive combination of the full polynomial's simple quotients; the paper cites a lemma that goes in the opposite direction, and if that unstated converse is false the criterion collapses.

Editorial extensions

If this is right

  • The rooted-product criterion unifies earlier path-based results: any $M$-separable graph $G$ combined with any rooted $H$ whose root is $M$-Wronskian stays $M$-separable, covering the adjacency, Laplacian, normalized Laplacian, $A_{\alpha}$, and universal spectra in one statement.
  • Because appending pendant paths preserves $M$-Wronskian vertices, there are infinitely many rooted graphs $H$ with this property, so the class of connected graphs with distinct $M$-eigenvalues is closed under many rooted products rather than only path-rooted ones.
  • If $G_1$ and $G_2$ are $M$-cospectral and $H^m_v$ has $u_m$ as an $M$-Wronskian vertex, then $G_1\circ H^m_v$ and $G_2\circ H^m_v$ are non-isomorphic, $M$-cospectral, and $M$-separable, giving a recursive source of infinite such pairs.
  • $M$-controllability of $G\circ H$ is decidable from the $M$-spectrum of $G$ and the controllability of the finitely many matrices $B(\mu)=M(H)+\mu E_{u,u}$; in particular, both factors must be controllable when the base graph has a zero eigenvalue.
  • If $G\circ H$ is determined by its $M$-spectrum, then so is $G$; with the coprimality condition, $M$-cospectrality of the products forces $M$-cospectrality of the bases, so the product construction cannot create spurious cospectral identifications.

Reading between the lines

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

  • The gcd criterion suggests a practical filter: since $M$-Wronskian vertices are detectable by polynomial gcd rather than full eigenvalue computation, one can enumerate rooted graphs up to moderate order and immediately generate large $M$-separable products with any separable base.
  • The same spectral-union decomposition is stated for arbitrary $C$, so searching for matrices $C$ for which the $B(\mu)$ families have pairwise disjoint root sets could produce broader families of separable product graphs beyond the rooted-product case.
  • The numerical census in the paper shows that every $A$-controllable graph up to order nine has an $A$-Wronskian vertex; if this pattern persists, controllability and Wronskian-vertex existence may be equivalent for all $A$-controllable graphs, a question the paper leaves open.
  • Because eigenvectors of the product decompose as tensor products, main-character splits multiplicatively between $G$ and each $B(\mu)$, which gives a route to controllability criteria for Cartesian and other $C$-products without forming large walk matrices.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces a graph product G ∘_C H with adjacency matrix C ⊗ A(G) + A(H) ⊗ I_n, studies its M-spectrum and eigenvectors, and aims to characterize when the product has distinct M-eigenvalues. For the rooted-product case C = E_{11}, it introduces the notion of an M-Wronskian vertex, proves that a vertex is M-Wronskian exactly when the characteristic polynomials of M(H) and its principal submatrix are coprime, and uses this to give an iff condition for rooted products to be M-separable. It then applies these tools to construct infinite families of non-isomorphic M-cospectral graphs and gives a necessary and sufficient condition for rooted products to be M-controllable.

Significance. If the technical gaps are repaired, the paper is a useful contribution: Lemma 2.1 provides a convenient spectral decomposition for the new product, Theorem 3.6 gives a clean separability criterion for rooted products, and the Wronskian-vertex machinery yields a systematic construction of cospectral pairs in the class of graphs with distinct eigenvalues. The paper also contains explicit examples and a numerical census of small graphs. However, the advertised general separability criterion (Theorems 3.1 and 3.2) is false as stated, the proof of the key Wronskian-gcd equivalence (Theorem 3.4) uses an unproved converse of the cited interlacing lemma, and the controllability proof (Theorem 6.1) omits a necessary simplicity argument. These are fixable within the manuscript's scope, but the current wording cannot be accepted as is.

major comments (3)
  1. [Section 3, Theorems 3.1 and 3.2]
  2. [Section 3, proof of Theorem 3.4]
  3. [Section 6, proof of Theorem 6.1]
minor comments (5)
  1. [Section 2, Lemma 2.1 proof]
  2. [Section 2, Lemma 2.1 and Theorem 2.1]
  3. [Section 3, Lemma 3.2]
  4. [Section 6, Table 1]
  5. [Section 4, Example 5]

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the M-spectrum, separability, and controllability results follow from Kronecker-sum spectral identities and external interlacing lemmas, with no fitted input relabeled as a prediction.

full rationale

The paper's central chain is non-circular. The M-spectrum formula Spec_M(G∘_C H)=∪_{μ∈Spec_M(G)} S(μ) is obtained in Lemma 2.1/Theorem 2.2 by applying the Kronecker-sum eigenvector identity D(η⊗ξ)=λη⊗ξ directly to the definition M(G∘_C H)=C⊗M(G)+M(H)⊗I_n; no parameter is fitted and no target conclusion is assumed. The separability criteria then follow by analyzing multiple roots of the polynomials φ(M(H),x)−μφ(M_u(H),x). Lemma 3.1 proves the gcd condition is equivalent to disjointness of the S(μ) sets, and Lemma 3.2 derives the separability criterion from the spectrum formula. Theorem 3.4 shows that the newly defined M-Wronskian condition (a Wronskian with no real zeros) is equivalent to gcd=1, using Cauchy interlacing and an external lemma from Fisk; the equivalence is nontrivial and not a definitional identity. Theorem 3.6 combines these equivalences, and Theorem 6.1 similarly derives controllability of the rooted product from the main-eigenvector decomposition η_ij⊗ξ_j; the condition that each B(μ) is controllable is an independent spectral condition on H, not a restatement of the conclusion. There are no fitting steps and no author self-citations used as evidence; prior work by Lou, Tian, and Godsil/McKay is background or external support. Two caveats are correctness issues rather than circularity: Theorems 3.1–3.2 omit the hypothesis that G is M-separable, and the K_{2,2}∘_{E11}P2 example shows they are false as stated; and Theorem 3.4 applies Lemma 3.3 in a converse direction that the quoted statement does not explicitly contain. Neither defect makes a claimed result true by construction, so the circularity score remains 0.

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

The paper introduces the M-Wronskian vertex as a named concept, but it is a definition equivalent to the gcd condition, not an unexplained entity. All results rest on standard matrix interlacing, the spectral theorem, and one lemma from an arXiv preprint. There are no fitted constants or ad hoc numerical parameters.

assumptions (4)
  • standard math Cauchy's Interlacing Theorem: eigenvalues of a principal submatrix interlace with those of the full symmetric matrix.
    Used in the proof of Theorem 3.4 to obtain strict interlacing λ1<μ1<λ2<... when gcd=1, which implies H is M-separable.
  • standard math Fisk's Lemma (Lemma 3.3, arXiv math/0612833): if roots of g interlace with roots of f, then g can be expanded with positive partial fractions.
    Used in Theorem 3.4 to show the derivative of φ(M_u)/φ(M_H) is negative, proving the Wronskian never vanishes.
  • standard math Spectral theorem for real symmetric matrices: an orthonormal eigenbasis exists.
    Used in Lemma 2.1 and throughout to decompose spectra and eigenvectors.
  • domain assumption The new product G∘C H is defined by adjacency matrix C⊗A(G)+A(H)⊗I_n; for M∈{L,Q,A_α,U} the M-matrix formula holds only for diagonal C.
    This restricts the scope of Theorems 2.2 and 3.2; the rooted product uses C=E11, which is diagonal, so the main results apply.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exploring Graphs with Distinct $M$-Eigenvalues: Product Operation, Wronskian Vertices, and Controllability." pith.science (2026). https://pith.science/paper/UENBTMJ6

@misc{pith2026241218759,
  author       = {Pith},
  title        = {Pith review of: Exploring Graphs with Distinct $M$-Eigenvalues: Product Operation, Wronskian Vertices, and Controllability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UENBTMJ6}},
  note         = {Machine review of arXiv:2412.18759}
}
abstract

Let $\mathcal{G}^M$ denote the set of connected graphs with distinct $M$-eigenvalues. This paper explores the $M$-spectrum and eigenvectors of a new product $G\circ_C H$ of graphs $G$ and $H$. We present the necessary and sufficient condition for $G\circ_C H$ to have distinct $M$-eigenvalues. Specifically, for the rooted product $G\circ H$, we present a more concise and precise condition. A key concept, the $M$-Wronskian vertex, which plays a crucial role in determining graph properties related to separability and construction of specific graph families, is investigated. We propose a novel method for constructing infinite pairs of non-isomorphic $M$-cospectral graphs in $\mathcal{G}^M$ by leveraging the structural properties of the $M$-Wronskian vertex. Moreover, the necessary and sufficient condition for $G\circ H$ to be $M$-controllable is given.

Figures

Figures reproduced from arXiv: 2412.18759 by the authors.

Figure 1
Figure 1. Graph P3 ◦C P3 with C =   1 0 0 0 0 1 0 1 1  . The adjacency matrix of G ◦C H is given by the formula A(G ◦C H) = C ⊗ A(G) + A(H) ⊗ In. (1) Let C1 be the diagonal matrix such that the i-th diagonal element of C1 is equal to the i-th row sum of C. Then we get D(G ◦C H) = C1 ⊗ D(G) + D(H) ⊗ In. When C is not a diagonal matrix, we get C 6= C1. For the universal adjacency matrix U = aA + dD, we have U(G ◦C H) = a(C … view at source ↗
Figure 2
Figure 2. Graph Gn v . An eigenvalue is considered main if its corresponding eigenspace contains a vector that is not orthogonal to the all-ones vector. We say a matrix M is controllable if all the eigenvalues of M are main, and a M-controllable graph is a connected graph whose M-matrix has distinct and main eigenvalues. It is well known in control theory (see [2]) that M is controllable if and only if the controllability mat… view at source ↗
Figure 3
Figure 3. Some graphs with A-Wronskian vertex Example 1. We can verify that each vertex of Hi is the A-Wronskian vertex of Hi for i = 1, 2, 3, 4. Let G be an A-separable graph. By Corollary 3.1, we have that G ◦ Hi, with a vertex of Hi arbitrarily selected as the root vertex, is also A-separable for i = 1, 2, 3, 4. Next, we aim to characterize the M-Wronskian vertex of H using Cauchy’s Interlacing Theorem and a lemma from Fis… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Two graphs with M-Wronskian vertex 5 DMS-property of G ◦ H In this section, we investigate the DMS-property of a rooted product graph and construct infinite pairs of non-isomorphic M-cospectral graphs in GM based on the results obtained in Sections 3 and 4. By Corollar…
Figure 5
Figure 5. Figure 5: A pair of Q-cospectral Q-separable graphs Next, we present two results related to the DMS problem. Theorem 5.2. If G ◦ H is DMS, then G is DMS. Proof. Let G1 be any graph such that SpecM (G1) = SpecM (G). By Lemma 5.1, we obtain SpecM (G ◦ H) = SpecM (G1 ◦ H), then G ◦…
Figure 6
Figure 6. Figure 6: Two A-controllable graphs Recall that the notation G A represents the set of connected graphs with distinct A-eigenvalues. In what follows, we define G to be the set of connected graphs, G A ∗ to be the set of connected A-controllable graphs, G A W as the set of connec…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

  1. [1]

    A note on the eigenvalues of a graph

    Chong-Yun Chao. A note on the eigenvalues of a graph. Journal of Combinatorial Theory, Series B , 10(3):301–302, 1971

    work page 1971

  2. [2]

    Linear System Theory and Design: International Fourth Edit ion

    Chi-Tsong Chen. Linear System Theory and Design: International Fourth Edit ion. Oxford University Press, Inc., 2013

    work page 2013

  3. [3]

    Cvetkovi´ c, P

    D. Cvetkovi´ c, P. Rowlinson, Z. Stani´ c, and M.-G. Yoon. Controllable graphs. Bull., Cl. Sci. Math. Nat., Sci. Math. , 143(36):81–88, 2011

    work page 2011

  4. [4]

    Controllable graphs with least eigenvalue at least −2

    Dragoˇ s Cvetkovi´ c, Peter Rowlinson, Zoran Stani´ c, and Myung-Gon Yoon. Controllable graphs with least eigenvalue at least −2. Appl. Anal. Discrete Math. , 5(2):165–175, 2011. 14

    work page 2011

  5. [5]

    Contr ollability of NEPSes of graphs

    Alexander Farrugia, Tamara Koledin, and Zoran Stani´ c. Contr ollability of NEPSes of graphs. Linear Multilinear Algebra, 70(10):1928–1941, 2022

    work page 1928

  6. [6]

    C. D. Godsil. Algebraic Combinatorics. Chapman Hall/CRC Mathematics Series. CRC Press, 2017

    work page 2017

  7. [7]

    C. D. Godsil and B. D. McKay. A new graph product and its spectr um. Bull. Aust. Math. Soc. , 18:21–28, 1978

    work page 1978

  8. [8]

    Haemers and G.R

    W.H. Haemers and G.R. Omidi. Universal adjacency matrices with tw o eigenvalues. Linear Algebra and its Applications, 435(10):2520–2529, 2011. Special Issue in Honor of Dragos Cve tkovic

    work page 2011

Show all 23 references
  1. [9]

    Frank Harary and Allen J. Schwenk. Which graphs have integral s pectra? In Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington , D.C., 1973) , volume Vol. 406 of Lecture Notes in Math. , pages 45–51. Springer, Berlin-New York, 1974

    1973

  2. [10]

    Number of connected graphs on n vertices whose spectrum has n distinct eigenvalues

    Travis Hoppe and Anna Petrone. Number of connected graphs on n vertices whose spectrum has n distinct eigenvalues. Entry A242952 in The On-Line Encyclopedia of Integer Sequen ces, https://oeis.org/A242952

  3. [11]

    On the hermit ian matrix with distinct eigenvalues and its applications

    Xue Liang Li, Jian Feng Wang, and Qiong Xiang Huang. On the hermit ian matrix with distinct eigenvalues and its applications. Acta Mathematica Sinica(Chinese Series) , 2015

    2015

  4. [12]

    Construc tion of graphs with distinct eigenvalues

    Zhenzhen Lou, Qiongxiang Huang, and Xueyi Huang. Construc tion of graphs with distinct eigenvalues. Discrete Math., 340(4):607–616, 2017

    2017

  5. [13]

    On the con struction of Q-controllable graphs

    Zhenzhen Lou, Qiongxiang Huang, and Xueyi Huang. On the con struction of Q-controllable graphs. Electron. J. Linear Algebra , 32:365–379, 2017

    2017

  6. [14]

    Solving the Korteweg-de Vries eq uation by its bilinear form: Wronskian solutions

    Wen-Xiu Ma and Yuncheng You. Solving the Korteweg-de Vries eq uation by its bilinear form: Wronskian solutions. Trans. Amer. Math. Soc. , 357(5):1753–1778, 2005

    2005

  7. [15]

    The signless Laplacian sp ectrum of rooted product of graphs

    Maryam Maghsoudi and Abbas Heydari. The signless Laplacian sp ectrum of rooted product of graphs. Discrete Math. Algorithms Appl. , 10(6):10, 2018. Id/No 1850076

    2018

  8. [16]

    The group of a graph whose adjacency matr ix has all distinct eigenvalues

    Abbe Mowshowitz. The group of a graph whose adjacency matr ix has all distinct eigenvalues. Proof Techniques in Graph Theory, Academic Press, New York , pages 109–110, 1969

    1969

  9. [17]

    Rajkumar and R

    R. Rajkumar and R. Pavithra. Spectra of M-rooted product o f graphs. Linear Multilinear Algebra , 70(1):1–26, 2022

    2022

  10. [18]

    Allen J. Schwenk. Computing the characteristic polynomial of a g raph. pages 153–172, 1974

    1974

  11. [19]

    Polynomials, roots, and interlacing–version 2

    Fisk Steve. Polynomials, roots, and interlacing–version 2. arXiv preprint math/0612833 , 2008

    2008 arXiv

  12. [20]

    Construction of gra phs with distinct Aα -eigenvalues

    Gui-Xian Tian, Jun-Xing Wu, and Shu-Yu Cui. Construction of gra phs with distinct Aα -eigenvalues. Discrete Math., 347(2):12, 2024. Id/No 113761

    2024

  13. [21]

    V. G. Vizing. The cartesian product of graphs. Vyˇ cisl. Sistemy, (9):30–43, 1963

    1963

  14. [22]

    The controllability of graphs with diameter n-2

    Liang Wei, Faxu Li, Haixing Zhao, and Bo Deng. The controllability of graphs with diameter n-2. Appl. Math. Comput. , 407:13, 2021. Id/No 126327

    2021

  15. [23]

    Weisstein

    Eric W. Weisstein. Number of onnected controllable simple graphs on n vertices. Entry A371897 in The On-Line Encyclopedia of Integer Sequences , https://oeis.org/A371897. 15

Pith tools

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