On the domination polynomial of a digraph: a generation function approach
Author
Alencar, Jorge
de Lima, Leonardo
Full text
https://www.revistaproyecciones.cl/index.php/proyecciones/article/view/468410.22199/issn.0717-6279-4684
Abstract
Let $G$ be a directed graph on $n$ vertices. The domination polynomial of $G$ is the polynomial $D(G, x) = \sum^n_{i=0} d(G, i)x^i$, where $d(G, i)$ is the number of dominating sets of $G$ with $i$ vertices. In this paper, we prove that the domination polynomial of $G$ can be obtained by using an ordinary generating function, which can be extended to undirected graphs. Besides, we show that our method is useful to obtain the minimum-weighted dominating set of a graph.