It is easy to see that vertex-transitive graphs must be regular.

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)?


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

  • 1
    $\begingroup$ Bibliographic annotations: firstly, a reference for $v\geq15\Rightarrow\mathrm{Aut}(L(S))\cong\mathrm{Aut}(S)$ is Corollary 1.13 on p. 1456 in Handbook of Combinatorics: Vol. 2, Elsevier, 1995, ISBN 9780444880024. Secondly, a proof of 'almost all Steiner triple systems asymmetric' was published in László Babai, Almost All Steiner Triple Systems Are Asymmetric, Annals of Discrete Mathematics, Volume 7, 1980, Pages 37-39. $\endgroup$ – Peter Heinig Mar 29 '18 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.