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. DOI: 10.33048/daio.2025.32.807 РИНЦ

Dates:

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

Identifiers:

Elibrary:

82904673

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

Altmetrics: