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

• Alencar, Jorge ^[2] ; de Lima, Leonardo ^[1]
  1. [1] Universidade Federal do Paraná

     Universidade Federal do Paraná

     Brasil

     
  2. [2] Instituto Federal de Educação, Ciência e Tecnologia do Triângulo Mineiro
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 40, Nº. 6, 2021, págs. 1587-1602
• Idioma: inglés
• DOI: 10.22199/issn.0717-6279-4684
• Enlaces
  • Texto completo
• Resumen

  • 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.

• Referencias bibliográficas
  • S. Akbari, S. Alikhani, and Y-H. Peng, “Characterization of graphs using domination polynomials”, European journal of combinatorics, vol....
  • 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,...
  • J. Ghoshal, R. Laskar, and D. Pillone, “Topics on domination in directed graphs”, in Domination in graphs advanced topics, T. W. Haynes, S....
  • 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...