Graph with only the identity as endomorphism

409 Views Asked by At

Is there a graph $G$ with more than one vertex such that the identity $\textrm{id}: G\to G$ is the only graph homomorphism from $G$ to itself? Is there even an infinite example?

1

There are 1 best solutions below

0
On

Hell and Nesetril proved that random graphs (edge probability 0.5) are cores.

Lemma 6.9.3 in "Algebraic Graph Theory" by Royle and somebody states that a triangle-free graph of diameter two is a core if and only if no two vertices have the same set of neighbours. So "all" that is needed is to find such a graph that is asymmetric. Note that a triangle-free graph is a spanning subgraph of a triangle-free graph with diameter two, so a computer search might be fruitful.