Graph with no nontrivial endomorphisms?

Question

For context, I'm trying to determine whether there exists a full and faithful functor $F:\mathsf{Dgr}\to\mathsf{SimpGph}$ that "encodes" directed graphs as simple graphs. Right now I believe that there is no such functor (although I'm not certain), and I'm trying to prove it.

I've noticed that there are lots of nontrivial examples of directed graphs which have no non-identity endomorphisms, such as a directed graph with two vertices and one edge. However, I can't seem to find any such examples of simple graphs, other than the trivial example of the graph with one vertex. If I can show that there is no graph which lacks non-identity endomorphisms, this will allow me to finish my proof: for the fully faithfulness of $F$ would force all endomorphism-less digraphs to be mapped to the graph with one vertex, entailing all sorts of juicy contradictions.

QUESTION: Are there, in fact, any simple graphs with more than one vertex that have no non-identity endomorphisms? I haven't been able to come up with any after playing around for a few days with pencil and paper, and maybe someone can offer a solution/reference/more methodical method of approaching this problem.

Answer 1

The term you are looking for is a "rigid graph". Unfortunately, the same name is also used for a completely unrelated notion in combinatorial rigidity theory. A related notion is an "asymmetric graph", which is a graph with a trivial automorphism group (but it seems to me that some sources use the term rigid graph with this meaning).

I'm not very familiar with this graph family, so I will just link to a couple of papers that might interest you. In this paper it is shown that there is a rigid graph on $n$ vertices if and only if $n \geq 8$. In this paper it is shown that almost all graphs are rigid, i.e. the ratio of the number of rigid graphs on $n$ vertices and the number of graphs on $n$ vertices tends to one. So the simplest way of constructing a rigid graph might just be to take a large random graph!

Answer 2

Suppose a graph can be decomposed into $10$ stars (a star is a subgraph that consists of one central vertex, and every other vertex connects to the central vertex but no other vertex in the subgraph). The first star has $10$ “points” or leaves (i.e. $10$ noncentral vertices), the second has $11$, and so on.

An endomorphism has to preserve adjacency, and thus degree. Each central vertex is thus distinct (in case it's not clear, “distinct” here means “must be fixed under any endomorphism”). Each star as a whole is also distinct, but we still need more work to make the leaves distinct. Suppose for each leaf, we choose $5$ of the other stars to connect to (leaves connect to other leaves, so there's no ambiguity what star a leaf is in). There are $9$ other stars, so we have ${9 \choose 5}= 126$ possibilities, so that's more than enough to distinguish even the leaves of the $19$ point star.

Each vertex is either a central vertex, in which case it's distinguished solely by which star it is in, or it is a leaf, in which case it is characterized by what star it is in, and what other stars it connects to. That is, within a particular star, no two vertices connect to the same set of stars (two leaves can connect to the same set of stars, but only if they are in different stars). Since a leaf has degree of at most $6$ (it connects to its center and $5$ other stars), it is easily distinguished from the central vertices that have degree of at least $10$.