Laplacian spectra and spanning trees of threshold graphs (Q1917274)

For an arbitrary threshold graph formulas for its Laplacian spectrum, Laplacian polynomial, and the number of spanning trees in terms of its degree sequence are found. It is proved that a threshold graph is uniquely determined by its Laplacian spectrum and that this spectrum consists of integers. A procedure of recognizing in polynomial time whether a given polynomial (or a sequence of integers) is the Laplacian polynomial (or the spectrum) of a threshold graph is given. The research is based on the Kelmans results in [The number of trees of a graph. I. II., Automat. Remote Control 26, 2118-2129 (1965); 27, 233-241 (1966; Zbl 0146.45902); translation from Avtomat. Telemekh. 26, 2194-2204 (1965) and 27, 56-65 (1966)] and [On properties of the characteristic polynomial of a graph (in Russian), Kibernetiku na Sluzbu Kommunizmu 4, 27-41 (1967; Zbl 0204.24403)] which are stated in the paper.