Regular -Irregular Graphs of Every Regularity at Least Nine
En palabras de los autores
For a vertex of a graph , the triangle-degree is the number of triangles containing . A graph is triangle-distinct, or -irregular, if its vertex triangle-degrees are pairwise distinct. Chartrand, Erd\H{o}s, and Oellermann asked whether a regular -irregular graph exists. We prove that such graphs exist for every regularity . More precisely, for every integer we construct a -regular triangle-distinct graph on vertices; complementation gives a -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 -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 and even are handled symbolically, while the remaining 24 values are settled by exact finite verification. Together with the known examples for , this closes the positive existence problem for every .
Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 19 pages