|
О количестве $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$-доминирующее независимое множество, планарный граф.
Статья поступила: 04.05.2023 Переработанный вариант: 03.07.2023 Принята к публикации: 22.09.2023
Образец цитирования:
Д. С. Талецкий, “О количестве $k$-доминирующих независимых множеств в планарных графах”, Дискретн. анализ и исслед. опер., 31:1 (2024), 109–128; J. Appl. Industr. Math., 18:1 (2024), 167–178
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1341 https://www.mathnet.ru/rus/da/v31/i1/p109
|
Статистика просмотров: |
Страница аннотации: | 28 | PDF полного текста: | 1 | Список литературы: | 9 | Первая страница: | 4 |
|