A characteristic polynomial for rooted graphs and rooted digraphs (Q5937442)
From MaRDI portal
scientific article; zbMATH DE number 1619278
Language | Label | Description | Also known as |
---|---|---|---|
English | A characteristic polynomial for rooted graphs and rooted digraphs |
scientific article; zbMATH DE number 1619278 |
Statements
A characteristic polynomial for rooted graphs and rooted digraphs (English)
0 references
21 February 2002
0 references
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.
0 references
characteristic polynomial
0 references
rooted graphs and digraphs
0 references
cover
0 references