RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2025 Volume 32, Issue 1, Pages 16–27 (Mi da1369)

Universal cycles that generate all graphs of coalition partitions in cycles

A. N. Glebov, A. A. Dobrynin

Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, 630090 Novosibirsk, Russia

Abstract:coalition in a graph $G$ is a pair of disjoint nondominating subsets of its vertices $V_1, V_2 \subset V(G)$ such that $V_1\cup V_2$ is a dominating set. In the coalition partition $\pi(G) = \{V_1,V_2,\dots,V_k\},$ every nondominating set $V_i$ is included in some coalition and if $V_i$ is dominating, then it is a single-vertex set. A coalition partition of vertices of a graph $G$ generates a coalition graph $\text{CG}(G,\pi)$ 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 $C_{3k},$ $k \ge 5,$ are universal. Tab. 4, illustr. 1, bibliogr. 25.

Keywords: graph, dominating set, coalition partition, coalition graph.

UDC: 519.17

Received: 11.07.2024
Revised: 16.08.2024
Accepted: 22.09.2024

DOI: 10.33048/daio.2025.32.807


 English version:
Journal of Applied and Industrial Mathematics, 2025, 19:1, 33–39


© Steklov Math. Inst. of RAS, 2025