2025/07/17 by Hojin Chu, Boram Park, Chu, Hojin +3 · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2507.12798
openalex publication_date 2025/07/17 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
For two integers k and ℓ, an (ℓ mod k)-cycle means a cycle of length m such that m≡ ℓ\pmodk. In 1977, Bollobás proved a conjecture of Burr and Erdős by showing that if ℓ is even or k is odd, then every n-vertex graph containing no (ℓ mod k)-cycles has at most a linear number of edges in terms of n. Since then, determining the exact extremal bounds for graphs without (ℓ mod k)-cycles has emerged as an interesting question in extremal graph theory, though the exact values are known only for a few integers ℓ and k. Recently, Győri, Li, Salia, Tompkins, Varga and Zhu proved that every n-vertex graph containing no (0 mod 4)-cycles has at most \lfloor (19)/(12)(n -1) \rfloor edges, and they provided extremal examples that reach the bound, all of which are not 2-connected. In this paper, we show that a 2-connected graph without (0 mod 4)-cycles has at most \lfloor (3n-1)/(2) \rfloor edges, and this bound is tight by presenting a method to construct infinitely many extremal examples.