Доминирующие множества с окрестностью для деревьев (2025)
Выпуск:
Т. 32, № 1 (2025)
Подмножество образует -доминирующее множество графа G, если для любой вершины найдется вершина такая, что длина кратчайшей цепи, соединяющей эти вершины; — число вершин в минимальном -доминирующем множестве; при; для числа, вычисление является NP-полной задачей. В работе рассматривается класс деревьев диаметра, степени внутренних вершин которых равны. Приводятся конструктивные описания деревьев. Разработаны процедуры вычисления значений в диапазоне. Установлены асимптотические оценки для и их доли от общего числа вершин деревьев при. Приводятся вычислительные примеры.