No threshold graphs are cospectral
From MaRDI portal
Publication:1625488
DOI10.1016/J.LAA.2018.09.033zbMATH Open1401.05152arXiv1806.07358OpenAlexW2963345395MaRDI QIDQ1625488FDOQ1625488
Fernando Colman Tura, Oscar F. Márquez, João Lazzarin
Publication date: 29 November 2018
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: A threshold graph G on n vertices is defined by binary sequence of length n. In this paper we present an explicit formula for computing the characteristic polynomial of a threshold graph from its binary sequence. Applications include obtaining a formula for the determinant of adjacency matrix of a threshold graph and showing that no two nonisomorphic threshold graphs are cospectral.
Full work available at URL: https://arxiv.org/abs/1806.07358
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Eigenvalues and energy in threshold graphs
- Constructing cospectral graphs
- Threshold graphs and related topics
- Eigenvalue location in threshold graphs
- On the adjacency matrix of a threshold graph
- Eigenvalue location for chain graphs
- A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
- On nested split graphs whose second largest eigenvalue is less than 1
- On the spectrum of threshold graphs
- Connected graphs of fixed order and size with maximal index: some spectral bounds
- Computing the Characteristic Polynomial of Threshold Graphs
- Efficient computation of the characteristic polynomial of a threshold graph
- Fast algorithms for computing the characteristic polynomial of threshold and chain graphs
- Exponentially many graphs have a \(Q\)-cospectral mate
Cited In (18)
- Integral cographs
- On bipartite graphs having minimum fourth adjacency coefficient
- A conjecture on the eigenvalues of threshold graphs
- An explicit formula for the distance characteristic polynomial of threshold graphs
- Each \((n,m)\)-graph having the \(i\)-th minimal Laplacian coefficient is a threshold graph
- Laplacian eigenvalues of equivalent cographs
- Almost controllable graphs and beyond
- On the eigenvalues distribution in threshold graphs
- Eigenvalue-free intervals of distance matrices of threshold and chain graphs
- Tridiagonal matrices and spectral properties of some graph classes
- A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
- Characterizing threshold graphs with \(k\) main signless Laplacian eigenvalues
- The role of the anti-regular graph in the spectral analysis of threshold graphs
- Threshold Graphs with an Arbitrary Large Gap Set
- Laplacian eigenvalues of weighted threshold graphs
- On the Seidel spectrum of threshold graphs
- Eigenvalue-free interval for Seidel matrices of cographs
- Some Properties of Chain and Threshold Graphs
This page was built for publication: No threshold graphs are cospectral
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1625488)
