A conjecture on the eigenvalues of threshold graphs (Q2228534)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A conjecture on the eigenvalues of threshold graphs |
scientific article |
Statements
A conjecture on the eigenvalues of threshold graphs (English)
0 references
17 February 2021
0 references
A simple graph \(G = (V, E)\) is called a threshold graph if there exists a function \(w: V \rightarrow [0,\infty)\) and a non-negative real number \(t\) such that \(uv \in E\) if and only if \(w(u) + w(v) \ge t\). A simple graph is called an anti-regular graph if only two vertices of it have equal degrees. It is known that, up to isomorphism, there is exactly one connected anti-regular graph on \(n\) vertices, which is denoted as \(A_n\). Anti-regular graphs form a subfamily of the family of threshold graphs. In [\textit{C. O. Aguilar} et al., Linear Algebra Appl. 557, 84--104 (2018; Zbl 1396.05064)], it was conjectured that for each \(n\), \(A_n\) has the smallest positive eigenvalue and the largest negative eigenvalue less than \(-1\) among all threshold graphs on \(n\) vertices. In [\textit{C. O. Aguilar} et al., ibid. 588, 210--223 (2020; Zbl 1437.05128)], this conjecture was proved for all threshold graphs on \(n\) vertices except for \(n - 2\) critical cases where the interlacing method fails. In this paper, the author deals with these cases and thereby completes the proof of this conjecture.
0 references
threshold graph
0 references
anti-regular graph
0 references
adjacency matrix
0 references
eigenvalues
0 references
0 references