4
$\begingroup$

Is it known what fraction (almost all?) of graphs have a trivial endomorphism monoid? I can't seem to find any reference to the question. Maybe it's related to the question: what fraction of graphs have chromatic number equal to their clique number?

$\endgroup$
11
$\begingroup$

The book "Graph Homomorphisms" contains an elegant proof that a random graph admits only the identity endomorphism.

The term to search on is "rigid graph". (This has two different meanings but they are easy to distinguish.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is this the book? Graphs and Homomorphisms amazon.com/… $\endgroup$ – CoffeeCat Dec 14 '14 at 17:58
  • $\begingroup$ Yes, that's it. I also think that if you google a bit you might find some notes online giving the proof. $\endgroup$ – Chris Godsil Dec 14 '14 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy