Covering powers of cycles with equivalence subgraphs

Let $C_n^k$ denote the $k$th power of the cycle $C_n$. The equivalence covering number $\mathrm{eq}(G)$, studied by Alon, is the minimum number of equivalence subgraphs needed to cover all edges of $G$. King conjectured that $\mathrm{eq}(C_n^k)=\mathrm{\Omega }(k)$ for sufficiently large $n$ relative to $k$. We study $\mathrm{eq}(C_n^k)$ and prove that, for every $n\ge 2k+2$, we have $1+\lceil {\log }_2(k+1)\rceil \le \mathrm{eq}(C_n^k)\le 1+2\lceil {\log }_2(k+1)\rceil$. We further show that, whenever $n\ge (k+1)\max \{41,5\lceil {\log }_2(k+1)\rceil \}$, \begin{equation*} \operatorname{eq}(C_n^k)\in\left{1+\lceil\log_2(k+1)\rceil,,2+\lceil\log_2(k+1)\rceil\right}. \end{equation*} Moreover, for every integer $n\ge \max \{2k+2,k^2(k+2)\}$, the following exact values hold in the indicated cases: \begin{equation*} \operatorname{eq}(C_n^k)=\begin{cases} 1+\lceil\log_2(k+1)\rceil, & k+1\neq2^{\lceil\log_2(k+1)\rceil} $\text{ or }$(k+1)\mid n,\[3pt] 2+\lceil\log_2(k+1)\rceil, & k+1=2^{\lceil\log_2(k+1)\rceil} $\text{ and }$2\nmid n. \end{cases} \end{equation*}