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

Математические заметки. 2023. Т. 113. № 4. С. 577–595.

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

Рассматривается класс деревьев, степень каждой вершины которых не превосходит целого числа d. Показано, что при d=4 каждое n-вершинное дерево из этого класса содержит не более (√2)^n наименьших доминирующих множеств (НДМ), и описана структура деревьев, содержащих ровно (√2)^n НДМ. С другой стороны, при d=5 для каждого n≥1 построено n-вершинное дерево, содержащее более (1/3)⋅1.415^n НДМ. Кроме того, показано, что каждое n-вершинное дерево содержит менее 1.4205^n НДМ.

Ключевые слова: dominating set, дерево, Tree, minimum dominating set, доминирующее множество, наименьшее доминирующее множеств