Two Distinct Eigenvalues from a New Graph Product

Eric Culver; Mark Kempton

REVIEW 1 major objections 5 minor 13 references

Two Distinct Eigenvalues from a New Graph Product

T0 review · 1 major / 5 minor · reviewed 2026-08-10 · 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 that a new modified strong product and a companion tensor-sum construction generate infinite families of graphs whose minimum number of distinct eigenvalues equals two.

desk verdict The new product and tensor method are legitimate, and Theorems 7–8 hold, but Theorem 11(a,b) overclaims because the A_i's isolated diagonal 1's introduce a third eigenvalue for l≥3. read the letter →

arxiv 2501.04297 v1 pith:UPCIKILV submitted 2025-01-08 math.CO

Eric Culver , Mark Kempton This is my paper · ORCID

classification math.CO MSC 05C5005C7615A18

keywords q(G)minimumnumberofdistincteigenvaluesmodifiedstrongproductgraphproductschromaticindexKroneckerlinearhypergraphscandlegraphs

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 studies $q(G)$, the minimum number of distinct eigenvalues that a symmetric matrix can have while respecting the zero-nonzero pattern of a graph $G$. It introduces a modified strong product $G\bowtie H$, whose adjacency matrix is $A_G\otimes (A_H+I)$, and a block tensor-sum construction $M=\sum_{i=1}^k (A_i\otimes J_i)$ whose eigenvalues are forced into a two-element set. The main theorems prove that $G\bowtie K_k$ has $q=2$ for every $k$-regular $1$-factorable graph $G$, that $G\boxtimes K_{k+1}$ has $q=2$ for every connected graph of maximum degree $k$, and that several families built from linear hypergraphs also reach $q=2$. If correct, this supplies infinite families of two-eigenvalue graphs and shows that the previously known candle families are special cases of one construction.

What carries the argument

The load-bearing objects are the modified strong product $G\bowtie H$ (the strong product without the vertical edges of $H$, so its adjacency matrix is $A_G\otimes(A_H+I)$), the tensor-sum matrix $M=\sum_i A_i\otimes J_i$, and the auxiliary orthogonal projections $J_i=QD_iQ^T$ built from a Householder orthogonal matrix $Q$. Lemma 5 carries the spectral argument: the mutually annihilating $J_i$ make the eigenvectors $v_{i,\ell}\otimes q_i$ diagonalize $M$ with the eigenvalues of the individual $A_i$. Lemma 6 carries the pattern argument: the support of $M$ is completely controlled by $A_1+\cdots+A_k$, producing full blocks where that sum has entries strictly between $0$ and $k$, identity blocks where it equals $k$, and zero blocks where it is $0$.

What would settle it

Take an $l$-uniform linear hypergraph with maximum degree $k$, chromatic index $c>k$, and at least one vertex that is incident to no hyperedge of some color $i$; for $l\ge 3$, the matrix $A_i$ in Theorem 11(a) then has eigenvalues $l-1$, $-1$, and $1$, so Lemma 5 forces $M$ to have three distinct eigenvalues. Computing this example directly would determine whether Theorem 11(a) holds as stated and would reveal the exact missing hypothesis.

Watch

Extended reading notes

Core claim

The central claim is that two-eigenvalue graphs can be manufactured by a tensor-sum sandwich: choose an orthogonal matrix $Q$, set $J_i=QD_iQ^T$ for the diagonal rank-one matrices $D_i$, and form $M=\sum_i A_i\otimes J_i$. Because $J_iJ_j=0$ for $i\ne j$, every vector $v\otimes q_i$ with $v$ an eigenvector of $A_i$ and $q_i$ a column of $Q$ is an eigenvector of $M$ with the same eigenvalue; hence $M$ has only two distinct eigenvalues whenever each $A_i$ does. Lemma 6 then recovers the graph pattern from the ordinary sum $A_1+\cdots+A_k$, so $M$ can be engineered to be a matrix in $S(G\bowtie K_k)$, $S(G\boxtimes K_{k+1})$, or the corresponding hypergraph product. The paper uses this to establish Theorems 7, 8, and 11.

Load-bearing premise

The construction depends on being able to choose the edge-color pieces so that every corresponding 0-1 matrix $A_i$ has only two eigenvalues, and in the hypergraph cases this is not guaranteed by the stated hypotheses: a vertex missed by a color contributes a diagonal $1$, which for $l\ge 3$ adds a third eigenvalue to $A_i$.

Editorial extensions

If this is right

Every $k$-regular graph whose edge set is the disjoint union of $k$ perfect matchings yields a graph $G\bowtie K_k$ with exactly two attainable eigenvalues; cycles, complete graphs of odd order, and many other regular graphs qualify.
Every connected graph of maximum degree $k$ can be embedded as a factor in $G\boxtimes K_{k+1}$ with $q=2$, so irregularity of the base graph is no obstruction once a $K_{k+1}$ factor is added.
Linear hypergraphs with chromatic index $c$ supply further infinite families, including $G\boxtimes K_c$ when $c>k$ and $G\boxtimes K_{c+1}$ when $c=k$.
The previously studied double-ended candles and closed candles are, respectively, $P_k\bowtie K_2$ and $C_k\bowtie K_2$, so their $q=2$ status follows from the new product rather than from case-by-case analysis.
The construction shows that $q=2$ is preserved under a kind of product operation in which the second factor contributes only a clique or complete graph structure, giving a systematic route to new examples.

Reading between the lines

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

A natural extension, not pursued in the paper, is to let the second factor $H$ be any graph whose adjacency matrix has exactly two distinct eigenvalues; the same tensor-sum template would then potentially produce $G\bowtie H$ and $G\boxtimes H$ families with $q=2$.
Because any $q=2$ graph can realize any prescribed pair of eigenvalues (a fact the paper cites), the edge-partition strategy could in principle work with arbitrary two-eigenvalue pieces rather than only matchings and cliques; what is missing is a pattern-control lemma for weighted pieces.
A reader wanting a testable version of the hypergraph claims could add the hypothesis that every vertex is incident to a hyperedge of every color; under that extra condition the construction appears to go through and yields further infinite families.
Since the product pattern is read off from an additive sum of 0-1 matrices, iterating the construction may give towers of two-eigenvalue graphs, but the paper leaves the iteration behavior open.

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.

Desk Editor's Note

read the letter

Punchline: the modified strong product and the tensor-sum method are real and give new families, but the proof of Theorem 11(a,b) has a load-bearing eigenvalue-count error for l≥3.

The construction is genuinely new: G⋈H with adjacency A_G⊗(A_H+I), and the trick of using a Householder Q to get rank-one projectors J_i works cleanly. Lemma 5 and Lemma 6 are correct, and they make Theorem 7 (1-factorable G) and Theorem 8 (max degree k) go through. I checked the spectra: in Theorem 8, each A_i is a matching plus diagonal 1's on missed vertices, which still has only {1,-1}. So that part is solid, aside from G=K_1 which trivially gives q=1. The remark that the double-ended and closed candles are P_k⋈K_2 and C_k⋈K_2 is a nice unification.

The soft spot is Theorem 11(a,b). There, A_i puts a 1 on the diagonal for every vertex not incident to a hyperedge of color i. In an l-uniform linear hypergraph, a color class is a disjoint union of K_l's plus those isolated vertices with diagonal 1. So the eigenvalues of A_i are {l-1, -1, 1}, not {l-1, -1} as claimed. For l=2, 1 = l-1, so the argument survives; for every l≥3 it gives M three distinct eigenvalues, so q(G⊠K_c)=2 and q(G⊠K_{c+1})=2 are not proven. Since in cases (a) and (b) every vertex is missed by some color, this is not a corner case. Part (c) is fine: k-regularity with c=k means no vertex is missed, so A_i really is a union of K_l's.

The defect is localized and repairable—restrict to l=2 or require each vertex incident to every color—but as written the abstract overclaims. The rest of the paper is still worth a serious referee: Theorems 7 and 8 are new infinite families, and the tensor-sum framework will likely be reused. I'd recommend sending it back for revision rather than rejecting.

Referee Report

1 major / 5 minor

Summary. The paper introduces a variant of the strong graph product, called the modified strong product, and a tensor-sum construction M = Σ(A_i ⊗ J_i) built from orthogonal matrices. Lemma 5 gives the eigenvalues of M in terms of the spectra of the A_i, and Lemma 6 shows that the pattern of M is controlled by the entrywise sum of the A_i. The authors use this framework to claim new infinite families of graphs with q(G)=2, including modified strong products of 1-factorable regular graphs with cliques, strong products of bounded-degree graphs with cliques, and graphs arising from linear hypergraphs. Theorems 7, 8, and 11 are presented as the main results, with Theorem 11 subdivided into three cases (a), (b), and (c).

Significance. The tensor-sum framework in Lemmas 3-6 is elegant and correct, and the paper provides explicit, self-contained matrix constructions. If valid, the results would unify several known families of two-eigenvalue graphs, such as double ended candles and closed candles, and add new infinite families from 1-factorable graphs and linear hypergraphs. The constructive nature of the proofs is a strength, as is the explicit use of Householder matrices to produce the idempotent, mutually orthogonal J_i. However, the proof of Theorem 11(a,b) contains a load-bearing spectral error: the matrices A_i there have eigenvalue 1 from vertices missed by a color, giving three distinct eigenvalues for l≥3. This means the advertised hypergraph families are not established as written, though the rest of the paper's framework and the k-regular case (c) remain sound.

major comments (1)

[Section 3, Theorem 11(a,b), proof] The proof defines A_i with diagonal entry 1 at every vertex not incident to a hyperedge of color i, and then states that the eigenvalues of M are −1 and l−1 from Lemma 5 and Lemma 9. This is incorrect for l≥3. A vertex missed by color i gives a 1×1 block [1] with eigenvalue 1. Since each color class is a disjoint union of K_l's (eigenvalues l−1 and −1) plus these isolated 1×1 blocks, the spectrum of A_i is {l−1, −1, 1}, not {l−1, −1}. In cases (a) and (b), every vertex is missed by at least one color (because c>k in (a), and an extra color is added in (b)), so the eigenvalue 1 genuinely appears. Lemma 5 then yields M with eigenvalues −1, l−1, and 1, which are three distinct values for every l≥3. Consequently the claims q(G⊠K_c)=2 and q(G⊠K_{c+1})=2 are not proved by this construction. The defect is load-bearing for the hypergraph families advertised in the abstract; a repair is needed, for example by restricting to l=2 or by modifying the diagonal entries so that missed vertices do not introduce a new eigenvalue while preserving the pattern argument.

minor comments (5)

[Section 3, Theorem 11 proof] In cases (a) and (b), the sum M is written as (A_1 ⊗ J_1) + ... + (A_k ⊗ J_k), but the number of colors is c in case (a) and c+1 in case (b), not the maximum degree k. This index error should be corrected for the pattern argument in Lemma 6 to apply with the correct number of matrices.
[Section 3, Theorem 8] The statement 'If connected G has max degree k, then q(G ⊠ K_{k+1}) = 2' fails for G = K_1, where k=0 and q(K_1 ⊠ K_1) = q(K_1) = 1. The theorem should assume k≥1, or the edgeless connected graph should be excluded or treated separately.
[Section 2, Lemma 3] In the even-k case, the sentence 'the proof will proceed precisely as in the odd case' is too terse: because the entries of u are not constant, the claim that no diagonal entry of (1 − u_K^T u_K) u_K u_K^T equals 1/4 needs a short verification. This is true, but the argument should be spelled out.
[Section 3, Theorem 8 proof] The text says 'the pattern of M is determined by A_1 + · · · + A_k = B', but there are k+1 matrices in the construction, so this should be A_1 + · · · + A_{k+1} = B.
[Section 3, Theorem 8 proof] The phrase 'every vertex of G fails to be incident to some color' is awkward; it should read 'every vertex of G is not incident to some color'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the constructions are explicit and self-contained.

full rationale

The paper's central results are obtained by writing down explicit matrices from the graph factors and edge colorings: the adjacency matrices A_i of the colored subgraphs, the diagonal matrices D_i, and an explicitly constructed orthogonal matrix Q from a Householder reflection. Lemma 5 is a direct eigenvector computation showing that the eigenvalues of M = Σ(A_i ⊗ J_i) are precisely the eigenvalues of the A_i, and Lemma 6 determines the zero-nonzero pattern of M from the sum A_1 + ... + A_k. No parameter is fitted to any target graph, no claimed two-eigenvalue conclusion is assumed as an input, and the constructions do not rely on the known candle families to prove the main theorems. The cited works are used for context or for standard external facts (Vizing's theorem, the spectrum of complete graphs), not as load-bearing premises that replace the derivation. The known families are presented as observations that they arise from the new product, not as assumptions on which the proofs depend. The proof of Theorem 11(a,b) has a genuine mathematical defect: a vertex missed by a color class gives a 1x1 all-ones block in A_i, so A_i has eigenvalues -1, l-1, and 1 when l >= 3, meaning Lemma 5 yields three distinct eigenvalues for M. That is a correctness gap, not circularity, because the erroneous claim does not make the theorem's conclusion identical to an input of the construction. Therefore the circularity score is 0.

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

The central proofs use standard results (Vizing's theorem, clique spectra) and one construction-specific but false premise about the spectrum of the color matrices A_i in Theorem 11(a,b). There are no fitted numerical parameters; the orthogonal matrix Q is defined explicitly. The modified strong product is a new definition, not a postulated entity with independent evidence.

assumptions (3)

standard math Vizing's theorem: every simple graph with maximum degree k has a proper edge coloring with k+1 colors.
Used in Theorem 8 to obtain the (k+1)-edge-coloring of G.
standard math The adjacency matrix of K_n has eigenvalues n-1 (once) and -1 (n-1 times).
Invoked as Lemma 9 and used for the eigenvalue computations in Theorem 11.
ad hoc to paper In Theorem 11(a,b), each matrix A_i has eigenvalues only in {l-1, -1}, because vertices missed by color i's hyperedges are represented by diagonal entries and do not add a separate eigenvalue.
This is asserted in the proof of Theorem 11 and is false for l>=3: a missed vertex is an isolated 1x1 block with eigenvalue 1. It is the load-bearing gap in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Two Distinct Eigenvalues from a New Graph Product." pith.science (2026). https://pith.science/paper/UPCIKILV

@misc{pith2026250104297,
  author       = {Pith},
  title        = {Pith review of: Two Distinct Eigenvalues from a New Graph Product},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UPCIKILV}},
  note         = {Machine review of arXiv:2501.04297}
}

abstract

The parameter $q(G)$ of a graph $G$ is the minimum number of distinct eigenvalues of a symmetric matrix whose pattern is given by $G$. We introduce a novel graph product by which we construct new infinite families of graphs that achieve $q(G)=2$. Several graph families for which it is already known that $q(G)=2$ can also be thought of as arising from this new product.

Figures

Figures reproduced from arXiv: 2501.04297 by the authors.

**Figure 2.** Some examples of graphs where Theorem 11 applies. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Modified strong products of cycles and paths with [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Bordering of symmetric matrices an d an application to the minimum number of distinct eigenvalues for the join of graphs

Aida Abiad, Shaun M Fallat, Mark Kempton, Rupert H Levene, Polon a Oblak, Helena ˇSmigoc, Michael Tait, and Kevin N Vander Meulen. Bordering of symmetric matrices an d an application to the minimum number of distinct eigenvalues for the join of graphs. Linear algebra and its applications , 679:104–126, 2023

work page 2023
[2]

Achievable multiplicity partitions in the inverse eigenvalue problem of a g raph

Mohammad Adm, Shaun Fallat, Karen Meagher, Shahla Nasserasr , Sarah Plosker, and Boting Yang. Achievable multiplicity partitions in the inverse eigenvalue problem of a g raph. Special Matrices , 7(1):276–290, 2019

work page 2019
[3]

Minimum number of distinct eigenvalues of graphs

Bahman Ahmadi, Fatemeh Alinaghipour, Michael S Cavers, Shaun F allat, Karen Meagher, and Shahla Nasserasr. Minimum number of distinct eigenvalues of graphs. Electronic Journal of Linear Algebra , 26:673–691, 2013

work page 2013
[4]

The inverse eigenvalue problem of a gra ph: Multiplicities and minors

Wayne Barrett, Steve Butler, Shaun M Fallat, H Tracy Hall, Leslie H ogben, Jephian C-H Lin, Bryan L Shader, and Michael Young. The inverse eigenvalue problem of a gra ph: Multiplicities and minors. Journal of Combinatorial Theory, Series B , 142:276–306, 2020

work page 2020
[5]

Sparsity of graphs that allow tw o distinct eigenvalues

Wayne Barrett, Shaun Fallat, Veronika Furst, Franklin Kenter, Shahla Nasserasr, Brendan Rooney, Michael Tait, and Hein van der Holst. Sparsity of graphs that allow tw o distinct eigenvalues. Linear Algebra and its Applications , 674:377–395, 2023

work page 2023
[6]

Regular graphs of degree at most four that allow two distinct eigenv alues

Wayne Barrett, Shaun Fallat, Veronika Furst, Shahla Nasseras r, Brendan Rooney, and Michael Tait. Regular graphs of degree at most four that allow two distinct eigenv alues. Linear Algebra and its Applications, 679:127–164, 2023

work page 2023
[7]

Graphs with Bipartite Complement that Admit Two Distinct Eigenvalues

Wayne Barrett, Shaun Fallat, Veronika Furst, Shahla Nasseras r, Brendan Rooney, and Michael Tait. Graphs with bipartite complement that admit two distinct eigenvalues. arXiv preprint arXiv:2411.12917, 2024

work page Pith review arXiv 2024
[8]

Generalizations of the strong arnold property and the minimum numb er of distinct eigenvalues of a graph

Wayne Barrett, Shaun Fallat, H Tracy Hall, Leslie Hogben, Jephian C-H Lin, and Bryan L Shader. Generalizations of the strong arnold property and the minimum numb er of distinct eigenvalues of a graph. Electronic Journal of Combinatorics , 24(2):Paper No. 2.40, 28, 2017

work page 2017

Show all 13 references

[9]

Zero forcing s ets and the minimum rank of graphs

AIM Minimum Rank-Special Graphs Work Group et al. Zero forcing s ets and the minimum rank of graphs. Linear algebra and its applications , 428(7):1628–1648, 2008

2008
[10]

Inverse problems and zero forcing for graphs , volume 270

Leslie Hogben, Jephian C-H Lin, and Bryan L Shader. Inverse problems and zero forcing for graphs , volume 270. American Mathematical Society, 2022. 9

2022
[11]

On the minimum num ber of distinct eigenvalues for a symmetric matrix whose graph is a given tree

Ant´ onio Leal-Duarte and Charles R Johnson. On the minimum num ber of distinct eigenvalues for a symmetric matrix whose graph is a given tree. Mathematical Inequalities and Applications , 5:175–180, 2002

2002
[12]

A nordhaus–gaddum conjecture for the minimum number of distinct eigenvalues of a graph

Rupert H Levene, Polona Oblak, and Helena ˇSmigoc. A nordhaus–gaddum conjecture for the minimum number of distinct eigenvalues of a graph. Linear Algebra and its Applications , 564:236–263, 2019

2019
[13]

Orthogonal symmetric matrices and joins of graphs

Rupert H Levene, Polona Oblak, and Helena ˇSmigoc. Orthogonal symmetric matrices and joins of graphs. Linear Algebra and its Applications , 652:213–238, 2022. 10

2022

Pith tools

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

[1] [1]

Bordering of symmetric matrices an d an application to the minimum number of distinct eigenvalues for the join of graphs

Aida Abiad, Shaun M Fallat, Mark Kempton, Rupert H Levene, Polon a Oblak, Helena ˇSmigoc, Michael Tait, and Kevin N Vander Meulen. Bordering of symmetric matrices an d an application to the minimum number of distinct eigenvalues for the join of graphs. Linear algebra and its applications , 679:104–126, 2023

work page 2023

[2] [2]

Achievable multiplicity partitions in the inverse eigenvalue problem of a g raph

Mohammad Adm, Shaun Fallat, Karen Meagher, Shahla Nasserasr , Sarah Plosker, and Boting Yang. Achievable multiplicity partitions in the inverse eigenvalue problem of a g raph. Special Matrices , 7(1):276–290, 2019

work page 2019

[3] [3]

Minimum number of distinct eigenvalues of graphs

Bahman Ahmadi, Fatemeh Alinaghipour, Michael S Cavers, Shaun F allat, Karen Meagher, and Shahla Nasserasr. Minimum number of distinct eigenvalues of graphs. Electronic Journal of Linear Algebra , 26:673–691, 2013

work page 2013

[4] [4]

The inverse eigenvalue problem of a gra ph: Multiplicities and minors

Wayne Barrett, Steve Butler, Shaun M Fallat, H Tracy Hall, Leslie H ogben, Jephian C-H Lin, Bryan L Shader, and Michael Young. The inverse eigenvalue problem of a gra ph: Multiplicities and minors. Journal of Combinatorial Theory, Series B , 142:276–306, 2020

work page 2020

[5] [5]

Sparsity of graphs that allow tw o distinct eigenvalues

Wayne Barrett, Shaun Fallat, Veronika Furst, Franklin Kenter, Shahla Nasserasr, Brendan Rooney, Michael Tait, and Hein van der Holst. Sparsity of graphs that allow tw o distinct eigenvalues. Linear Algebra and its Applications , 674:377–395, 2023

work page 2023

[6] [6]

Regular graphs of degree at most four that allow two distinct eigenv alues

Wayne Barrett, Shaun Fallat, Veronika Furst, Shahla Nasseras r, Brendan Rooney, and Michael Tait. Regular graphs of degree at most four that allow two distinct eigenv alues. Linear Algebra and its Applications, 679:127–164, 2023

work page 2023

[7] [7]

Graphs with Bipartite Complement that Admit Two Distinct Eigenvalues

Wayne Barrett, Shaun Fallat, Veronika Furst, Shahla Nasseras r, Brendan Rooney, and Michael Tait. Graphs with bipartite complement that admit two distinct eigenvalues. arXiv preprint arXiv:2411.12917, 2024

work page Pith review arXiv 2024

[8] [8]

Generalizations of the strong arnold property and the minimum numb er of distinct eigenvalues of a graph

Wayne Barrett, Shaun Fallat, H Tracy Hall, Leslie Hogben, Jephian C-H Lin, and Bryan L Shader. Generalizations of the strong arnold property and the minimum numb er of distinct eigenvalues of a graph. Electronic Journal of Combinatorics , 24(2):Paper No. 2.40, 28, 2017

work page 2017