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

Дискрет. матем., 2020, том 32, выпуск 2, страницы 71–84 (Mi dm1554)

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

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

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

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

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

УДК: 519.176+519.172.1

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

DOI: 10.4213/dm1554


 Англоязычная версия: Discrete Mathematics and Applications, 2021, 31:2, 135–144

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


© МИАН, 2024