A simple, undirected graph $G = (V,E)$ is said to be *strongly rigid* if the identity is the only [graph endomorphism](https://en.wikipedia.org/wiki/Graph_homomorphism).


For which positive integers $k>2$ is there a strongly rigid $k$-[regular](https://en.wikipedia.org/wiki/Graph_homomorphism) graph?



Strongly rigid regular graphs
Let $X(\mathcal{S)}$ be the block graph of a Steiner triple system $\mathcal{S}$ on $v$ points. The triple system consists of $b=v(v-1)/6$ triples from a set $V$ of size $v$ such that each pair of points from $V$ lies in exactly one triple. Necessarily $v\equiv1,3$ mod 6 and, if this condition holds, triple systems on $v$ points exist. The block graph has the triples of $\mathcal{S}$ as it
vertices, two triples are adjacent if they have exactly one point in common. The block graph is strongly regular.


A coclique in $X(\mathcal{S})$ is given by a set of pairwise disjoint triple, whence
$\alpha(X(\mathcal{S})) =\lfloor v/3\rfloor$. If $v>15$, the cliques of maximum size come from the triple containing a given point, and so 
$\omega(X(\mathcal{S}))=(v-1)/2$. So we see that, if $v\equiv1$ mod 6, then 
$\chi(X(\mathcal{S})) > \omega(X(\mathcal{S}))$.


Now in "Cores of geometric graphs" ([arXiv:0806.1300v1](https://arxiv.org/abs/0806.1300)), Gordon Royle and I prove that every endomorphism of the block graph of a Steiner triple system is either an automorphism, or is a homomorphism to a maximum clique. It follows that if $v\cong1$ mod 6, the block graph of a Steiner triple system has no non-identity endomorphism. 


Finally Babai proved that almost all Steiner triple systems are asymmetric, whence it follows that almost all Steiner triple systems on $v\equiv1$ mod 6 points have no non-identity automorphism. (See L. Babai "[Almost all Steiner triple systems are asymmetric](https://doi.org/10.1016/S0167-5060(08)70169-9)" in Topics on Steiner systems. *Ann. Discrete Math.* **7** (1980), 37–39.) When $v>15$ all cliques of maximum size come from points of $V$ (exercise), when $v>15$ the automorphism group of a triple system and its block graph
are isomorphic.


So we have lots of strongly rigid regular graphs.


In "Homomorphisms of strongly regular graphs" ([arXiv:1601.00969](https://arxiv.org/abs/1601.00969)), David Roberson proves that the core of a strongly regular graph is either the graph itself, or is a complete graph. Hence any strongly regular graph with $\chi>\omega$ must be a core and, if the graph is asymmetric, it will not admit a non-trivial endomorphism.
I suspect that almost all Latin square graphs on a given order are strongly rigid.


There is a second way to potentially produce more examples. In a book somewhere, Gordon Royle and I prove that a triangle-free graph with diameter two and no "twinned vertices" is a core. It follows that is $X$ is connected, triangle-free and asymmetric, it is strongly rigid. Unfortunately no examples come to mind just now.


Finally none of this helps in finding finite cubic graphs with only trivial endomorphisms.


