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

Дискретный анализ и исследование операций. 2023. Т. 30. № 1. С. 110–129.

Талецкий Д. С.

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

Ключевые слова: Экстремальная комбинаторика, дерево, extremal combinatorics, Tree, 2-caterpillar, minimum total dominating set, 2-гусеница, наименьшее полное доминирующее множество