A characteristic polynomial for rooted graphs and rooted digraphs (Q5937442)

The paper investigates the characteristic polynomial \(p(G,\lambda)\) by concentrating exclusively on rooted graphs and digraphs \(G\). It is shown that when \(G\) is a rooted digraph, this polynomial essentially counts the number of sinks in \(G\). When \(G\) is a rooted graph, the authors give combinatorial interpretations of several coefficients and the degree of \(p(G,\lambda)\). In particular, it is shown that \(|p(G,0)|\) is the number of acyclic orientations of \(G\), while the degree of \(p(G,\lambda)\) gives the size of the minimum tree cover, and the leading coefficient gives the number of such covers. Finally, the paper considers the class of rooted fans in detail by showing that \(p(G,\lambda)\) exhibits cyclotomic behavior.