OpenAlex ·
There is no $8$-regular $K_3$-irregular graph
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.37978
- Original
- Read it at the publisher
- Topics
Abstract
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 \in \{10,11,12\}$ (Stevanović et al., 2024), our previous work (Hak et al., 2025) showed that no such graphs exist for $r \le 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 \ge 9$. Together with our results, this establishes that an $r$-regular $K_3$-irregular graph exists if and only if $r\geq 9$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Resolving Erdős-Ulam Monochromatic Union-Closed Family Conjectures
Toward Pólya and Szegő's conjecture for logarithmic vs Newtonian capacity
Sharp Riesz capacity inequalities and the Pólya--Szegő conjecture
The lattice of varieties of semigroups with completely regular square. II
Non-dyadic Laver algebras
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.