Реферат: Коалицией в графе 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.

Даты:

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

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

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