A formula for the eigenvalues of underlying threshold multigraphs

Abstract

Threshold graphs are graphs whose node set can be partitioned into a clique and an independent set, with the additional property that for each pair of nodes, one’s neighborhood is a subset of the other’s neighborhood. Threshold graphs have been well-studied in graph theory, but not much is known about multigraphs that are underlying threshold. Proper threshold graphs are those in which all nodes in the independent set have the same degree. In this paper, we present a formula for the eigenvalues of a particular class of multigraphs that are underlying proper threshold.