Том 30, номер 1, 2023 г., Стр. 110-129

УДК 519.17
Талецкий Д. С.
О количестве наименьших полных доминирующих множеств в деревьях

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

Ключевые слова:

DOI: 10.33048/daio.2023.30.745

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

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

Литература

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

© Д. С. Талецкий, 2023