Д. С. Талецкий, Д. С. Малышев, “Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств”, Дискрет. матем., 2018, том 30, выпуск 4,страницы 115

Эта публикация цитируется в 3 статьях

Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств

Д. С. Талецкий^a, Д. С. Малышев^b

^a Нижегородский государственный университет им. Н. И. Лобачевского
^b Национальный исследовательский университет «Высшая школа экономики»

Аннотация: Для любого $n$ в множестве $n$-вершинных деревьев, в которых любые два листа не имеют общей смежной вершины, полностью описаны деревья с наименьшим количеством максимальных независимых множеств.

Ключевые слова: экстремальная комбинаторика, дерево, максимальное независимое множество.

УДК: 519.172.1

Статья поступила: 04.04.2018
Переработанный вариант поступил: 31.08.2018

DOI: 10.4213/dm1515