On the Coalition Number of the dth Power of the n-Cycle

A coalition in a graph G consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set but whose union V1∪V2 is a dominating set. A coalition partition in a graph G is a vertex partition π={V1,V2,…,Vk} such that every set Vi∈π is not a dominating set but forms a coalition with another set Vj∈π which is not a dominating set. The coalition number C(G) equals the maximum k of a coalition partition of G. In this paper, we study the coalition number of the dth power of the n-cycle Cnd, where n≥3 and d≥2. We show that C(Cnd)=d2+3d+2 for n=2d2+4d+2 or n≥2d2+5d+3, and also provide some bounds of C(Cnd) for the other cases. As a special case, we obtain the exact value of the coalition number of Cn2.