An explicit formula for the distance characteristic polynomial of threshold graphs

DOI10.1007/S40314-023-02350-6arXiv1811.03061OpenAlexW2899860932MaRDI QIDQ6159856FDOQ6159856

Authors: João Lazzarin, Oscar F. Márquez, Fernando Colman Tura 

Publication date: 22 June 2023

Published in: Computational and Applied Mathematics (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 distance characteristic polynomial of a threshold graph from its binary sequence. As application, we show a several of nonisomorphic pairwise threshold graphs which are {D}-cospectral graphs.

Full work available at URL: https://arxiv.org/abs/1811.03061

Recommendations

• No threshold graphs are cospectral
• On the distance spectra of threshold graphs
• Computing the characteristic polynomial of threshold graphs
• On the eigenvalues distribution in threshold graphs
• Efficient computation of the characteristic polynomial of a threshold graph

zbMATH Keywords

threshold graphdistance characteristic polynomial\(\mathcal{D}\)-cospectral graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18) Graph polynomials (05C31) Distance in graphs (05C12)

Cites Work

• Distance spectra of graphs: a survey
• Distance spectrum of graph compositions
• Eigenvalues and energy in threshold graphs
• On the Addressing Problem for Loop Switching
• Constructing cospectral graphs
• Threshold graphs and related topics
• Title not available (Why is that?)
• Wiener index of trees: Theory and applications
• Eigenvalue location in threshold graphs
• On the adjacency matrix of a threshold graph
• Title not available (Why is that?)
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Exploring symmetries to decompose matrices and graphs preserving the spectrum
• Title not available (Why is that?)
• 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
• No threshold graphs are cospectral
• On the distance spectra of threshold graphs

This page was built for publication: An explicit formula for the distance characteristic polynomial of threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159856)