Show simple item record

On the domination polynomial of a digraph: a generation function approach

dc.creatorAlencar, Jorge
dc.creatorde Lima, Leonardo
dc.date2021-11-29
dc.date.accessioned2022-08-30T15:59:39Z
dc.date.available2022-08-30T15:59:39Z
dc.identifierhttps://www.revistaproyecciones.cl/index.php/proyecciones/article/view/4684
dc.identifier10.22199/issn.0717-6279-4684
dc.identifier.urihttps://revistaschilenas.uchile.cl/handle/2250/207091
dc.descriptionLet $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.en-US
dc.formatapplication/pdf
dc.languageeng
dc.publisherUniversidad Católica del Norte.en-US
dc.relationhttps://www.revistaproyecciones.cl/index.php/proyecciones/article/view/4684/3939
dc.rightsCopyright (c) 2021 Jorge Alencar, Leonardo de Limaen-US
dc.rightshttps://creativecommons.org/licenses/by/4.0en-US
dc.sourceProyecciones (Antofagasta, On line); Vol. 40 No. 6 (2021); 1587-1602en-US
dc.sourceProyecciones. Revista de Matemática; Vol. 40 Núm. 6 (2021); 1587-1602es-ES
dc.source0717-6279
dc.source10.22199/issn.0717-6279-2021-06
dc.subjectGenerating functionen-US
dc.subjectDigraphen-US
dc.subjectDomination polynomialen-US
dc.subjectMinimum-weighted dominating set problemen-US
dc.subjectAlgebraen-US
dc.subjectCombinatoricsen-US
dc.subjectGraph Theoryen-US
dc.titleOn the domination polynomial of a digraph: a generation function approachen-US
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion
dc.typePeer-reviewed Articleen-US
dc.typetexten-US


This item appears in the following Collection(s)

Show simple item record