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 $\operatorname{eq}(G)$, studied by Alon, is the minimum number of equivalence subgraphs needed to cover all edges of $G$. King conjectured that $\operatorname{eq}(C_n^k)=Ω(k)$ for sufficiently large $n$ relative to $k$. We study $\operatorname{eq}(C_n^k)$ and prove that, for every $n \geq 2k + 2$, we have $1 + \lceil\log_2(k+1)\rceil \leq \operatorname{eq}(C_n^k) \leq 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*}…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.15635
curl -X POST /api/v1/records/arxiv/2610.15635/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.15635/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'