О количестве независимых и k-доминирующих множеств в графах со средней степенью вершин не более k

Математический сборник. 2023. Т. 214. № 11. С. 133–156.

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

Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа k ⩾ 1, то количество его k-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является k-регулярным. Эта гипотеза доказана для случая k ∈ {1,2}.

Ключевые слова: независимое множество, enumerative combinatorics, dominating set, перечислительная комбинаторика, independent set, k-dominating set, доминирующее множество, k-доминирующее множество

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Исследование графовых и сетевых структур и их приложения (2023)