Реферат: Коалицией в графе G называется пара непересекающихся и недоминирующих подмножеств его вершин V1, V2 ⊂ V (G) таких, что объединение V1 ∪ V2 является доминирующим множеством. В коалиционном разбиении π(G) = {V1, V2, . . . , Vk} каждое недоминирующее множество Vi входит в некоторую коалицию с другим множеством этого разбиения, а если Vi доминирующее, то оно одновершинное. Коалиционное разбиение вершин графа G порождает граф коалиций CG(G, π), в котором вершины соответствуют множествам разбиения и две вершины смежны, если соответствующие множества образуют коалицию. Известно, что в совокупности все простые циклы порядка более трёх порождают 26 графов коалиций с числом вершин не более шести. Универсальный цикл по- рождает все такие графы. В работе показано, что только циклы C3k при k > 5 универсальны.

Библиографическая ссылка: Глебов А.Н. , Добрынин А.А.
Универсальные циклы, порождающие все графы коалиционных разбиений циклов
Дискретный анализ и исследование операций. 2025. Т.32. №1. С.16–27. DOI: 10.33048/daio.2025.32.807 РИНЦ

Даты:

Поступила в редакцию:	11 июл. 2024 г.
Принята к публикации:	22 сент. 2024 г.
Опубликована в печати:	20 мар. 2025 г.
Опубликована online:	20 мар. 2025 г.

Идентификаторы БД:

РИНЦ:

82904673

Цитирование в БД: Пока нет цитирований

Альметрики: