Эта публикация цитируется в
3 статьях
О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств
Д. С. Талецкийa,
Д. С. Малышевba a Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950 Нижний Новгород, Россия
b Национальный исследовательский университет «Высшая школа экономики», ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
Аннотация:
Для любых
$n$ и
$d$ описана структура деревьев с максимально возможным количеством наибольших независимых множеств в классе
$n$-вершинных деревьев, степень каждой вершины которых не превосходит
$d$. Показано, что при всех чётных
$n$ экстремальное дерево единственно, а при нечётных
$n$ единственности может и не быть, причём при
$d=3$ для любого нечётного
$n\geq7$ имеется в точности
$\lceil\frac{n-3}4\rceil+1$ экстремальных деревьев. В данной работе проблема поиска экстремальных
$(n,d)$-также рассмотрена применительно к 2-гусеницам, т.е. деревьям, в которых каждая вершина отстоит от некоторого простого пути на расстояние не более чем два. В ней для любых
$n$ и
$d\in\{3,4\}$ полностью выявляются все экстремальные
$2$-гусеницы с
$n$ вершинами, каждая из которых имеет степень не более чем
$d$. Ил. 9, библиогр. 10.
Ключевые слова:
экстремальная комбинаторика, дерево, наибольшее независимое множество.
УДК:
519.17 Статья поступила: 29.09.2017
DOI:
10.17377/daio.2018.25.591