On the domination polynomial of a digraph

a generation function approach





Generating function, Digraph, Domination polynomial, Minimum-weighted dominating set problem


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.


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.



How to Cite

J. Alencar and L. de Lima, “On the domination polynomial of a digraph: a generation function approach”, Proyecciones (Antofagasta, On line), vol. 40, no. 6, pp. 1587-1602, Nov. 2021.




Most read articles by the same author(s)