The edge-isoperimetric inequality for powers of cycles
DOI:
https://doi.org/10.55630/mem.2026.55.078-084Keywords:
edge-isoperimetric inequality, cycle graphAbstract
This note provides a complete solution to a certain version of the edge-isoperimetric problem for powers of cycle graphs. Namely, it shows that the maximum number of edges induced by a vertex subset of C_s^n of size k is achieved by a set of k consecutive vertices.
References
Andries E. Brouwer and Willem H. Haemers. Spectra of graphs Springer Science & Business Media, 2011.
F. Chung. Discrete isoperimetric inequalities. In Surveys in Differential Geometry IX, International Press, pages 53–82, 2024.
Nikita A. Dubinin, Elizaveta A. Neustroeva, Andrei M. Raigorodskii, and Yakov K. Shubin. Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph. Matematicheskii Sbornik, 215(5):71–95, 2024.
Tamás Makai, Matija Pasch, Kalina Petrova, and Leon Schiller. Sharp thresholds for higher powers of Hamilton cycles in random graphs. arXiv preprint arXiv:2502.14515, 2025.
