Papers
arxiv:2610.08478

Regular K_3-Irregular Graphs of Every Regularity at Least Nine

Published on Oct 6
Authors:

Abstract

Regular triangle-distinct graphs exist for all regularities r ≥ 9 via explicit constructions using antiregular blocks, matrix switches, and discriminant analysis.

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 rge 9. More precisely, for every integer kge 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 kge 17 and even kge 62 are handled symbolically, while the remaining 24 values are settled by exact finite verification. Together with the known examples for 9le rle 29, this closes the positive existence problem for every rge 9.

Community

Sign up or log in to comment

Get this paper in your agent:

hf papers read 2610.08478
Don't have the latest CLI?
curl -LsSf https://hf.co/cli/install.sh | bash

Models citing this paper 0

No model linking this paper

Cite arxiv.org/abs/2610.08478 in a model README.md to link it from this page.

Datasets citing this paper 0

No dataset linking this paper

Cite arxiv.org/abs/2610.08478 in a dataset README.md to link it from this page.

Spaces citing this paper 0

No Space linking this paper

Cite arxiv.org/abs/2610.08478 in a Space README.md to link it from this page.

Collections including this paper 0

No Collection including this paper

Add this paper to a collection to link it from this page.