Fast algorithms for computing the characteristic polynomial of threshold and chain graphs

DOI10.1016/J.AMC.2018.03.024MaRDI QIDQ2333249zbMATH OpenOpenAlexWikidataFDO

Authors Milica Andelić, Dejan Živković, E. Ć. Dolićanin, Slobodan K. Simić

Publication date 12 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2018.03.024

zbMATH Keywords

adjacency matrixcharacteristic polynomialthreshold graphchain graphlexicographic productgraph divisor

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph polynomials (05C31)

Recommendations

• Efficient computation of the characteristic polynomial of a threshold graph
• Efficient computation of the characteristic polynomial of a threshold graph
• Computing the characteristic polynomial of threshold graphs
• Evaluation of the characteristic polynomial of a graph
• Computing the characteristic polynomial of a tree

Cites work

• scientific article; zbMATH DE number 5177331 (Why is no real title available?)
• scientific article; zbMATH DE number 3972892 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• A new graph product and its spectrum
• An introduction to the theory of graph spectra
• Combinatorial approach for computing the characteristic polynomial of a matrix
• Computing the characteristic polynomial of threshold graphs
• Difference graphs
• Efficient computation of the characteristic polynomial of a threshold graph
• Eigenvalue location for chain graphs
• Graph Classes: A Survey
• Graphs for which the least eigenvalue is minimal. I
• Graphs for which the least eigenvalue is minimal. II.
• On the first eigenvalue of bipartite graphs
• Spectra of graphs obtained by a generalization of the join graph operation
• The Complexity of the Partial Order Dimension Problem
• Threshold graph limits and random threshold graphs
• Threshold graphs and related topics

Cited in

(8)

• Computing the characteristic polynomial of threshold graphs
• No threshold graphs are cospectral
• Evaluation of the characteristic polynomial of a graph
• Characterizing threshold graphs with k main signless Laplacian eigenvalues
• Threshold Graphs with an Arbitrary Large Gap Set
• Efficient computation of the characteristic polynomial of a threshold graph
• Efficient computation of the characteristic polynomial of a threshold graph
• Tridiagonal matrices and spectral properties of some graph classes.

This page was built for publication: Fast algorithms for computing the characteristic polynomial of threshold and chain graphs

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