Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 57 min ago
PreprintarXiv licencearXiv

There is no $8$-regular K3-irregular graph

  • Artem Hak
  • Sergiy Kozerenko
  • Andrii Serdiuk
Open at sourcePDFDOICite

Abstract

A graph is K3-irregular if its vertices belong to pairwise distinct numbers of triangles. We prove that no $8$-regular K3-irregular graph exists, settling the last unresolved case. Following the initial discovery of such graphs for regularities r ∈ {10,11,12} (Stevanović et al., 2024), our previous work (Hak et al., 2025) showed that no such graphs exist for r ≤ 7, provided the first example for r=9, and proved that any $8$-regular candidate must have between $17$ and $22$ vertices. We exclude these possible orders for r=8 by combining careful analysis of triangle degrees with integer linear programming techniques. Meanwhile, a recent construction (Zhang, 2026) established that regular K3-irregular graphs do exist for all r ≥ 9. Together with our results, this establishes that an r-regular K3-irregular graph exists if and only if r≥ 9.

Related

  1. There are only finitely many irregular Diophantine quadruples
    Bo He, Alain Togbe
    arXivPreprintCC BY-NC-ND 4.0Full textGeometry & topologyarXiv
  2. Regular K3-Irregular Graphs of Every Regularity at Least Nine
    Zhanhe Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Coherent configuration on 3-uniform hypergraph over strongly regular graph
    Fajri Maulana
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. An Induced Subgraph Paradigm for Strongly Regular Graph Constructions
    Benjamin Baker
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Every r-regular Hamiltonian graph with r≥ 17 contains a second Hamilton cycle
    Haiyang Liu, Xu Liu, Bo Ning
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hak2026there,
  title = {{There is no $8$-regular $K_3$-irregular graph}},
  author = {Artem Hak and Sergiy Kozerenko and Andrii Serdiuk},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.37978},
  eprint = {2609.37978},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.37978},
}
RIS
TY  - UNPB
TI  - There is no $8$-regular K_3-irregular graph
AU  - Artem Hak
AU  - Sergiy Kozerenko
AU  - Andrii Serdiuk
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.37978
UR  - https://arxiv.org/abs/2609.37978
AB  - A graph is K_3-irregular if its vertices belong to pairwise distinct numbers of triangles. We prove that no $8$-regular K_3-irregular graph exists, settling the last unresolved case. Following the initial discovery of such graphs for regularities r ∈ {10,11,12} (Stevanović et al., 2024), our previous work (Hak et al., 2025) showed that no such graphs exist for r ≤ 7, provided the first example for r=9, and proved that any $8$-regular candidate must have between $17$ and $22$ vertices. We exclude these possible orders for r=8 by combining careful analysis of triangle degrees with integer linear programming techniques. Meanwhile, a recent construction (Zhang, 2026) established that regular K_3-irregular graphs do exist for all r ≥ 9. Together with our results, this establishes that an r-regular K_3-irregular graph exists if and only if r≥ 9.
ER  -