Lamsade

On rigid regular graphs and a problem of Babai and Pultr

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...