A simple, undirected graph $G = (V,E)$ is said to be strongly rigid if the identity is the only graph endomorphism.
For which positive integers $k>2$ is there a strongly rigid $k$-regular graph?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityA simple, undirected graph $G = (V,E)$ is said to be strongly rigid if the identity is the only graph endomorphism.
For which positive integers $k>2$ is there a strongly rigid $k$-regular graph?
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), 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" 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), 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.
An infinite family of (strongly?) rigid 3-regular finite graphs can be constructed using the following graph $RC_1$ called the rigid connector:
A graph composed of the chain consisting of $n$ rigid connectors will be denoted by $RC_n$:
Finally, the required rigid 3-regular graph consists of 3 parallel chains $RC_k$, $RC_n$, $RC_m$ for pairwise distinct numbers $k,n,m$:
It is (more-or-less) clear that this graph is rigid.
Is it strongly rigid, too?