On the domination polynomial of a digraph
a generation function approach
DOI:
https://doi.org/10.22199/issn.0717-6279-4684Keywords:
Generating function, Digraph, Domination polynomial, Minimum-weighted dominating set problemAbstract
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.
References
S. Akbari, S. Alikhani, and Y-H. Peng, “Characterization of graphs using domination polynomials”, European journal of combinatorics, vol. 31, no. 7, pp. 1714-1724, 2010.
S. Alikhani, Dominating sets and domination polynomials of graphs. Lap Lambert Academic, 2012.
S. Alikhani and Y-H. Peng, “Introduction to domination poly nomial of a graph”, Ars Combinatoria, vol. 114, pp. 257-266, 2014.
G. Chartrand, F. Harary and B. Quan Yue, “On the out- domination and in-domination numbers of a digraph”, Discrete mathematics, vol. 197-198, pp. 179-183, 1999.
J. Ghoshal, R. Laskar, and D. Pillone, “Topics on domination in directed graphs”, in Domination in graphs advanced topics, T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Eds. New York, NY: Routledge, 1998, pp. 401–437.
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs. New York, NY: CRC, 1998.
C. Pang, R. Zhang, Q. Zhang, and J. Wang, “Dominating sets in directed graphs”, Information sciences, vol. 180, no. 19, pp. 3647-3652, 2010.
F. Zou, Y. Wang, X-H. Xu, X. Li, H. Du, P. Wan, and W. Wu, “New approximations for minimum- weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs”, Theoretical computer science, vol. 412, no. 3, pp. 198-208, 2011.
Published
How to Cite
Issue
Section
Copyright (c) 2021 Jorge Alencar, Leonardo de Lima
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
