0
$\begingroup$

By a graph, I mean a simple, undirected graph with no loops. A graph homomorphism $f : G \to H$ is a function from the vertexset of $G$ to the vertexset of $H$ such that if $u$ and $v$ are adjacent vertices in $G$, then $f(u)$ and $f(v)$ are adjacent vertices in $H$. A graph is said to be a core if all its endomorphisms are in fact automorphisms.

A vertex $v$ of a graph $G$ is said to be dismantlable if there is another vertex $w$ whose neighbourhood contains the neighbourhood of $v$. A graph with no dismantlable vertices is said to be stiff.

Every core is stiff. Indeed, if $v$ is a dismantlable vertex of $G$, so that there is some vertex $w \neq v$ with $N(w) \supseteq N(v)$, then the endomap $f : G \to G$ given by $$f(u) = \begin{cases} w, & \text{if } u = v; \\ u, &\text{if } u \neq v, \end{cases}$$
is a graph homomorphism that is not surjective. Thus each core cannot have any dismantable vertices, and hence is stiff by definition.

My question is regarding the converse. Are there stiff graphs that are not cores?

$\endgroup$
2
  • 2
    $\begingroup$ Isn't a bi-infinite path an example? $\endgroup$
    – Wojowu
    Commented Sep 8 at 11:49
  • 5
    $\begingroup$ For a finite graph, how about a 6-cycle? $\endgroup$ Commented Sep 8 at 11:54

1 Answer 1

0
$\begingroup$

These answers is due to Wojowu and Anthony Quas respectively.

An infinite stiff graph that is not a core is a bi-infinite path, with vertex set $\mathbb{Z}$ and edge set $\{\{x, x+1\} \in \binom{\mathbb{Z}}{2} : \, x \in \mathbb{Z}\}$. It admits an endomorphism $x \mapsto x \bmod 2$, which is not surjective and hence not an automorphism.

A finite stiff graph that is not a core is the 6-cycle $C_6$. It has chromatic number $2$ and so admits an endomorphism $x \mapsto x \bmod 2$ that is not surjective and hence not an automorphism.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .