It is easy to see that [vertex-transitive](https://en.wikipedia.org/wiki/Vertex-transitive_graph) graphs must be [regular](https://en.wikipedia.org/wiki/Regular_graph).


This question looks for regular graphs that are "the opposite" of vertex-transitive.


**Question.** Is there an integer $N\in\mathbb{N}$ such that given an integer $k\geq N$, is there a connected $k$-regular graph $G\_k$ that is strongly rigid (i.e. the only graph homomorphism $f:G\_k\to G\_k$ is the identity)?



Strongly rigid connected $k$-regular graphs
I will use the blocks of Steiner triple systems. Suppose $\mathcal{S}$ is a Steiner triple system on $v$ points. Then $v\cong1,3$ mod 6 and there are $v(v-1)/2$ blocks. The block graph has the blocks of the triple system as its vertices, two are adjacent if they have a point in common. It is
strongly regular.


If a triple system has more than 15 points, the maximum size of a clique in the block graph is $(v-1)/2$, and any clique of the size consists of the triples that contain a given point in the underlying set. The maximum size of a coclique is $\lfloor{v/3}\rfloor$.


If is known that the automorphism group of a triple system on more than 15 points is isomorphic to the automorphism group of its block graph. (This can be proved easily using the above claim re the cliques.) Babai proved that almost all Steiner triple systems are asymmetric.


In <https://arxiv.org/pdf/0806.1300.pdf> it is proved that any endomorphism of the block graph of a Steiner triple system is either an automorphism, or its image is a clique.


Assume that our triple system is asymmetric on $v$ points, where $v\cong1$ mod 6 and $v>15$. If the block admits a non-identity endomorphism, its image must be a clique of size $(v-1)/2$. However the fibres must be cocliques of this endomorphism must have size $v/3$, which is impossible. Hence the only endomorphism of the block graph is the identity.


Remarks: a graph is a pseudocore is its only endomorphisms are automorphisms and colourings. Recently Roberson <https://arxiv.org/pdf/1601.00969.pdf> proved that all strongly regular graphs are pseudocores. So any asymmetric strongly regular graph with chromatic number greater than its clique number is "strongly rigid".


