Paperlane

no. 10 · Friday 6 November 2026

On rigid regular graphs and a problem of Babai and Pultr

Kolja Knauer and Gil Puig i Surroca

math.CO · v2 · 34 pp

Abstract

A graph is rigid if it only admits the identity endomorphism. We show that for every $d\ge 3$ there exist infinitely many mutually rigid $d$-regular graphs of arbitrary odd girth $g\geq 7$. Moreover, we determine the minimum order of a rigid $d$-regular graph for every $d\ge 3$. This provides strong positive answers to a question of van der Zypen [https://mathoverflow.net/q/296483, https://mathoverflow.net/q/321108]. Further, we use our construction to show that every finite monoid is isomorphic to the endomorphism monoid of a regular graph. This solves a problem of Babai and Pultr [J. Comb. Theory, Ser. B, 1980].

comments
34 pages, 13 figures, journal (revised) version
journal
European Journal of Combinatorics 140 (2027) 104466
fields
Combinatorics
pdf ↗ page arXiv:2502.11421 ↗