|
О деревьях заданного диаметра с экстремальным количеством $k$-дистанционных независимых множеств
Д. С. Талецкийab a Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печерская, 25/12, 603155 Нижний Новгород, Россия
b Нижегородский гос. университет им. Н. И. Лобачевского, пр. Гагарина, 23, 603950 Нижний Новгород, Россия
Аннотация:
Множество вершин графа называется $k$-дистанционным независимым, если расстояние между любыми двумя его вершинами больше некоторого целого числа $k \geq 1.$ В работе рассматривается задача описания $n$-вершинных деревьев фиксированного диаметра $d,$ содержащих максимально и минимально возможное число $k$-дистанционных независимых множеств среди всех таких деревьев. Задача на максимум решается для случая $1 < k < d \leq 5$ при всех достаточно больших значениях $n.$ Задача на минимум существенно более простая и решается для всех значений параметров $1 < k < d < n.$ Ил. 4, библиогр. 10.
Ключевые слова:
дерево, независимое множество, $k$-дистанционное независимое множество, диаметр.
Статья поступила: 20.10.2022 Переработанный вариант: 02.05.2023 Принята к публикации: 11.05.2023
Образец цитирования:
Д. С. Талецкий, “О деревьях заданного диаметра с экстремальным количеством $k$-дистанционных независимых множеств”, Дискретн. анализ и исслед. опер., 30:3 (2023), 111–131
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1330 https://www.mathnet.ru/rus/da/v30/i3/p111
|
|