On transitive Cayley graphs of groups and semigroups
type: Item
instance of: scholarly article
title: On transitive Cayley graphs of groups and semigroups
zbMATH Open document ID: 1011.05027
DOI: 10.1016/S0195-6698(02)00120-8
author: Cheryl E. Praeger
author: A. V. Kelarev
published in: European Journal of Combinatorics
publication date: 2003-04-09T00:00:00Z
review text: 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\) whic…
reviewed by: Alireza Abdollahi
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 1895799
zbMATH Keywords: Cayley graphs of semigroups
zbMATH Keywords: Cayley graphs of groups
zbMATH Keywords: vertex-transitive graphs
zbMATH Keywords: colour-preserving endomorphisms
MaRDI profile type: Publication
Wikidata QID: Q56987912
cites work: Q4871775
cites work: Q4839155
cites work: Q4352273
cites work: Q4846425
cites work: Q4529513
cites work: Q4352275
description: scientific article; zbMATH DE number 1895799