A characteristic polynomial for rooted graphs and rooted digraphs Original Research Article

We consider the one-variable characteristic polynomial p(G;λ) in two settings. When G is a rooted digraph, we show that this polynomial essentially counts the number of sinks in G. When G is a rooted graph, we give combinatorial interpretations of several coefficients and the degree of p(G;λ). In particular, |p(G;0)| is the number of acyclic orientations of G, while the degree of p(G;λ) gives the size of the minimum tree cover (every edge of G is adjacent to some edge of T), and the leading coefficient gives the number of such covers. Finally, we consider the class of rooted fans in detail; here p(G;λ) shows cyclotomic behavior.