• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

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

Для любых n и d описана структура деревьев с максимально возможным количеством наибольших независимых множеств в классе n-вершинных деревьев, степень каждой вершины которых не превосходит d. Показано, что при всех чётных n экстремальное дерево единственно, а при нечётных n единственности может и не быть, причём при d = 3 для любого нечётного n > 7 имеется в точности (n−3)%4+ 1 экстремальных деревьев. В данной работе проблема поиска экстремальных (n, d)-деревьев также рассмотрена применительно к 2-гусеницам, т. е. деревьям, в которых каждая вершина отстоит от некоторого простого пути на расстояние не более чем два. В ней для любых n и d ∈ {3, 4} полностью выявляются все экстремальные 2-гусеницы с n вершинами, каждая из которых имеет степень не более чем d.