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?
$\begingroup$
$\endgroup$
7
asked Jan 17, 2019 at 13:15
-
$\begingroup$ It would be interesting whether you already know the answer for any $k\ge 3$? $\endgroup$– M. WinterCommented Jan 17, 2019 at 16:06
-
$\begingroup$ Good point @M.Winter - I don't...! $\endgroup$– Dominic van der ZypenCommented Jan 17, 2019 at 16:54
-
$\begingroup$ Dou you consider only finite graphs, or infinite also are allowed? $\endgroup$– Taras BanakhCommented Jan 17, 2019 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 PetrovCommented Jan 17, 2019 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 RoyleCommented Jan 17, 2019 at 22:53
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
0
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.
answered Jan 19, 2019 at 2:14
$\begingroup$
$\endgroup$
4
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?
answered Jan 17, 2019 at 18:59
-
$\begingroup$ What do you mean with a rigid graph? $\endgroup$– WojowuCommented Jan 20, 2019 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$ Commented Jan 20, 2019 at 21:23
-
2$\begingroup$ Vertex loops should not be allowed otherwise constant maps would be endomorphisms, distinct from the identity. $\endgroup$ Commented Jan 20, 2019 at 21:30
-
3$\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$ Commented Jan 21, 2019 at 1:41
$\begingroup$
$\endgroup$
In Groups and Monoids of Regular Graphs Hell and Nesetril show that every finite group is isomorphic to the endomorphism monoid of a cubic graph (Thm 4). So this in particular holds for the trivial group. Observing that you can use arbitrarily large gadgets like the one in Fig. 2 of their paper, one can construct infinitely many strongly rigid cubic graphs.
