The smallest number of vertices for a graph with the same endomorphism monoid Let $G$ be a directed graph without loop and suppose that $M$ is its endomorphism monoid.
First how we can create a simple graph $\Gamma$ (using $G$), with the same endomorphism monoid? and then how we can create it with the smallest possible number of vertices?
Thanks for your help 
 A: Here's a not terribly efficient method that at least shows that this is possible.  Start by replacing each directed edge by a path of length $4$ with a triangle over the second edge of the path.

These special marker triangles will be the only triangles in the new graph, so this construction almost works.  The problem is that in some cases you can't tell from the new graph where the original vertices were, which can be fixed by attaching a path of the same suitably large length to each of the original vertices.  Probably length $1$ (i.e. a pendant edge) is sufficient.
By hanging things off the third vertex of the triangle, this construction can be extended to encode directed graphs with labelled edges, which can be used to show that every group is the automorphism group of some graph.
EDIT: I now think you probably have to work a bit harder to get something that works for endomorphisms rather than automorphisms.  For example, the long paths I suggested using as vertex tags can be folded any old how onto the rest of the graph, and conceivably you can wrap edges around marker triangles.  I'm sure there's something you can do with your bare hands, but you'll need to be a little more careful than I was.
A: These kinds of results are considered in the paper http://onlinelibrary.wiley.com/doi/10.1002/jgt.20396/epdf
