A coalition in graph $G = (V(G), E(G))$ is a pair of two non-dominating disjoint sets $V_1 \subseteq V(G)$ and $V_2 \subseteq V(G)$, whose union $V_1 \cup V_2$ is a dominating set of $G$. A coalition partition in a graph $G$ is a vertex partition $\pi = (V_1, V_2, \ldots, V_k)$ such that every set $V_i \in \pi$ either is a dominating set consisting of a single (full) vertex, or is not a dominating set but forms a coalition with another non-dominating set $V_j \in \pi$. A coalition graph of graph $G$ with respect to the coalition partition $\pi$ is a graph $CG(G, \pi)$, the vertices of which correspond one-to-one with the sets $V_1, V_2, \ldots, V_k$ of $\pi$ and two vertices are adjacent in $CG(G, \pi)$ if their corresponding sets in $\pi$ form a coalition. In this paper we characterize the coalition graphs of paths and cycles. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely which they are.
|
