Open AccessOn the domination polynomial of a digraph: a generation function approach
Author(s) -
Jorge Alencar,
Leonardo de Lima
Publication year - 2021
Publication title -
proyecciones
Language(s) - English
Resource type - Journals
eISSN - 0717-6279
pISSN - 0716-0917
DOI - 10.22199/issn.0717-6279-4684
Subject(s) - digraph , combinatorics , mathematics , dominating set , graph , polynomial , domination analysis , discrete mathematics , function (biology) , vertex (graph theory) , mathematical analysis , evolutionary biology , biology
Let G be a directed graph on n vertices. The domination polynomial of G is the polynomial D(G, x) =∑ni=0 d(G, i)xi, 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. Besides, we show that our method is useful to obtain the minimum-weighted dominating set of a graph.