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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.)
answered Dec 14, 2014 at 17:13
-
$\begingroup$ Is this the book? Graphs and Homomorphisms amazon.com/… $\endgroup$ Commented Dec 14, 2014 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$ Commented Dec 14, 2014 at 23:02