Computing the Characteristic Polynomial of Threshold Graphs

David Jacobs; Vilmar Trevisan; Fernando Tura

doi:10.7155/jgaa.00342

Computing the Characteristic Polynomial of Threshold Graphs

Authors

David Jacobs
Vilmar Trevisan
Fernando Tura

DOI:

https://doi.org/10.7155/jgaa.00342

Abstract

We present an algorithm for constructing the characteristic polynomial of a threshold graph's adjacency matrix. The algorithm is based on a diagonalization procedure that is easy to describe. It can be implemented using O(n) space and with running time O(n²).

Downloads

Download data is not yet available.

Downloads

article (PDF)

Published

2014-12-01

How to Cite

Jacobs, D., Trevisan, V., & Tura, F. (2014). Computing the Characteristic Polynomial of Threshold Graphs. Journal of Graph Algorithms and Applications, 18(5), 709–719. https://doi.org/10.7155/jgaa.00342