The Spectral Theory of Threshold Graphs: A Survey
Abstract
Threshold graphs-the {P4, C4, 2K2}-free graphs, equivalently those built from a single vertex by repeatedly adding isolated or dominating vertices-are among the most thoroughly studied graph classes in spectral graph theory. This survey collects results on the spectrum of threshold graphs across the full range of matrices studied in the literature: the adjacency, Laplacian, and signless Laplacian matrices; the distance, distance Laplacian, and distance signless Laplacian matrices; the eccentricity and Seidel matrices; and the normalized adjacency, Laplacian matrix-together with the associated graph energies, cospectrality questions, extremal spectral radius problems, and several generalizations (weighted, quasi-threshold, hypergraph, and random threshold graphs). We emphasize results from the recent years, including the foundational work of Chvátal--Hammer, Merris, Bapat, and Jacobs--Lazzarin--Trevisan--Tura. We also present a study of integral threshold graphs (those with all-integer spectrum) across all seven matrices. We close with a list of open problems and conjectures drawn directly from the surveyed literature and from this new analysis.
Related
- Spectral Theory and Descriptive Combinatorics for Non-Regular Borel pmp Graphs
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- Minimal transitive factorizations supported on quasi-threshold graphs
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- The Connectivity Threshold for Friends and Strangers graphs
BibTeX
@misc{manna2026spectral,
title = {{The Spectral Theory of Threshold Graphs: A Survey}},
author = {Pallabi Manna and Santanu Mandal and Fernando C. Tura},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22838},
eprint = {2610.22838},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22838},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Spectral Theory of Threshold Graphs: A Survey
AU - Pallabi Manna
AU - Santanu Mandal
AU - Fernando C. Tura
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.22838
UR - https://arxiv.org/abs/2610.22838
AB - Threshold graphs-the {P_4, C_4, 2K_2}-free graphs, equivalently those built from a single vertex by repeatedly adding isolated or dominating vertices-are among the most thoroughly studied graph classes in spectral graph theory. This survey collects results on the spectrum of threshold graphs across the full range of matrices studied in the literature: the adjacency, Laplacian, and signless Laplacian matrices; the distance, distance Laplacian, and distance signless Laplacian matrices; the eccentricity and Seidel matrices; and the normalized adjacency, Laplacian matrix-together with the associated graph energies, cospectrality questions, extremal spectral radius problems, and several generalizations (weighted, quasi-threshold, hypergraph, and random threshold graphs). We emphasize results from the recent years, including the foundational work of Chvátal--Hammer, Merris, Bapat, and Jacobs--Lazzarin--Trevisan--Tura. We also present a study of integral threshold graphs (those with all-integer spectrum) across all seven matrices. We close with a list of open problems and conjectures drawn directly from the surveyed literature and from this new analysis.
ER -