Covering powers of cycles with equivalence subgraphs

Abstract

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)=\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*}