PreprintarXiv licencearXiv
Covering powers of cycles with equivalence subgraphs
Abstract
Let Cnk denote the kth power of the cycle Cn. The equivalence covering number eq(G), studied by Alon, is the minimum number of equivalence subgraphs needed to cover all edges of G. King conjectured that eq(Cnk)=Ω(k) for sufficiently large n relative to k. We study eq(Cnk) and prove that, for every n ≥ 2k + 2, we have 1 + ⌈log2(k+1)⌉ ≤ eq(Cnk) ≤ 1 + 2⌈log2(k+1)⌉. We further show that, whenever n≥(k+1)max{41,5⌈log2(k+1)⌉}, eq(Cnk)∈{1+⌈log2(k+1)⌉, 2+⌈log2(k+1)⌉}. Moreover, for every integer n≥ max{2k+2,k2(k+2)}, the following exact values hold in the indicated cases: eq(Cnk)= 1+⌈log2(k+1)⌉, & k+1≠2⌈log2(k+1)⌉ or (k+1)| n, [3pt] 2+⌈log2(k+1)⌉, & k+1=2⌈log2(k+1)⌉ and 2nmid n.
Related
- Structural properties of admissible subgraphs and the depth of symbolic powers of cover ideals
- DEPTH OF POWERS OF EDGE IDEALS OF CYCLES AND STARLIKE TREES
- Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs
- The Last Isolated Vertex in Random-Order Uncovering of Cycles and Their Powers: Exact Enumeration and Weibull Limits
- Homological invariants of Edge Ideals associated to powers of cycles
BibTeX
@misc{yang2026covering,
title = {{Covering powers of cycles with equivalence subgraphs}},
author = {Zhanping Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15635},
eprint = {2610.15635},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15635},
}
RIS
TY - UNPB
TI - Covering powers of cycles with equivalence subgraphs
AU - Zhanping Yang
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15635
UR - https://arxiv.org/abs/2610.15635
AB - Let C_n^k denote the kth power of the cycle C_n. The equivalence covering number eq(G), studied by Alon, is the minimum number of equivalence subgraphs needed to cover all edges of G. King conjectured that eq(C_n^k)=Ω(k) for sufficiently large n relative to k. We study eq(C_n^k) and prove that, for every n ≥ 2k + 2, we have 1 + ⌈log_2(k+1)⌉ ≤ eq(C_n^k) ≤ 1 + 2⌈log_2(k+1)⌉. We further show that, whenever n≥(k+1)max{41,5⌈log_2(k+1)⌉}, eq(C_n^k)∈{1+⌈log_2(k+1)⌉, 2+⌈log_2(k+1)⌉}. Moreover, for every integer n≥ max{2k+2,k^2(k+2)}, the following exact values hold in the indicated cases: eq(C_n^k)= 1+⌈log_2(k+1)⌉, & k+1≠2^⌈log_2(k+1)⌉ or (k+1)| n, [3pt] 2+⌈log_2(k+1)⌉, & k+1=2^⌈log_2(k+1)⌉ and 2nmid n.
ER -