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

Дискретн. анализ и исслед. опер., 2024, том 31, выпуск 1, страницы 109–128 (Mi da1341)

О количестве $k$-доминирующих независимых множеств в планарных графах

Д. С. Талецкийab

a Национальный исследовательский университет «Высшая школа экономики», ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
b Санкт-Петербургский гос. университет, Университетская наб., 7/9, 199034 Санкт-Петербург, Россия

Аннотация: Множество $J_k$ вершин графа называется $k$-доминирующим независимым ($k \geq 1$), если его вершины попарно не смежны и каждая вершина не из $J_k$ смежна хотя бы с $k$ вершинами из $J_k.$ В этой статье получены новые оценки количества $k$-доминирующих независимых множеств при различных значениях $k \geq 2$ в некоторых классах планарных графов. Ил. 7, библиогр. 15.

Ключевые слова: независимое множество, доминирующее множество, $k$-доминирующее независимое множество, планарный граф.

УДК: 519.17

Статья поступила: 04.05.2023
Переработанный вариант: 03.07.2023
Принята к публикации: 22.09.2023

DOI: 10.33048/daio.2024.31.770


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2024, 18:1, 167–178


© МИАН, 2024