# Efficient Computation of the Characteristic Polynomial of a Threshold Graph

arXiv: https://arxiv.org/abs/1503.00617 · HTML: https://mlsanity.com/paper/1503.00617/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2015.

## Built on by (most cited first, 1 of 1)

- [Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms](https://mlsanity.com/paper/2601.22943/) (2026)

## Abstract (arXiv)

An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chv'atal and Hammer, as well as by Henderson and Zalcstein in 1977. A threshold graph is obtained from a one vertex graph by repeatedly adding either an isolated vertex or a dominating vertex, which is a vertex adjacent to all the other vertices. Threshold graphs are special kinds of cographs, which themselves are special kinds of graphs of clique-width 2. We obtain a running time of O(n log2 n) for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time. Keywords: Efficient Algorithms, Threshold Graphs, Characteristic Polynomial.