On rigid regular graphs and a problem of Babai and Pultr

arXiv:2502.11421 · math.CO, cs.DM · Submitted 2025-02-17 · Read on arXiv

math.CO, cs.DM

Submitted: 2025-02-17

Updated: 2026-11-05

Comments: 34 pages, 13 figures, journal (revised) version

Journal ref: European Journal of Combinatorics 140 (2027) 104466

DOI: 10.1016/j.ejc.2026.104466

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: A graph is rigid if it only admits the identity endomorphism.

Terminology

Abstract

A graph is rigid if it only admits the identity endomorphism. We show that for every d at least 3 there exist infinitely many mutually rigid d-regular graphs of arbitrary odd girth g at least 7. Moreover, we determine the minimum order of a rigid d-regular graph for every d at least 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].

Related papers