|
Деревья с заданным числом листьев и максимально возможным количеством наибольших независимых множеств
Д. С. Талецкийa, Д. С. Малышевb a Нижегородский государственный университет им. Н. И. Лобачевского
b Государственный университет «Высшая школа экономики», Нижегородский филиал
Аннотация:
В работе полностью описаны деревья с максимально возможным количеством наибольших независимых множеств среди всех $n$-вершинных деревьев, содержащих ровно $l$ листьев. При любых значениях параметров $n$ и $l$ экстремальное дерево единственно. Оно является результатом отождествления концов $l$ простых путей.
Ключевые слова:
независимое множество, наибольшее независимое множество, экстремальное дерево.
Статья поступила: 06.12.2018 Переработанный вариант поступил: 14.05.2020
Образец цитирования:
Д. С. Талецкий, Д. С. Малышев, “Деревья с заданным числом листьев и максимально возможным количеством наибольших независимых множеств”, Дискрет. матем., 32:2 (2020), 71–84; Discrete Math. Appl., 31:2 (2021), 135–144
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1554https://doi.org/10.4213/dm1554 https://www.mathnet.ru/rus/dm/v32/i2/p71
|
Статистика просмотров: |
Страница аннотации: | 323 | PDF полного текста: | 127 | Список литературы: | 41 | Первая страница: | 20 |
|