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

Cite: Глебов А.Н. , Добрынин А.А.
Универсальные циклы, порождающие все графы коалиционных разбиений циклов
Дискретный анализ и исследование операций. 2025. Т.32. №1. С.16–27.

Dates:

Submitted:	Jul 11, 2024
Accepted:	Sep 22, 2024
Published print:	Mar 20, 2025
Published online:	Mar 20, 2025

Identifiers: No identifiers

Citing: Пока нет цитирований