On transitive Cayley graphs of groups and semigroups (Q1869031): Difference between revisions

The main theme of the paper under review is the study of Cayley graphs of semigroups and proving that they sometimes enjoy properties analogous to those of the Cayley graphs of groups. The Cayley graph Cay\((G,S)\) of \(G\) relative to \(S\) is defined as the graph with vertex set \(G\) and edge set \(E(S)\) consisting of those ordered pairs \((x,y)\) such that \(sx=y\) for some \(s\in S\). Let \(D(V,E)\) be a graph with vertex set \(V\) and edge set \(E\subseteq V\times V\). A mapping \(\phi:V\rightarrow V\) is called an endomorphism of the graph \(D\) if \((u^\phi,v^\phi)\in E\) for all \((u,v)\in E\). An automorphism is an endomorphism that is one-to-one and onto. A subset \(A\) of End\((D)\) is said to be vertex-transitive on \(D\), and \(D\) is said to be \(A\)-vertex-transitive if, for any two vertices \(x,y\in V\), there exists an endomorphism \(\phi\in A\) such that \(x^\phi=y\). A graph \(D(V,E)\) is called vertex-transitive if it is \(\Aut(D)\)-vertex-transitive. Let \(G\) be a semigroup, and let \(S\) be a nonempty subset of \(G\). Denote the automorphism group (endomorphism monoid) of Cay\((G,S)\) by \(\Aut_S(G)\) (respectively, End\(_S(G)\)). Denote by ColAut\(_S(G)\) the set of all colour-preserving automorphisms of Cay\((G,S)\), where an element \(\phi\in\Aut_S(G)\) is called a colour-preserving automorphism if \(sx=y\) implies \(s(x^\phi)=y\), for all \(x,y\in G\) and \(s\in S\). Reminding the well-known and easy to verify fact that, for every group \(G\) and every subset \(S\) of \(G\), all of \(\text{End}_S(G)\), \(\Aut_S(G)\), and \(\text{ColAut}_S(G)\) are vertex-transitive on the Cayley graph \(\text{Cay}(G,S)\), the authors state that their first main theorem (Theorem 2.1) describes all semigroups \(G\) and all subsets \(S\) of \(G\), satisfying a certain finiteness condition, such that the Cayley graph \(\text{Cay}(G,S)\) is \(\text{ColAut}_S(G)\)-vertex-transitive. Theorem 2.1. Let \(G\) be a semigroup, and let \(S\) be a subset of \(G\) which generates a subsemigroup \(\left<S\right>\) such that all principal left ideals of \(\left<S\right>\) are finite. Then, the Cayley graph \(\text{Cay}(G,S)\) is \(\text{ColAut}_S(G)\)-vertex-transitive if and only if the following conditions hold: (i) \(sG=G\), for all \(s\in S\); (ii) \(\left<S\right>\) is isomorphic to a direct product of a right zero band and a group (a semigroup is called a right zero band if it satisfies the identity \(xy=y\)); (iii) ~ \(|\left<S\right>g|\) is independent of the choice of \(g\in G\). The next main result of the paper reduces the problem of describing vertex-transitive Cayley graphs of finite semigroups to the case of completely simple semigroups. The result applies to all semigroups satisfying the same finiteness condition as in Theorem 2.1. Here a semigroup is called completely simple if it has no proper ideals and has an idempotent minimal with respect to the partial order \(e\leq f \Leftrightarrow e=ef=fe\). Theorem 2.2. Let \(G\) be a semigroup, and let \(S\) be a subset of \(G\) such that all principal left ideals of the subsemigroup \(\left<S\right>\) are finite. Then the Cayley graph \(\text{Cay}(G,S)\) is \(\text{Aut}_S(G)\)-vertex-transitive if and only if the following conditions hold: (i) \(SG=G\); (ii) \(\left<S\right>\) is a completely simple semigroup; (iii) the Cayley graph \(\text{Cay}(\langle S\rangle, S)\) is \(\text{Aut}_S(\left<S\right>)\)-vertex-transitive; (iv) ~ \(|\left<S\right>g|\) is independent of the choice of \(g\in G\).