A Note on the Laplacian Eigenvectors of Threshold Graphs

James L. Borg; Irene Sciriha; Zoia Sherman

paper

A Note on the Laplacian Eigenvectors of Threshold Graphs

arXiv:2605.03645

Abstract

Threshold graphs are graphs that can be characterized in a number of different ways. For example, they are graphs that are $P_{4}, C_{4}, 2 K_{2}$ --free. They may also be characterized by a finite sequence of positive integers $a_{1}, \dots, a_{r}$ , such that $a_{1} ⩾ 2$ and $a_{1} + a_{2} + \dots + a_{r} = ∣ V (G) ∣$ . Threshold graphs have the remarkable property that all graphs of the same order share a common integer Laplacian eigenbasis. This property characterizes threshold graphs. This result was proved in \cite{MachareteDelVecchio}. We give a different proof of the same result.