On rigid regular graphs and a problem of Babai and Pultr
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality