О количестве наименьших полных доминирующих множеств в деревьях

О количестве наименьших полных доминирующих множеств в деревьях

Талецкий Д. С.
Дискретный анализ и исследование операций, 30, 1, 110-129 (2023)
Скачать статью

УДК 519.17
DOI: 10.33048/daio.2023.30.745

Аннотация:

Наименьшим полным доминирующим множеством графа (НПДМ) называется подмножество его вершин $D$ наименьшей мощности такое, что каждая вершина графа смежна хотя бы с одной вершиной из $D$. В работе получена точная верхняя оценка числа НПДМ в классе $n$-вершинных 2-гусениц. Кроме того, показано, что при всех $n \ge 1$ каждое $n$-вершинное дерево содержит менее чем $(\sqrt{2})^n$ НПДМ.
Ил. 5, библиогр. 6.

Литература:
  1. Bród D., Skupien Z. Trees with extremal numbers of dominating sets // Australas. J. Comb. 2006. Vol. 35. P. 273–290.
     
  2. Krzywkowski M., Wagner S. Graphs with few total dominating sets // Discrete Math. 2018. Vol. 341, No. 4. P. 997–1009.
     
  3. Bien A. Properties of gamma graphs of trees // Colourings, independence and domination. Abs. 17th Workshop Graph Theory (Piechowice, Poland, Sept. 17–22, 2017). Zielona Góra: Univ. Zielona Góra, 2017. 1 p. 
    Available at www.cid.uz.zgora.pl/php/pdf_file.php?vid=1046 (accessed Jan. 13, 2023).
     
  4. Alvarado J., Dantas S., Mohr E., Rautenbach D. On the maximum number of minimum dominating sets in forests // Discrete Math. 2018. Vol. 342, No. 4. P. 934–942.
     
  5. Taletskii D. S. Trees with extremal numbers of $k$-dominating sets // Discrete
    Math. 2022. Vol. 345, No. 1, ID 112656. 5 p.
     
  6. Rote G. Minimal dominating sets in a tree: Counting, enumeration, and extremal results. Ithaca, NY: Cornell Univ., 2019. (Cornell Univ. Libr. e-Print Archive; arXiv:1903.04517).
     
  7. Henning M. A., Mohr E., Rautenbach D. On the maximum number of minimum total dominating sets in forests // Discrete Math. Theor. Comput. Sci. 2019. Vol. 21, No. 3, ID 3. 12 p.

Исследование выполнено при поддержке Российского научного фонда (проект № 21–11–00194).

Талецкий Дмитрий Сергеевич
  1. Национальный исследовательский университет «Высшая школа экономики»,
    ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
  2. Нижегородский гос. университет им. Н. И. Лобачевского,
    пр. Гагарина, 23, 603950 Нижний Новгород, Россия

E-mail: dmitalmail@gmail.com

Статья поступила 16 июня 2022 г.
После доработки — 4 октября 2022 г.
Принята к публикации 6 октября 2022 г.

Abstract:

The minimum total dominating set (MTDS) of a graph is a vertex subset $D$ of minimum cardinality such that every vertex of the graph is adjacent to at least one vertex of $D$. In this paper we obtain the sharp upper bound for the number of MTDS in the class of $n$-vertex 2-caterpillars. We also show that for all $n \ge 1$ every $n$-vertex tree has less than $(\sqrt{2})^n$ MTDS. 
Illustr. 5, bibliogr. 6.

References:
  1. D. Bród and Z. Skupien, Trees with extremal numbers of dominating sets, Australas. J. Comb. 35, 273–290 (2006).
     
  2. M. Krzywkowski and S. Wagner, Graphs with few total dominating sets, Discrete Math. 341 (4), 997–1009 (2018).
     
  3. A. Bien, Properties of gamma graphs of trees, Colourings, Independence and Domination (Abs. 17th Workshop Graph Theory, Piechowice, Poland, Sept. 17–22, 2017) (Univ. Zielona Góra, Zielona Góra, 2017). 
    Available at www.cid.uz.zgora.pl/php/pdf_file.php?vid=1046 (accessed Jan. 13, 2023).
     
  4. J. Alvarado, S. Dantas, E. Mohr, and D. Rautenbach, On the maximum number of minimum dominating sets in forests, Discrete Math. 342 (4), 934–942 (2018).
     
  5. D. S. Taletskii, Trees with extremal numbers of $k$-dominating sets, Discrete Math. 345 (1), ID 112656, 5 p. (2022).
     
  6. G. Rote, Minimal dominating sets in a tree: Counting, enumeration, and extremal results (Cornell Univ., Ithaca, NY, 2019) (Cornell Univ. Libr. e-Print Archive, arXiv:1903.04517).
     
  7. M. A. Henning, E. Mohr, and D. Rautenbach, On the maximum number of minimum total dominating sets in forests, Discrete Math. Theor. Comput. Sci. 21 (3), ID 3, 12 p. (2019).