pith. sign in

arxiv: 1906.08690 · v1 · pith:D2QK3QBXnew · submitted 2019-06-20 · 🧮 math.CO

The strong spectral property for graphs

Jephian C.-H. Lin , Polona Oblak , Helena \v{S}migoc This is my paper

Pith reviewed 2026-05-25 19:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords strong spectral propertygraphstreessymmetric matriceszero-nonzero patternspectral propertiescombinatorial matrix theory
0
0 comments X

The pith

The trees belonging to G^SSP are characterised, where G^SSP is the set of graphs for which every symmetric matrix with the graph pattern has the strong spectral property.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the set G^SSP of graphs where every symmetric matrix with the graph's zero-nonzero pattern has the strong spectral property. It identifies several families of such graphs. In particular, it provides a characterization of the trees that belong to this set. This is of interest because the strong spectral property links graph structure to the spectral behavior of associated matrices, which is central to problems like the inverse eigenvalue problem for graphs.

Core claim

We introduce the set G^SSP of all simple graphs G with the property that each symmetric matrix corresponding to a graph G in G^SSP has the strong spectral property. We find several families of graphs in G^SSP and, in particular, characterise the trees in G^SSP.

What carries the argument

The set G^SSP, consisting of graphs for which the strong spectral property holds for all matrices matching the graph pattern.

If this is right

  • The characterization gives a combinatorial criterion for when the strong spectral property holds uniformly for a tree.
  • Several families of graphs satisfy the condition that all their pattern matrices have the strong spectral property.
  • The property is shown to be determined by the graph structure alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The characterization provides a way to verify the property without examining individual matrices for trees.
  • This result may be useful for constructing graphs with prescribed spectral properties.
  • It opens the door to similar characterizations for other graph classes such as cycles or bipartite graphs.

Load-bearing premise

The strong spectral property is a well-defined condition on symmetric matrices that depends only on the zero-nonzero pattern of the graph and can be required to hold uniformly for every matrix with that pattern.

What would settle it

Finding a tree that according to the characterization should have the strong spectral property but for which there exists a symmetric matrix with the corresponding pattern that does not, or the opposite case.

Figures

Figures reproduced from arXiv: 1906.08690 by Helena \v{S}migoc, Jephian C.-H. Lin, Polona Oblak.

Figure 1
Figure 1. Figure 1: Since {1, 2} is focused on {3} with respect to G (see Example 3.2), we have {1, 2} G −→ G {1, 3}, and we define G1 = G+{1, 3}. (See [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
read the original abstract

We introduce the set $\mathcal{G}^{\rm SSP}$ of all simple graphs $G$ with the property that each symmetric matrix corresponding to a graph $G \in \mathcal{G}^{\rm SSP}$ has the strong spectral property. We find several families of graphs in $\mathcal{G}^{\rm SSP}$ and, in particular, characterise the trees in $\mathcal{G}^{\rm SSP}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper defines the class G^SSP of simple graphs G such that every real symmetric matrix whose zero-nonzero pattern is exactly G has the strong spectral property (SSP). It exhibits several infinite families belonging to G^SSP and supplies a complete characterization of the trees that lie in G^SSP.

Significance. A correct characterization of the trees in G^SSP would furnish an explicit, checkable criterion for when the SSP holds uniformly over all realizations of a tree pattern. This directly supports the inverse eigenvalue problem by identifying graphs for which every admissible spectrum is realizable with the SSP, and the listed families supply concrete examples that can be used in constructions.

minor comments (2)
  1. [Abstract] The abstract states the characterization result but does not indicate the precise combinatorial condition on the trees; a one-sentence description of the condition would improve readability for readers outside the immediate subfield.
  2. [Introduction] Notation for the strong spectral property is introduced via the set G^SSP; a brief reminder of the matrix-theoretic definition of SSP (e.g., the existence of a matrix with distinct eigenvalues whose eigenspaces satisfy a certain independence condition) in the first paragraph of the introduction would help readers who encounter the paper in isolation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The referee report contains no major comments.

Circularity Check

0 steps flagged

No significant circularity; characterization is self-contained

full rationale

The paper defines G^SSP directly from the uniform strong spectral property on pattern matrices, then states a characterization of the trees belonging to this set. No equations or claims reduce a derived quantity to a fitted parameter or prior self-citation by construction. The result is a standard pattern-based classification in inverse eigenvalue theory with no load-bearing self-referential steps visible in the abstract or described structure.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are described.

pith-pipeline@v0.9.0 · 5582 in / 929 out tokens · 38604 ms · 2026-05-25T19:33:46.287612+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Cavers , Shaun Fallat, Karen Meagher, and Shahla Nasserasr

    Bahman Ahmadi, Fatemeh Alinaghipour, Michael S. Cavers , Shaun Fallat, Karen Meagher, and Shahla Nasserasr. Minimum numbe r of distinct eigenvalues of graphs. Electron. J. Linear Algebra , 26:673– 691, 2013

    work page 2013

  2. [2]

    J. Ahn, C. Alar, B. Bjorkman, S. Butler, J. Carlson, A. Goo dnight, H. Knox, C. Monroe, and M. C. Wigal. Ordered multiplicity inv erse eigenvalue problem for graphs on six vertices. ArXiv e-prints , August 2017

    work page 2017

  3. [3]

    Hall, Zhongshan Li, and Hein van der Holst

    Marina Arav, Frank J. Hall, Zhongshan Li, and Hein van der Holst. The inertia set of a signed graph. Linear Algebra Appl. , 439(5):1506– 1529, 2013. 30 JEPHIAN C.-H. LIN, POLONA OBLAK, AND HELENA ˇSMIGOC

    work page 2013

  4. [4]

    A va riant on the graph parameters of Colin de Verdi` ere: implications to the minimum rank of graphs

    Francesco Barioli, Shaun Fallat, and Leslie Hogben. A va riant on the graph parameters of Colin de Verdi` ere: implications to the minimum rank of graphs. Electron. J. Linear Algebra , 13:387–404, 2005

    work page 2005

  5. [5]

    Barrett, S

    W. Barrett, S. Butler, S. M. Fallat, H. T. Hall, L. Hogben, J. C.-H. Lin, B. L. Shader, and M. Young. The inverse eigenvalue probl em of a graph: Multiplicities and minors. ArXiv e-prints, July 2017

    work page 2017

  6. [6]

    Barrett, S

    W. Barrett, S. Fallat, H. T. Hall, L. Hogben, J. C.-H. Lin, and B. L. Shader. Generalizations of the strong Arnold property and t he mini- mum number of distinct eigenvalues of a graph. Electron. J. Combin. , 24(2):Paper 2.40, 28, 2017

    work page 2017

  7. [7]

    The comb ina- torial inverse eigenvalue problem: complete graphs and sma ll graphs with strict inequality

    Wayne Barrett, Anne Lazenby, Nicole Malloy, Curtis Nels on, William Sexton, Ryan Smith, John Sinkovic, and Tianyi Yang. The comb ina- torial inverse eigenvalue problem: complete graphs and sma ll graphs with strict inequality. Electron. J. Linear Algebra , 26:656–672, 2013

    work page 2013

  8. [8]

    The combinatorial inverse eigenvalue problem II: All cases for small graphs

    Wayne Barrett, Curtis Nelson, John Sinkovic, and Tianyi Yang. The combinatorial inverse eigenvalue problem II: All cases for small graphs. Electron. J. Linear Algebra , 27:742–778, 2014

    work page 2014

  9. [9]

    Bjorkman, L

    B. Bjorkman, L. Hogben, S. Ponce, C. Reinhart, and T. Tran el. Appli- cations of analysis to the determination of the minimum numb er of distinct eigenvalues of a graph. ArXiv e-prints, August 2017

    work page 2017

  10. [10]

    Sur un nouvel invariant des gra phes et un crit` ere de planarit´ e.J

    Yves Colin de Verdi` ere. Sur un nouvel invariant des gra phes et un crit` ere de planarit´ e.J. Combin. Theory Ser . B, 50(1):11–21, 1990

    work page 1990

  11. [11]

    On a new graph invariant and a cr iterion for planarity

    Yves Colin de Verdi` ere. On a new graph invariant and a cr iterion for planarity. In Graph structure theory (Seattle, WA, 1991) , volume 147 of Contemp. Math., pages 137–147. Amer. Math. Soc., Providence, RI, 1993

    work page 1991

  12. [12]

    Fallat and L

    S. Fallat and L. Hogben. Minimum rank, maximum nullity, and zero forcing number of graphs. In Leslie Hogben, editor, Handbook of lin- ear algebra, Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, second edition, 2014

    work page 2014

  13. [13]

    Fallat and Leslie Hogben

    Shaun M. Fallat and Leslie Hogben. The minimum rank of sy mmetric matrices described by a graph: a survey. Linear Algebra Appl. , 426(2- 3):558–582, 2007

    work page 2007

  14. [14]

    A characterization of tridiagonal m atrices

    Miroslav Fiedler. A characterization of tridiagonal m atrices. Linear Al- gebra and Appl. , 2:191–197, 1969

    work page 1969

  15. [15]

    Graham M. L. Gladwell. Inverse problems in vibration , volume 119 of Solid Mechanics and its Applications . Kluwer Academic Publishers, Dordrecht, second edition, 2004

    work page 2004

  16. [16]

    Zero forci ng sets and the minimum rank of graphs

    AIM Minimum Rank-Special Graphs Work Group. Zero forci ng sets and the minimum rank of graphs. Linear Algebra Appl. , 428(7):1628– 1648, 2008

    work page 2008

  17. [17]

    Levene, Polona Oblak, and Helena ˇSmigoc

    Rupert H. Levene, Polona Oblak, and Helena ˇSmigoc. A Nordhaus- Gaddum conjecture for the minimum number of distinct eigenv alues of a graph. Linear Algebra Appl. , 564:236–263, 2019

    work page 2019

  18. [18]

    Jephian C.-H. Lin. Using a new zero forcing process to gu arantee the strong Arnold property. Linear Algebra Appl. , 507:229–250, 2016. THE STRONG SPECTRAL PROPERTY FOR GRAPHS 31

    work page 2016

  19. [19]

    Lov ´ asz and A

    L. Lov ´ asz and A. Schrijver. On the null space of a Colin d e Verdi` ere matrix. Ann. Inst. Fourier (Grenoble) , 49(3):1017–1026, 1999. Sympo- sium ` a la M´ emoire de Franc ¸ ois Jaeger (Grenoble, 1998)

    work page 1999

  20. [20]

    The strong Arn old property for 4-connected flat graphs

    Alexander Schrijver and Bart Sevenster. The strong Arn old property for 4-connected flat graphs. Linear Algebra Appl., 522:153–160, 2017

    work page 2017

  21. [21]

    Some connectivity properties for ex cluded mi- nors of the graph invariant ν(G)

    Hein van der Holst. Some connectivity properties for ex cluded mi- nors of the graph invariant ν(G). European J. Combin., 24(7):929–946, 2003. (J. C.-H. Lin) D EPAR TMENT OF APPLIED MATHEMATICS , N ATIONAL SUN YAT -SEN UNIVERSITY , K AOHSIUNG 80424, T AIWAN E-mail address: jephianlin@gmail.com (P. Oblak) F ACULTY OF COMPUTER AND INFORMATION SCIENCE , U NI...

    work page 2003