On monoid graphs

If $s,t\in S$, $c\in C$ and $(t,tc)$ is an arc of $\mathrm{Cay}_{\mathrm{col}}(S,C)$ having color $c$, then $(st,stc)$ is also an arc of $\mathrm{Cay}_{\mathrm{col}}(S,C)$ having color $c$. Thus, left-multiplication $\varphi_{s}$ with $s$ is an element of $\mathrm{End}(\mathrm{Cay}_{\mathrm{col}}(S,C))$. Clearly, $\varphi_{st}=\varphi_{s}\circ\varphi_{t}$, so this is a semigroup homomorphism. $\square$

Suppose that there is a vertex $e$ and a submonoid $M\leq\mathrm{End}(G)$ satisfying this property. Let $C=\{\varphi\in M\ |\ (e,\varphi(e))\in A\}$. We claim that there is an isomorphism $G\cong\mathrm{Cay}(M,C)$ given by $x\mapsto\varphi_{x}$. It is clear that this map is injective. It is also surjective: the preimage of $\varphi\in M$ is $\varphi(e)$. Now, if $(x,y)\in A$, there is an out-neighbor $c$ of $e$ with $\varphi_{x}\circ\varphi_{c}(e)=\varphi_{x}(c)=y$; thus $\varphi_{x}\circ\varphi_{c}=\varphi_{y}$. Since $\varphi_{c}\in C$, $(\varphi_{x},\varphi_{y})$ is an arc of $\mathrm{Cay}(M,C)$. Conversely, if $(\varphi_{x},\varphi_{y})$ is an arc of $\mathrm{Cay}(M,C)$ then $\varphi_{x}\circ\varphi=\varphi_{y}$ for some $\varphi\in C$. This implies that the arc $(e,\varphi(e))\in A$ is mapped by $\varphi_{x}$ to $(x,\varphi_{x}\circ\varphi(e))=(x,y)$, which must be also in $A$, because $\varphi_{x}$ is an endomorphism.

Conversely, suppose that $G=\mathrm{Cay}(M,C)$ for a monoid $M$ and $C\subseteq M$. For each vertex $x$ consider the endomorphism $\varphi_{x}$ of $G$ defined by left-multiplication by $x$. All these endomorphisms together form a submonoid $M^{\prime}\leq\mathrm{End}(\mathrm{Cay}_{\mathrm{col}}(M,C))\leq\mathrm{End}(G)$, by Lemma 2.1. Let $e$ be the neutral element of $M$. It is clear that for any vertex $x$, the mapping $\varphi_{x}$ is the only of them that maps $e$ to $x$. Moreover, for any out-neighbor $y$ of $x$ there is an out-neighbor $c\in C$ of $e$ with $xc=y$, so $\varphi_{x}(c)=y$. $\square$

For any $s\in S$ and any $X\subseteq S$ with $XC\subseteq X$ we have that $sXC\subseteq sX$. In particular, $sS$ has no outgoing arcs. Hence if $sS\subsetneq S$, then there is a directed edge cut defined by the arcs from $S\setminus sS$ to $sS$. Thus, strong connectivity yields $sS=S$. By Lemma 2.1 and the fact that $S$ is finite, left-multiplication by $s$ is an automorphism of $G$. This means that $S$ is left cancellative. $\square$

By Observation 3.1, if $G=(V,A)$ is a monoid digraph, then $G=\mathrm{Cay}(M,\{a\})$ for some monoid $M$ and $a\in M$. Let $k$ and $h$ be the pre-period and the period of $a$, respectively. This is, $e,a,...,a^{k+h-1}$ are pairwise distinct and $a^{k+h}=a^{k}$. Hence, the component $\mathcal{C}$ containing $a$ satisfies $z(\mathcal{C})=h$ and $\ell(\mathcal{C})\geq k$. Now let $\mathcal{D}$ be any component of $G$, $x\in\mathcal{D}$ at distance $p=\ell(\mathcal{D})$ from the cycle of $\mathcal{D}$, and $q=z(\mathcal{D})$. If $q$ does not divide $h$, then $k$ and $k+h$ are not congruent modulo $q$ and thus $xa^{k}\neq xa^{k+h}$, a contradiction. Hence $z(\mathcal{D})$ divides $z(\mathcal{C})$. Now suppose $p\geq k+1$. Then $xa^{k}$ is distinct from $xa^{l}$ for each $l\neq k$, but this is also a contradiction. Hence $p\leq k\leq\ell(\mathcal{C})$.

Now suppose that the condition is fulfilled. For $x,y\in V$ denote by $d(x,y)$ the length of the shortest directed path from $x$ to $y$, if it exists. Moreover, for $x\in\mathcal{D}$ denote $z(x):=z(\mathcal{D})$. In $\mathcal{C}$ choose a vertex at distance $\ell(\mathcal{C})$ from the cycle $Z\subseteq\mathcal{C}$. Conveniently call this vertex $e$ and call its out-neighbor $a$. For any vertex $x\in V$ and any $k\in\mathbb{N}$, define $x+k$ as the end vertex of the directed walk of length $k$ starting at $x$. It is clear that for any $k,\ell\in\mathbb{N}$ the vertices $x+k,x+\ell$ are equal if and only if $d(x,x+k)=d(x,x+\ell)$.

Now, let $\omega=e+(\ell(\mathcal{C})+z(\mathcal{C})-1)$. Observe that $\omega\in Z\subseteq\mathcal{C}$. Therefore $\omega$ can be reached from any vertex $v$ of $\mathcal{C}$, so we can set $r(v):=d(e,\omega)-d(v,\omega)$. Note that we have $d(v,\omega)=d(e+r(v),\omega)$. This implies that $d(v+k,\omega)=d(e+r(v)+k,\omega)$ for any $k\in\mathbb{N}$, so $r(v+k)=r(e+r(v)+k)=d(e,e+r(v)+k)$ for any $k\in\mathbb{N}$. We regard the vertices of $G$ as the elements of a monoid $M$ equipped with the following multiplication:

By definition, $e$ is the right-neutral element, but also $xe=x+r(e)=x$. Hence $e$ is the neutral element of this operation. Let us check that the operation is associative. Pick any $x,y,z\in V$. If $y\notin\mathcal{C}$, then $yz\notin\mathcal{C}$ and $(xy)z=yz=x(yz)$. If $z\notin\mathcal{C}$ then $(xy)z=z=x(yz)$. So suppose $y,z\in\mathcal{C}$. Then using the above Claim we can transform, $(xy)z=(x+r(y))+r(z)=x+d(x,x+r(y)+r(z))=x+d(x,x+d(e,e+r(y)+r(z)))=x+d(e,e+r(y)+r(z))=x+r(y+r(z))=x+r(yz)=x(yz)$. Finally, note that $(x,y)$ is an arc of $G$ if and only if $y=x+1=xa$. Therefore, $G=\mathrm{Cay}(M,\{a\})$. $\square$

Again by Observation 3.1 we can suppose that $G=\mathrm{Cay}(S,\{a\})$ for a semigroup $S$ and $a\in S$. Let $\mathcal{C}$ be the connected component of $a$ and $S^{\prime}$ the monoid obtained from $S$ by adjoining a neutral element $e$. We can establish a bijective correspondence $\mathcal{D}\mapsto\mathcal{D}^{\prime}$ between connected components of $G$ and $\mathrm{Cay}(S^{\prime},\{a\})$ as follows: $\mathcal{D}^{\prime}=\mathcal{D}$ if $\mathcal{D}\neq\mathcal{C}$, and $\mathcal{C}^{\prime}$ is obtained from $\mathcal{C}$ by adding the vertex $e$ and the arc $(e,a)$. Observe that $z(\mathcal{C}^{\prime})=z(\mathcal{C})$ and $\ell(\mathcal{C}^{\prime})\leq\ell(\mathcal{C})+1$. By Theorem 3.2, $z(\mathcal{D})\mid z(\mathcal{C})$ and $\ell(\mathcal{D})\leq\ell(\mathcal{C})+1$ for any connected component $\mathcal{D}$ of $G$.

Now suppose that $G=(V,A)$ fulfills the condition. Pick a vertex $v$ in $\mathcal{C}$ with $\ell(v)=\ell(\mathcal{C})$, and from $G$ construct a new $1$-outregular graph $G^{\prime}$ by adding a new vertex $u$ and the arc $(u,v)$. By Theorem 3.2, $G^{\prime}$ is isomorphic to $\mathrm{Cay}(M,\{a\})$ for some monoid $M$ and some $a\in M$. It follows from its proof that $u$ can be assumed to be the neutral element $e$ and $v$ to be $a$. Additionally, since $e$ has no in-neighbors, it can be checked that $M\setminus\{e\}$ is closed under the constructed product. Therefore, it is a semigroup, and $G$ is isomorphic to $\mathrm{Cay}(M\!\setminus\!\{e\},\{a\})$. $\square$

Given two positive integers $k,\ell$, let $G_{k,\ell}$ be the directed graph with vertex set $\{(0,j)\in\mathbb{Z}^{2}\ |\ 0\leq j\leq k^{2}-1\}\cup\{(i,j)\in\mathbb{Z}^{2}\ |\ 1\leq i\leq\ell-1,\,0\leq j\leq k-1\}$ which has an arc from $(i_{1},j_{1})$ to $(i_{2},j_{2})$ if and only if $i_{1}+1=i_{2}$ or alternatively $i_{1}=\ell-1$, $i_{2}=0$ and $j_{1}=\left\lfloor\frac{j_{2}}{k}\right\rfloor$. Given a positive integer $\kappa$, let $\sim_{\kappa}$ be an equivalence relation on $\{(0,j)\in\mathbb{Z}^{2}\ |\ 0\leq j\leq k^{2}-1\}$ defined as $(0,j_{1})\sim_{\kappa}(0,j_{2})$ if and only if the following conditions are satisfied:

• (i)

  $j_{1}\equiv j_{2}\mod k$;

• (ii)

  $\left\lfloor\frac{j_{1}}{k\kappa}\right\rfloor=\left\lfloor\frac{j_{2}}{k\kappa}\right\rfloor$, or $\kappa\nmid k$ and $\left\lfloor\frac{j_{1}}{k\kappa}\right\rfloor+1=\left\lfloor\frac{j_{2}}{k\kappa}\right\rfloor=\left\lfloor\frac{k^{2}-1}{k\kappa}\right\rfloor$ (or the symmetric condition).

We call $G_{k,\ell,\kappa}$ the directed graph obtained from $G_{k,\ell}$ by merging all vertices of each $\sim_{\kappa}$-class. See Figure 2 for an illustration.

Note that for $\ell\geq 2$ the digraph $G_{k,\ell,\kappa}$ is $k$-outregular and strongly connected. Denote by $V_{i}$ the set of vertices of $G_{k,\ell,\kappa}$ with first coordinate congruent to $i$ modulo $\ell$ if $\ell\nmid i$, and the set of $\sim_{\kappa}$-classes if $\ell\mid i$. In particular, $|V_{0}|=\left\lfloor\frac{k}{\kappa}\right\rfloor k$ and $|V_{1}|=...|V_{\ell-1}|=k$. Assume that $\left\lfloor\frac{k}{\kappa}\right\rfloor>1$ and $\ell\geq 4$.

It is clear that $G_{k,\ell,\kappa}$ is not strongly $(\kappa+1)$-connected: for instance, all in-neighbors of any vertex of $V_{0}$ form a directed vertex cut. Now let $X$ be a minimal directed vertex cut. Suppose that there is a vertex $x\in X\cap V_{i}$ with $i\not\equiv-1\mod\ell$. Then since $|X|\leq\kappa<k$ there is in $V_{i}\setminus X$ a vertex with the same in-neighbors and out-neighbors as $x$, so $X\setminus\{x\}$ is also a directed vertex cut, a contradiction. Therefore $X\subseteq V_{-1}$. Hence there must be a vertex in $V_{0}$ with all in-neighbors in $X$, or $X$ would not be a directed vertex cut. This implies that $|X|=\kappa$.

Moreover the underlying undirected graph of $G_{k,\ell,\kappa}$ is $(k+\kappa)$-connected. First note that $V_{1}\cup Y$, where $Y$ is the set of in-neighbors of a vertex of $V_{0}$, is a vertex cut. Now let $X$ be a minimal vertex cut; it is clear that $V_{i}\subseteq X$ for some $i$. This $i$ is unique (modulo $\ell$); more precisely, it is the only index satisfying $|X\cap V_{i}|\geq k$. Suppose that there is a vertex $x\in X\cap V_{j}$ with $j\not\equiv-1,i\mod\ell$. Then there is a vertex in $V_{j}\setminus X$ with the same neighbors as $x$, so $X\setminus\{x\}$ is also a vertex cut, a contradiction. Therefore $X\subseteq V_{-1}\cup V_{i}$. Since $\ell\geq 3$ it is clear that $V_{-1},V_{0}\neq V_{i}$. Moreover, since $\ell\geq 4$ there is a vertex $y\in V_{0}\setminus X$ with all its in-neighbors in $X$. This implies that $k+\kappa\leq|V_{i}|+|Y|\leq|X|\leq k+\kappa$, where $Y$ is the set of in-neighbors of $y$.

We will now show that:

• (a)

  under the assumed hypotheses on $k,\ell,\kappa$, $G_{k,\ell,\kappa}$ is not a semigroup digraph;

• (b)

  if additionally $\left\lfloor\frac{k}{\kappa}\right\rfloor>2+\frac{1}{k}$, then there is no semigroup $S$ and $C\subseteq S$ for which $G_{k,\ell,\kappa}=\mathrm{Cay}^{\mathrlap{\circlearrowleft}\,\setminus}(S,C)$, where $\mathrm{Cay}^{\mathrlap{\circlearrowleft}\,\setminus}(S,C)$ denotes the graph obtained from $\mathrm{Cay}(S,C)$ by removing all loops.

In both cases a hypothetical representation with a semigroup $S$ and a connection set $C$ leads to a contradiction. Indeed, let $x\in S$ and $X\subseteq S$. By Lemma 2.5 $S$ is left cancellative, so $|xX|=|X|$. Now suppose that $x\notin V_{-2}$ and let $y\in V_{-2}$. We have $k=|xC^{2}|=|C^{2}|=|yC^{2}|=\left\lfloor\frac{k}{\kappa}\right\rfloor k$ if there is a semigroup representation in case (a) and $2k+1\geq|xC^{2}|=|C^{2}|=|yC^{2}|\geq\left\lfloor\frac{k}{\kappa}\right\rfloor k$ if there is a semigroup representation in case (b), the desired contradictions. $\square$

Consider the directed graph $G$ from Figure 3 with vertex set $\{x,y,z\}$ and arc set

Suppose that $G=\mathrm{Cay}(S,C)$ for a semigroup $S$ and some $C\subseteq S$. It is clear that there is no $u\in S$ with $ux=y$ or $uz=y$. On the other hand, $\exists c,c^{\prime}\in C\ \,xc=zc^{\prime}=y$. Therefore, $c=c^{\prime}=y\in C$. Now suppose that $y^{2}=x$. Then $yx=xy=y$, a contradiction. Similarly, $y^{2}\neq z$. Hence $y^{2}=y$, but this is also a contradiction, because $y$ is loopless.

Moreover, there is no $k$-outregular non-semigroup digraph with less than three vertices. Since all $0$-outregular digraphs and all $1$-outregular connected digraphs are monoid digraphs (by Theorem 3.2), we only have to worry about $1$-outregular disconnected digraphs and $2$-outregular digraphs. But with less than three vertices there is only one of each kind: the digraph formed by two vertices with a loop each, and the complete digraph with loops of two vertices; and they are respectively isomorphic to $\mathrm{Cay}(\mathbb{Z}_{2},\{0\})$ and $\mathrm{Cay}(\mathbb{Z}_{2},\{0,1\})$, where $\mathbb{Z}_{2}$ is the additive group on the integers modulo $2$. $\square$

Consider the following multiplication $\cdot$ on $M$:

Note that $\textrm{id}\in\langle\mathcal{F}\rangle$ serves as the neutral element of $\cdot$. To see that $\cdot$ is associative, pick any $\alpha,\beta,\gamma\in M$. If $\gamma\in V$, then $(\alpha\cdot\beta)\cdot\gamma=\gamma=\alpha\cdot\gamma=\alpha\cdot(\beta\cdot\gamma)$. Thus, let $\gamma\in\langle\mathcal{F}\rangle$. In the case $\beta\in V$ we have $(\alpha\cdot\beta)\cdot\gamma=\gamma(\beta)=\alpha\cdot\gamma(\beta)=\alpha\cdot(\beta\cdot\gamma)$; in the case $\alpha\in V$, $\beta\in\langle\mathcal{F}\rangle$ we have $(\alpha\cdot\beta)\cdot\gamma=\gamma(\beta(\alpha))=\alpha\cdot(\gamma\circ\beta)=\alpha\cdot(\beta\cdot\gamma)$; and the case $\alpha,\beta\in\mathcal{\langle}\mathcal{F}\rangle$ is trivial. Let $H=\mathrm{Cay}(M,\mathcal{F})$. It is clear that the subgraph $H[\langle\mathcal{F}\rangle]$ induced by $\langle\mathcal{F}\rangle$ is a connected component of $H$, and it coincides with $H_{\textrm{id}}$. The subgraph $H[V]$ induced by $V$ is formed by the rest of the connected components, and by the hypotheses on $\mathcal{F}$, it is isomorphic to $G$. $\square$

One can greedily cover the arcs of $G$ by $k$ spanning $1$-outregular subdigraphs: to construct the $i$th such digraph $G_{i}$ simply take any vertex $x$ that has not yet outdegree $1$ in $G_{i}$, add any not yet covered arc $(x,y)$ to $G_{i}$ or an already covered one $(x,y)$ if all are covered, and iterate.

Now each $G_{i}$ yields a function $f_{i}$ that just maps every vertex $x$ to its out-neighbor $y$ in $G_{i}$. The resulting set $\mathcal{F}$ has order $k$ and Proposition 3.8 yields the result. $\square$

Since $C\subseteq N(e)$ all we have to show is that every edge $\{v,w\}$ of $\underline{\mathrm{Cay}}(M,N(e))$ is an edge of $G$. Suppose that $w=vx$ for some $x\in N(e)\setminus C$. Then $xc=e$ for some $c\in C$. This implies that $\{v,w\}$ is also an edge of $G$, because $wc=vxc=v$. $\square$

Let $M$ be a monoid and $C\subseteq M$ with $G=\underline{\mathrm{Cay}}(M,C)$. Define a monoid structure on $M^{\prime}=V\cup\{x\}$ using the multiplication from $M$ whenever possible, and defining $xv=vx=x^{2}=x$ for every $v\in V$. This new multiplication preserves the neutral element from $M$, and it is also associative: let $u,v,w\in M^{\prime}$ and suppose than at least one of them is equal to $x$; then, $(uv)w=x=u(vw)$. It is straightforward to check that $G^{\prime}=\underline{\mathrm{Cay}}(M^{\prime},C)$ and $G^{\prime\prime}=\underline{\mathrm{Cay}}(M^{\prime},C\cup\{x\})$. $\square$

Let $F$ be any forest. Pick in each component $\mathcal{C}$ an arbitrary vertex $v$. Direct all edges of $\mathcal{C}$ towards $v$ and add a loop at $v$. Clearly, the resulting digraph satisfies the hypothesis of Theorem 3.2: every component $\mathcal{C}$ has $z(\mathcal{C})=1$, and some of them maximize $\ell(\mathcal{C})$. $\square$

Assume for a contradiction that $\underline{\mathrm{Cay}}(M,C)=K_{4}\cup C_{\ell}$ for some monoid $M$ and $C\subseteq M$. Denote by $\overrightarrow{K_{4}}$, $\overrightarrow{C_{\ell}}$ the corresponding components of $\mathrm{Cay}(M,C)$, that are directed graphs with possible loops and anti-parallel arcs. Since $\ell$ is odd, there are two consecutive arcs in $\overrightarrow{C_{\ell}}$. Hence, there is a vertex $u$ and $c,c^{\prime}\in C$ such that the vertices $u,uc,ucc^{\prime}$ are all different. If the neutral element $e$ is in $K_{4}$, then $e,cc^{\prime}$ are either neighbors or the same vertex. But then $u,ucc^{\prime}$ should also be neighbors or the same vertex, a contradiction.

Therefore $e$ must be in $C_{\ell}$. Hence by Lemma 4.1 we can suppose that $C=\{c,c^{\prime}\}$ with $c\neq c^{\prime}$. The periods of $c,c^{\prime}$ can only be $1$, $2$ or $\ell$, so by Theorem 3.2 both $\underline{\mathrm{Cay}}(M,\{c\})$ and $\underline{\mathrm{Cay}}(M,\{c^{\prime}\})$ are pseudoforests without cycles of length $3$ or $4$. Then each element of $C$ corresponds to at most $3$ non-loop arcs of $\overrightarrow{K_{4}}$, and it must correspond to exactly $3$, because $K_{4}$ has $6$ edges; moreover, none of the edges of $K_{4}$ correspond to both $c,c^{\prime}$. Therefore, if we group the edges of $K_{4}$ depending on whether they come from $c$ or from $c^{\prime}$, we obtain two edge-disjoint copies of the path $P_{4}$. We now distinguish two cases.

If there is an edge in $C_{\ell}$ corresponding to both $c,c^{\prime}$, any endomorphism mapping $e$ to a vertex of $K_{4}$ implies the existence of a loop in $\overrightarrow{K_{4}}$. Lemma 2.4 guarantees the existence of such an endomorphism.

If otherwise every edge in $C_{\ell}$ corresponds to either $c$ or $c^{\prime}$, since $\ell$ is odd then there is a loop in $\overrightarrow{C_{\ell}}$. Thus, by Lemma 2.4 there is a loop in $\overrightarrow{K_{4}}$. We can suppose that this loop corresponds to $c$. Let $x$ be the vertex of the loop. Wherever $x$ lies along the $c$-copy of $P_{4}$, it implies there are vertices $v\neq w$, different from $x$, such that $vc=w,wc=x$. This implies that $e,c,c^{2}$ are all different. We know that $cc^{\prime}\in\{e,c,c^{2}\}$, so $xc^{\prime}=(xc)c^{\prime}=x(cc^{\prime})=x$, and there cannot be more loops in $\overrightarrow{K_{4}}$. Now, $wc^{\prime}=vcc^{\prime}\in\{v,w,x\}$, but that is a contradiction. $\square$