Abstract: A coalition in a graph G is a pair of disjoint nondominating subsets of its vertices V1,V2 ⊂ V(G) such that V1 ∪ V2 is a dominating set. In the coalition partition π(G) = {V1,V2,...,Vk}, every nondominating set Vi is included in some coalition and if Vi is dominating, then it is a single-vertex set. A coalition partition of vertices of a graph G generates a coalition graph CG(G,π) whose vertices correspond to the partition sets, while two vertices are adjacent if the corresponding sets form a coalition. It is well known that all simple cycles of order greater than three generate in total 26 coalition graphs of order at most six. A universal cycle generates all such graphs. It is shown that only the cycles C3k, k ≥ 5, are universal.

Cite: Glebov A.N. , Dobrynin A.A.
Universal Cycles That Generate All Graphs of CoalitionPartitions in Cycles
Journal of Applied and Industrial Mathematics. 2025. V.19. N1. P.33-39. DOI: 10.1134/s199047892501003x Scopus РИНЦ OpenAlex

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

Dates:

Submitted:	Jul 11, 2024
Accepted:	Sep 22, 2024
Published print:	Nov 2, 2025
Published online:	Nov 2, 2025

Identifiers:

Scopus:	2-s2.0-105020663527
Elibrary:	83155448
OpenAlex:	W4415775055

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

Altmetrics: