The Spectral Theory of Threshold Graphs: A Survey

Source abstract

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.