Изопериметричното неравенство за ребрата на степените на цикличен граф
DOI :
https://doi.org/10.55630/mem.2026.55.078-084Ключови думи :
реброво-изопериметрично неравенство, цикличен графАбстракт
В тази статия се дава пълно решение на определена версия на реброво-изопериметричната задача за степени на циклични графи. По-точно се доказва, че максималният брой ребра в индуциран подграф на C_s^n , породен от множество от k върха, се постига, когато това множество се състои от k последователни върха.
Литература (библиография)
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.
