Largest edge set compatible with graph endomorphisms

Question

Let $V$ be a set and let $V^V$ denote the set of all functions $f:V\to V$. Suppose that $F\subseteq V^V$. Let $[V]^2 = \big\{\{x,y\}: x, y\in V \land x\neq y\big\}$. We say $E\subseteq [V]^2$ is $F$-compatible if all members of $F$ are graph homomorphisms from $(V,E)$ to itself.

Suppose $G=(V,E)$ is a simple, undirected graph. With $\text{Hom}(G,G)$ we denote the set of all graph homomorphisms $f:V\to V$.

This post says that there is a largest $\text{Hom}(G,G)$-compatible set $E'\subseteq [V]^2$. Clearly $E'\supseteq E$.

Question. Do we have $E'=E$?

Answer 1

No. In this paper the define the hull of a graph $G$. The hull of $G$ has the same vertices of $G$ and has an edge between any pair of vertices that cannot be identified by any endomorphism of $G$. In other words, two vertices $x$ and $y$ of $G$ are adjacent in the hull of $G$ if and only if $f(x) \ne f(y)$ for all endomorphisms $f$ of $G$. In the same paper they show (and it is not difficult to see) that a graph is a core (has no homomorphism to a proper subgraph) if and only if its hull is a complete graph. Since it is known that almost all graphs are cores, this means that almost all graphs have complete hulls and thus $E' \ne E$.

If $E' = E$, then any pair of non-adjacent vertices can be identified by some endomorphism. This implies (but is not equivalent to) that the core of the graph (smallest subgraph the whole graph admits a homomorphism to) is a complete graph (which is equivalent to the clique and chromatic numbers of the graph being equal). Examples where $E' = E$ would include graphs that are transitive on non-edges and have a clique number equal to chromatic number. More specifically, the Paley graphs of square order have this property.

Answer 2

In general: if $u,v\in V$ are such that $f(u)\neq f(v)$ for all $f\in F=\mathop{\mathrm{Hom}}(G,G)$ then we may add to $E'$ the edge $(u,v)$ along with all its homomorphic images. So $E'$ is merely the set of all such edges $(u,v)$.

Specifically, for a chain $a-b-c-d$ the vertices $a$ and $d$ can never map to one vertex. Thus $(a,d)$ will be in $E'$.

A bit more generally, it seems that for a bipartite connected graph $G$ with parts $A$ and $B$ the set $E'$ will consist of all edges between $A$ and $B$.