Abstract:
A 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.