3
$\begingroup$

Asymmetric graphs are graphs that have a trivial automorphism group $\textrm{Aut}(G)$, i.e. the only graph isomorphism from $G$ to itself is the identity.

Let's call a graph $G$ strongly asymmetric if the only graph homomorphism $h: G\to G$ is the identity (in other words, the endomorphism monoid $\textrm{End}(G)$ is trivial).

Given a (finite or infinite) cardinal $\kappa > 0$, is there a strongly asymmetric graph on $\kappa$ vertices?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

I believe the common name for such graphs is rigid. In fact, most random graphs are rigid. See this reference: On the minimal order of a graphs within a semigroup.

$\endgroup$
2
  • $\begingroup$ A cautionary note: in many contexts, "rigid" is taken to mean merely "no nontrivial automorphisms" e.g. here: arxiv.org/pdf/math/9411236v1.pdf $\endgroup$ Nov 25, 2014 at 17:33
  • $\begingroup$ That's right -- I think the reference given in the answer above might refer to existence of a trivial auto (but not endo) morphism only... I'm not sure we already have an answer for the question whether for any cardinal there is a rigid graph (in the strong sense). $\endgroup$ Nov 25, 2014 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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