Universal Cycles That Generate All Graphs of CoalitionPartitions in Cycles

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.