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

Матем. заметки, 2024, том 115, выпуск 3, страницы 371–384 (Mi mzm13940)

О 5- и 6-листных деревьях, имеющих наибольшее количество паросочетаний

Н. А. Кузьминab, Д. С. Малышевa

a Национальный исследовательский университет – Высшая школа экономики в Нижнем Новгороде
b Санкт-Петербургский государственный университет

Аннотация: Паросочетанием графа называется любое множество его ребер, попарно не имеющих общих вершин. Важным параметром графов, находящим свое применение в математической химии, является индекс Хосойи, определяемый как количество их паросочетаний. Ранее рассматривались и были полностью решены задачи максимизации этого индекса для $n$-вершинных деревьев c двумя, тремя, четырьмя листьями при любом достаточно большом $n$. В этой работе полностью решается аналогичная задача для 5-листных деревьев при $n\geqslant 20$ и для 6-листных деревьев при $n\geqslant 26$.
Библиография: 19 названий.

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

УДК: 519.17

MSC: 05C70

Поступило: 08.06.2023

DOI: 10.4213/mzm13940


 Англоязычная версия: Mathematical Notes, 2024, 115:3, 341–351

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


© МИАН, 2024