Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 41 min ago
PreprintarXiv licencearXiv

Regular K3-Irregular Graphs of Every Regularity at Least Nine

  • Zhanhe Zhang
Open at sourcePDFDOICite

Abstract

For a vertex v of a graph G, the triangle-degree tdG(v) is the number of triangles containing v. A graph is triangle-distinct, or K3-irregular, if its vertex triangle-degrees are pairwise distinct. Chartrand, Erdős, and Oellermann asked whether a regular K3-irregular graph exists. We prove that such graphs exist for every regularity r≥ 9. More precisely, for every integer k≥ 15 we construct a 2k-regular triangle-distinct graph on 4k+2 vertices; complementation gives a (2k+1)-regular example of the same order. The construction uses two antiregular threshold blocks joined by a zero-one matrix with prescribed margins, followed by matrix $2$-switches that preserve those margins. After a uniform reference perturbation, exactly three triangle-degree collisions remain. Switches chosen according to parity remove two of them, and the last possible collision is controlled by a short quadratic discriminant argument. Odd k≥ 17 and even k≥ 62 are handled symbolically, while the remaining 24 values are settled by exact finite verification. Together with the known examples for 9≤ r≤ 29, this closes the positive existence problem for every r≥ 9.

Related

  1. Every tournament T of order at least 3 admits infinitely many T-irregular oriented graphs
    Tatiana Dovzhenok
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The integrability of sesqui-regular graphs with smallest eigenvalue at least −3
    Qianqian Yang, Ruo-Lan Ding
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Strongly stable CMC-one hypersurfaces in every hyperbolic space of dimension at least four
    Zihao Wang
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  4. There is no $8$-regular K3-irregular graph
    Artem Hak, Sergiy Kozerenko, Andrii Serdiuk
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Finitely generated groups of diffeomorphisms with prescribed critical regularity in every dimension
    Maximiliano Escayola, Carl-Fredrik Nyberg-Brodda
    arXivPreprintarXiv licenceFull textAlgebra & number theoryDynamical systemsarXiv

Cite

BibTeXRIS
BibTeX
@misc{zhang2026regular,
  title = {{Regular $K_3$-Irregular Graphs of Every Regularity at Least Nine}},
  author = {Zhanhe Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.08478},
  eprint = {2610.08478},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.08478},
}
RIS
TY  - UNPB
TI  - Regular K_3-Irregular Graphs of Every Regularity at Least Nine
AU  - Zhanhe Zhang
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.08478
UR  - https://arxiv.org/abs/2610.08478
AB  - For a vertex v of a graph G, the triangle-degree td_G(v) is the number of triangles containing v. A graph is triangle-distinct, or K_3-irregular, if its vertex triangle-degrees are pairwise distinct. Chartrand, Erdős, and Oellermann asked whether a regular K_3-irregular graph exists. We prove that such graphs exist for every regularity r≥ 9. More precisely, for every integer k≥ 15 we construct a 2k-regular triangle-distinct graph on 4k+2 vertices; complementation gives a (2k+1)-regular example of the same order. The construction uses two antiregular threshold blocks joined by a zero-one matrix with prescribed margins, followed by matrix $2$-switches that preserve those margins. After a uniform reference perturbation, exactly three triangle-degree collisions remain. Switches chosen according to parity remove two of them, and the last possible collision is controlled by a short quadratic discriminant argument. Odd k≥ 17 and even k≥ 62 are handled symbolically, while the remaining 24 values are settled by exact finite verification. Together with the known examples for 9≤ r≤ 29, this closes the positive existence problem for every r≥ 9.
ER  -