0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Do you insist on using the term 'largest' for 'maximal'? The latter is the usual way to put it in such contexts. I recommend you edit all occurrences of 'largest', also in the linked MO post, to 'maximal', or even to 'inclusion-maximal'. $\endgroup$ – Peter Heinig Sep 22 '17 at 14:43
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.