Skip to main content
used MathJax instead of \textbf for text formatting
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

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.1300v1arXiv: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""Almost all Steiner triple systems are asymmetric" in Topics on Steiner systems. \textsl{Ann. Discrete Math.} \textbf{7} 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"Homomorphisms of strongly regular graphs" (arXiv:1601.00969arXiv: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"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.

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. \textsl{Ann. Discrete Math.} \textbf{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.

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.

Source Link
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

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. \textsl{Ann. Discrete Math.} \textbf{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.