RUS  ENG
Полная версия
ЖУРНАЛЫ // Математический сборник // Архив

Матем. сб., 2023, том 214, номер 11, страницы 133–156 (Mi sm9870)

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

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

Лаборатория алгоритмов и технологий анализа сетевых структур, Национальный исследовательский университет "Высшая школа экономики", г. Нижний Новгород

Аннотация: Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа $k \geqslant 1$, то количество его $k$-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является $k$-регулярным. Эта гипотеза доказана для случая $k \in \{1,2\}$.
Библиография: 10 названий.

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

MSC: 05C30

Поступила в редакцию: 22.12.2022 и 20.06.2023

DOI: 10.4213/sm9870


 Англоязычная версия: Sbornik: Mathematics, 2023, 214:11, 1627–1650

Реферативные базы данных:


© МИАН, 2024