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?

| cite | improve this question | | | | |
  • $\begingroup$ It would be interesting whether you already know the answer for any $k\ge 3$? $\endgroup$ – M. Winter Jan 17 '19 at 16:06
  • $\begingroup$ Good point @M.Winter - I don't...! $\endgroup$ – Dominic van der Zypen Jan 17 '19 at 16:54
  • $\begingroup$ Dou you consider only finite graphs, or infinite also are allowed? $\endgroup$ – Taras Banakh Jan 17 '19 at 18:26
  • 4
    $\begingroup$ I bet that random $k$-regular graphs are rigid with probability almost 1, and possibly this is even proved in Bollobas' book. $\endgroup$ – Fedor Petrov Jan 17 '19 at 19:40
  • 4
    $\begingroup$ A homomorphism is a map between two graphs, so it makes no sense to use the word when there is just one graph. Perhaps you mean endomorphism which is a homomorphism from a graph to itself. The distinction is analogous to the distinction between isomorphism (two graphs) and automorphism (one graph). $\endgroup$ – Gordon Royle Jan 17 '19 at 22:53

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.

| cite | improve this answer | | | | |

An infinite family of (strongly?) rigid 3-regular finite graphs can be constructed using the following graph $RC_1$ called the rigid connector: enter image description here

A graph composed of the chain consisting of $n$ rigid connectors will be denoted by $RC_n$: enter image description here

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$:

enter image description here

It is (more-or-less) clear that this graph is rigid.

Is it strongly rigid, too?

| cite | improve this answer | | | | |
  • $\begingroup$ What do you mean with a rigid graph? $\endgroup$ – Wojowu Jan 20 '19 at 20:48
  • $\begingroup$ I think he means no interesting automorphisms. However, I think three edges can collapse in the component, unless vertex loops aren't allowed. Gerhard "What Is A Self-Map Anyway?" Paseman , 2019.01.20. $\endgroup$ – Gerhard Paseman Jan 20 '19 at 21:23
  • 2
    $\begingroup$ Vertex loops should not be allowed otherwise constant maps would be endomorphisms, distinct from the identity. $\endgroup$ – Taras Banakh Jan 20 '19 at 21:30
  • 2
    $\begingroup$ This graph has chromatic number three (Brook's theorem), hence it admits a homomorphism onto any triangle in it. So it is not strongly rigid. (Thus a strongly rigid cubic graph must be triangle-free.) $\endgroup$ – Chris Godsil Jan 21 '19 at 1:41

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.