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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Noah Schweber
    Commented 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$
    – Dominic van der Zypen
    Commented Nov 25, 2014 at 20:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .