Skip to content
DraconiticResearch
Search Sources API
197,357 studies31 sourcesUpdated 37 min ago
PreprintarXiv licencearXiv

Extremal graphs with cycle lengths in a fixed residue class

  • Takahiro Ueoro
Open at sourcePDFDOICite

Abstract

For integers k≥3 and 0≤ ℓ<k, we call a graph (ℓbmod k)-cycle-restricted if every cycle has length congruent to ℓ 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 (0bmod k)-cycle-restricted graph and characterized the graphs attaining equality. In this paper, we determine the maximum number of edges in a $2$-connected (ℓbmod k)-cycle-restricted graph for every ℓ ≠ 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.

Related

  1. Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
    Zejun Huang, Chenxi Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The edge spectral extremal problem for kK3 in nonzero residue classes
    Jing Gao, Shuchao Li, Yuantian Yu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Minimising the harmonic sum of cycle lengths
    Richard Montgomery, Aleksa Milojević, Alexey Pokrovskiy +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The edge spectral extremal problem for odd wheels in nonzero residue classes
    Honghao Chen, Jing Gao, Shuchao Li
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. The Erdős-Gallai bound for consecutive even cycle lengths
    Yaobin Chen, Hong Liu, Xia Wang +2
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ueoro2026extremal,
  title = {{Extremal graphs with cycle lengths in a fixed residue class}},
  author = {Takahiro Ueoro},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15151},
  eprint = {2610.15151},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15151},
}
RIS
TY  - UNPB
TI  - Extremal graphs with cycle lengths in a fixed residue class
AU  - Takahiro Ueoro
PY  - 2026
DA  - 2026/10/10
PB  - arXiv
DO  - 10.48550/arxiv.2610.15151
UR  - https://arxiv.org/abs/2610.15151
AB  - For integers k≥3 and 0≤ ℓ<k, we call a graph (ℓbmod k)-cycle-restricted if every cycle has length congruent to ℓ 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 (0bmod k)-cycle-restricted graph and characterized the graphs attaining equality. In this paper, we determine the maximum number of edges in a $2$-connected (ℓbmod k)-cycle-restricted graph for every ℓ ≠ 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.
ER  -