A conjecture on the eigenvalues of threshold graphs

DOI10.1016/J.LAA.2020.11.007MaRDI QIDQ2228534zbMATH OpenOpenAlexWikidataFDO

Authors Fernando Colman Tura

Publication date 17 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.03136

zbMATH Keywords

adjacency matrixanti-regular grapheigenvaluesthreshold graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Let $A_n$ be the anti-regular graph of order $n.$ It was conjectured that among all threshold graphs on $n$ vertices, $A_n$ has the smallest positive eigenvalue and the largest eigenvalue less than $-1.$ Recently, in cite{Cesar2} was given partial results for this conjecture and identified the critical cases where a more refined method is needed. In this paper, we deal with these cases and confirm that conjecture holds.

Review text

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.

Recommendations

• On the eigenvalues distribution in threshold graphs
• Eigenvalues and energy in threshold graphs
• On the minimum number of distinct eigenvalues of a threshold graph
• On the spectrum of threshold graphs
• Eigenvalue-free interval for threshold graphs
• Eigenvalue location in threshold graphs
• scientific article; zbMATH DE number 5575414
• On the adjacency matrix of a threshold graph
• Eigenvalue-free interval for Seidel matrices of threshold graphs
• On the eccentricity spectra of threshold graphs

Cites work

• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Eigenvalue location in threshold graphs
• Eigenvalue-free interval for threshold graphs
• Eigenvalues and energy in threshold graphs
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• No threshold graphs are cospectral
• On the adjacency matrix of a threshold graph
• On the eigenvalues distribution in threshold graphs
• On the spectrum of threshold graphs
• Spectral characterizations of anti-regular graphs
• The role of the anti-regular graph in the spectral analysis of threshold graphs
• Threshold graphs and related topics

Cited in

(11)

• Spectral characterizations of anti-regular graphs
• Validity of Akbari's energy conjecture for threshold graphs
• The role of the anti-regular graph in the spectral analysis of threshold graphs
• Eigenvalue-free interval for threshold graphs
• Eigenvalue location in threshold graphs
• On the adjacency matrix of a threshold graph
• scientific article; zbMATH DE number 5575414 (Why is no real title available?)
• Eigenvalue-free intervals of distance matrices of threshold and chain graphs
• Multithreshold multipartite graphs
• Laplacian eigenvalues of equivalent cographs
• Some notes on the threshold graphs

This page was built for publication: A conjecture on the eigenvalues of threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2228534)