RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2023, том 30, выпуск 3, страницы 111–131 (Mi da1330)

О деревьях заданного диаметра с экстремальным количеством $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$-дистанционное независимое множество, диаметр.

УДК: 519.17

Статья поступила: 20.10.2022
Переработанный вариант: 02.05.2023
Принята к публикации: 11.05.2023

DOI: 10.33048/daio.2023.30.755



© МИАН, 2024