{"id":"f5857810-90eb-49fb-8dae-0ce50808eab0","arxiv_id":"2412.18759","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A unified condition for rooted products of graphs to have distinct matrix eigenvalues, plus a construction of infinite families of non-isomorphic cospectral graphs and a controllability criterion.","lead":"This paper studies graphs whose associated matrices have all distinct eigenvalues, and how these properties survive a new graph product operation. It gives conditions for the product to keep distinct eigenvalues and controllability, and uses them to build infinitely many pairs of non-isomorphic graphs that share the same spectrum.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 3.1–3.2 omit the necessary hypothesis that G is M-separable; for G=K_{2,2}, H=P2, C=E_{1,1}, their conditions hold but G∘C H has repeated ±1 eigenvalues, so the paper's general separability criterion is false.","rationale":"The reader's stated weakest point, the use of Lemma 3.3 in Theorem 3.4, is a genuine presentation gap, but checking it shows the converse needed there is actually true: under strict interlacing with positive leading coefficients, the residues g(λ_i)/f'(λ_i) all have the same sign, so the partial fraction coefficients can be taken positive. Thus the rooted-product Theorem 3.6 is likely correct. The more serious problem is in Theorems 3.1–3.2, which are the general results advertised in the abstract. The K_{2,2}∘P2 counterexample is decisive: the graph is inseparable even though both stated conditions hold, because multiplicities from repeated M-eigenvalues of G are ignored. This is an internal mathematical falsehood, not a mere disagreement with prior literature. It does not refute Theorem 3.6, but it does mean the manuscript's central general claim is unsound as written. I would reject the current version, or require major revision, with the minimal fix being to add G∈GM to the hypotheses of Theorems 3.1 and 3.2 and to re-check all dependent statements.","tokens_in":16015,"tokens_out":25243,"duration_ms":227665,"concrete_test":"Compute the characteristic polynomial of the 8×8 matrix E_{1,1}⊗A(K_{2,2})+A(P2)⊗I_4, or use Lemma 2.1's spectral decomposition, and check that (x^2−1)^2 divides it, while verifying that the two conditions of Theorem 3.1 hold with S(0), S(2), S(−2) pairwise disjoint. If the divisibility holds, Theorem 3.1 is false; then re-prove Theorem 3.1 with the added hypothesis 'G is A-separable' and confirm the corrected statement.","verdict_should_be":"REJECT","load_bearing_attack":"Theorems 3.1 and 3.2 state an iff for G∘C H to be M-separable in terms of (1) B(μ) having distinct eigenvalues for each μ and (2) S(μ1)∩S(μ2)=∅ for distinct μ. These conditions do not include the requirement that G be M-separable. Since Spec_M(G) is a multiset (as defined in §1), a repeated M-eigenvalue μ of multiplicity k forces every element of S(μ) to occur with multiplicity k in Spec_M(G∘C H), regardless of conditions (1)–(2). Concretely, take M=A, G=K_{2,2} with spectrum {2,0,0,−2}, H=P2, and C=E_{1,1} (the rooted-product case). Then μ=0 has multiplicity two; A(P2)+0E_{1,1}=A(P2) has distinct eigenvalues ±1, and the sets S(0)={±1}, S(2)={1±√2}, S(−2)={−1±√2} are pairwise disjoint. Thus both conditions of Theorem 3.1 hold, yet ±1 are repeated eigenvalues of G∘C H, so it is not A-separable. Hence the paper's advertised general separability criterion is false as stated. The rooted-product Theorem 3.6 is not refuted by this example because it explicitly assumes G is M-separable; the general theorems need exactly that missing hypothesis, or an explicit treatment of eigenvalue multiplicities.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16280,"tokens_out":12327,"duration_ms":108452,"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":[{"comment":"","section":"Section 3, Theorems 3.1 and 3.2"},{"comment":"","section":"Section 3, proof of Theorem 3.4"},{"comment":"","section":"Section 6, proof of Theorem 6.1"}],"minor_comments":[{"comment":"","section":"Section 2, Lemma 2.1 proof"},{"comment":"","section":"Section 2, Lemma 2.1 and Theorem 2.1"},{"comment":"","section":"Section 3, Lemma 3.2"},{"comment":"","section":"Section 6, Table 1"},{"comment":"","section":"Section 4, Example 5"}],"recommendation":"major_revision","confidential_remarks":"The counterexample to Theorems 3.1–3.2 is decisive and should be fixed before publication, but the fix is local (add the hypothesis that G is M-separable). The proof of Theorem 3.4 also needs a proper citation or proof of the converse of Lemma 3.3, and the controllability proof needs a few clarifying sentences. I do not see evidence of circularity or unstated parameter fitting. The paper fits the journal's scope and, after these repairs, should be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the general separability criterion advertised in Theorems 3.1 and 3.2 is false as stated. The missing hypothesis is that G be M-separable. Counterexample: take G=K_{2,2} with A-spectrum {2,0,0,-2}, H=P2, and C=E_{1,1} (so the product is the rooted product). For μ=0, B(0)=A(P2) has distinct eigenvalues ±1, and the sets S(2), S(0), S(-2) are pairwise disjoint. Both conditions in Theorem 3.2 hold, yet because μ=0 has multiplicity two in G, the eigenvalues ±1 each appear twice in the product, so G∘C H is not A-separable. Adding 'G is M-separable' to the hypotheses fixes the statement; the rooted-product version (Theorem 3.6) already includes it and is not refuted.\n\nThat said, the paper has genuine contributions. It extends the earlier distinct-eigenvalue results of Lou–Huang–Huang and Tian et al. from A and A_α to all of {A,L,Q,A_α,U} and to weighted graphs. The rooted-product characterization is a clean iff: G∘H is M-separable iff G is M-separable and the root is an M-Wronskian vertex. The Wronskian vertex repackages the known gcd condition, but the packaging enables a new, genuinely useful construction of infinite families of non-isomorphic M-cospectral graphs in Section 5. The controllability theorem (Theorem 6.1) is new and, as far as I can tell, correct.\n\nSoft spots besides the counterexample: the proof of Theorem 3.4 invokes Lemma 3.3 in the wrong direction. The lemma states that positive coefficients in the partial fraction expansion imply interlacing; the proof needs the converse, which is true but not proved or cited. Lemma 2.1's proof has garbled notation (some tensor products written where inner products belong), and Theorem 6.1's eigenvector argument is compressed. The numerical examples in Sections 4–6 are not reproducible: no code or data files are provided.\n\nOverall, the paper deserves a serious referee. It has a fixable but real error in the general theorems, a few proof-presentation issues, and the main rooted-product results appear sound. I wouldn't cite the current version, but I'd cite a corrected one.","headline":"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.","tokens_in":16872,"tokens_out":8116,"would_cite":false,"duration_ms":65232,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C76"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["Product of graphs","Distinct M-eigenvalues","M-cospectral graph","M-controllable graph","Wronskian vertex","Rooted product","Separable polynomial","Graph spectra"],"falsifier":"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.","tokens_in":15765,"feed_emoji":"📐","tokens_out":8304,"duration_ms":75816,"temperature":0.7,"pith_summary":"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.","feed_headline":"A single gcd condition preserves distinct eigenvalues in rooted products","feed_subtitle":"M-Wronskian vertices also build infinite cospectral pairs and settle controllability of the product.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the rooted product $G\\circ H$ and its $A$-characteristic polynomial, providing the spectral foundation that Corollary 2.3 generalizes to arbitrary $M$.","marker":"[7]"},{"why":"Supplies Lemma 3.3 on interlacing and positive partial-fraction expansions, the critical step in proving that coprimality implies the Wronskian property.","marker":"[19]"},{"why":"Gives the earlier construction of graphs with distinct $A$-eigenvalues via rooted products with paths, which the present criterion generalizes.","marker":"[12]"},{"why":"Provides the analogous $Q$-separable and $Q$-controllable rooted-path constructions that the $M$-Wronskian criterion subsumes.","marker":"[13]"},{"why":"Extends the rooted-path construction to $A_{\\alpha}$-spectra; Theorem 3.6 of this paper generalizes that result to arbitrary rooted $H$.","marker":"[20]"},{"why":"Supplies the sum-of-squares identity used in Remark 1 to show that for adjacency spectra the Wronskian is non-positive.","marker":"[6]"},{"why":"States the controllability-matrix full-rank criterion used in Section 6 to define and verify $M$-controllability of the product.","marker":"[2]"}],"fun_headline_variants":["M-Wronskian vertex unlocks infinite cospectral graph pairs","Distinct M-eigenvalues: gcd criterion for rooted products","Rooted product separability: one Wronskian condition","New tool builds infinite cospectral M-separable graphs","Controllability and separability: a rooted product theorem"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["M-Wronskian vertex unlocks infinite cospectral graph pairs","Distinct M-eigenvalues: gcd criterion for rooted products","Rooted product separability: one Wronskian condition","New tool builds infinite cospectral M-separable graphs","Controllability and separability: a rooted product theorem"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001127,"raw_usage":{"total_tokens":4729,"prompt_tokens":1030,"completion_tokens":3699,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":646,"completion_tokens_details":{"reasoning_tokens":3616}},"tokens_in":646,"tokens_out":3699,"duration_ms":24900,"temperature":1.0,"reasoning_tokens":3616,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:30:17.911951+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the rooted product $G\\circ H$ and its $A$-characteristic polynomial, providing the spectral foundation that Corollary 2.3 generalizes to arbitrary $M$."},{"cited_title":"Construc tion of graphs with distinct eigenvalues","cited_arxiv_id":null,"evidence_quote":"Gives the earlier construction of graphs with distinct $A$-eigenvalues via rooted products with paths, which the present criterion generalizes."},{"cited_title":"On the con struction of Q-controllable graphs","cited_arxiv_id":null,"evidence_quote":"Provides the analogous $Q$-separable and $Q$-controllable rooted-path constructions that the $M$-Wronskian criterion subsumes."},{"cited_title":"Construction of gra phs with distinct Aα -eigenvalues","cited_arxiv_id":null,"evidence_quote":"Extends the rooted-path construction to $A_{\\alpha}$-spectra; Theorem 3.6 of this paper generalizes that result to arbitrary rooted $H$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sum-of-squares identity used in Remark 1 to show that for adjacency spectra the Wronskian is non-positive."},{"cited_title":"Linear System Theory and Design: International Fourth Edit ion","cited_arxiv_id":null,"evidence_quote":"States the controllability-matrix full-rank criterion used in Section 6 to define and verify $M$-controllability of the product."}],"review_version":1}