Laplacian spectra and spanning trees of threshold graphs
type: Item
instance of: scholarly article
title: Laplacian spectra and spanning trees of threshold graphs
zbMATH Open document ID: 0860.05055
DOI: 10.1016/0166-218X(94)00049-J
author: Peter L. Hammer
author: Alexander Kelmans
published in: Discrete Applied Mathematics
publication date: 1997-04-21T00:00:00Z
full work available at URL: dam
review text: 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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 897383
zbMATH Keywords: threshold graph
zbMATH Keywords: Laplacian spectrum
zbMATH Keywords: Laplacian polynomial
zbMATH Keywords: number of spanning trees
reviewed by: Regina Iosifovna Tyshkevich
MaRDI profile type: Publication
cites work: Q5596091
cites work: Q5422499
cites work: Strongly regular graphs, partial geometries and partially balanced designs
cites work: Q4190651
cites work: Q4165164
cites work: Q4726256
cites work: Q5648382
cites work: Developments in the theory of graph spectra
cites work: Q4327350
cites work: Laplacian eigenvalues and the maximum cut problem
cites work: Nonisomorphic trees with the same T-polynomial
cites work: On characterizing certain graphs with four eigenvalues by their spectra
cites work: A spectral characterization of the line graph of a BIBD with \(\lambda=1\)
cites work: Q3287781
cites work: Q5682350
cites work: Q3328583
cites work: The Laplacian Spectrum of a Graph
cites work: Threshold Sequences
cites work: Parallel concepts in graph theory
cites work: On the Line Graph of a Projective Plane
cites work: On the line Graph of a Finite Affine Plane
cites work: On the Line Graph of a Symmetric Balanced Incomplete Block Design
cites work: Transformations of a graph increasing its Laplacian polynomial and number of spanning trees
cites work: Comparison of graphs by their number of spanning trees
cites work: Graphs with an extremal number of spanning trees
cites work: A certain polynomial of a graph and graphs with an extremal number of trees
cites work: Graphic sequences with unique realization
cites work: Threshold graphs and related topics
cites work: Q5602686
cites work: The characteristic polynomial of a graph
cites work: The Uniqueness of the $\mathrm{L}_2$ Association Scheme
cites work: Q5676231
cites work: Q3926615
description: scientific article; zbMATH DE number 897383