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?


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.

  • $\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$ – Noah Schweber Nov 25 '14 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$ – Dominic van der Zypen Nov 25 '14 at 20:53

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.