On rigid regular graphs and a problem of Babai and Pultr

Abstract

A graph is rigid if it only admits the identity endomorphism. We determine the minimum number of vertices of a rigid 𝑑 -regular graph for every 𝑑 . This extends results of Baron and Imrich (1969). Two rigid graphs are further mutually rigid if there is no homomorphism from one to the other. We show that for every 𝑑 ≥ 3 there exist infinitely many mutually rigid 𝑑 -regular graphs of arbitrary odd girth 𝑔 ≥ 7 . This provides strong positive answers to a question of van der Zypen from 2018 [ https://mathoverflow.net/q/296483 , https://mathoverflow.net/q/321108 ]. With the above construction as a building block, we show that every finite monoid is isomorphic to the endomorphism monoid of a regular graph. This solves a problem of Babai and Pultr (1980).