Regular $K_3$-Irregular Graphs of Every Regularity at Least Nine
For a vertex $v$ of a graph $G$, the triangle-degree $\operatorname{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\ge 9$. More precisely, for every integer $k\ge 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.08478
curl -X POST /api/v1/records/arxiv/2610.08478/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.08478/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'