no. 10 · Friday 6 November 2026
On rigid regular graphs and a problem of Babai and Pultr
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