Отправить статью по E-mail О количестве независимых и $k$-доминирующих множеств в графах со средней степенью вершин не более $k$
- Авторы: Талецкий Д.С.1
-
Учреждения:
- Национальный исследовательский университет – Высшая школа экономики в Нижнем Новгороде
- Выпуск: Том 214, № 11 (2023)
- Страницы: 133-156
- Раздел: Статьи
- URL: https://journal-vniispk.ru/0368-8666/article/view/147925
- DOI: https://doi.org/10.4213/sm9870
- ID: 147925
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа $k \geqslant 1$, то количество его $k$-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является $k$-регулярным. Эта гипотеза доказана для случая $k \in \{1,2\}$.Библиография: 10 названий.
Об авторах
Дмитрий Сергеевич Талецкий
Национальный исследовательский университет – Высшая школа экономики в Нижнем Новгороде
Автор, ответственный за переписку.
Email: math-net2025_06@mi-ras.ru
кандидат физико-математических наук, младший научный сотрудник
Список литературы
- H. Prodinger, R. F. Tichy, “Fibonacci numbers of graphs”, Fibonacci Quart., 20:1 (1982), 16–21
- C. Heuberger, S. G. Wagner, “Maximizing the number of independent subsets over trees with bounded degree”, J. Graph Theory, 58:1 (2008), 49–68
- N. Alon, “Independent sets in regular graphs and sum-free subsets of finite groups”, Israel J. Math., 73:2 (1991), 247–256
- A. A. Sapozhenko, “Independent sets in quasi-regular graphs”, European J. Combin., 27:7 (2006), 1206–1210
- J. Kahn, “An entropy approach to the hard-core model on bipartite graphs”, Combin. Probab. Comput., 10:3 (2001), 219–238
- Yufei Zhao, “The number of independent sets in a regular graph”, Combin. Probab. Comput., 19:2 (2009), 315–320
- А. Б. Дайняк, А. А. Сапоженко, “Независимые множества в графах”, Дискрет. матем., 28:1 (2016), 44–77
- D. Brod, Z. Skupien, “Trees with extremal numbers of dominating sets”, Australas. J. Combin., 35 (2006), 273–290
- S. Wagner, “A note on the number of dominating sets of a graph”, Util. Math., 92 (2013), 25–31
- D. S. Taletskii, “Trees with extremal numbers of $k$-dominating sets”, Discrete Math., 345:1 (2022), 112656, 5 pp.
Дополнительные файлы
