Extremal graphs with cycle lengths in a fixed residue class

Abstract

For integers $k\ge 3$ and $0\le \ell <k$, we call a graph $(\ell \mathrm{mod}k)$-cycle-restricted if every cycle has length congruent to $\ell$ modulo $k$. Akbari, Jamaali, Mahmoody, and Seyed Fakhari [On the size of graphs whose cycles have length divisible by a fixed integer, Australas. J. Combin. 45 (2009), 67--72] determined the maximum number of edges in a $2$-connected $(0\mathrm{mod}k)$-cycle-restricted graph and characterized the graphs attaining equality. In this paper, we determine the maximum number of edges in a $2$-connected $(\ell \mathrm{mod}k)$-cycle-restricted graph for every $\ell \ne 0$, and completely characterize all graphs attaining equality. Combined with the result of Akbari et al., our result gives a complete solution for all residue classes modulo $k$.

arXiv comment9 pages