Generalized Cayley graphs of semigroups. I. (Q415542)

The study of Cayley graphs of semigroups and its valuable applications, is a very important research area which is closely related to finite state automata (see the survey by \textit{A. Kelarev, J. Ryan} and \textit{J. Yearwood}, [Discrete Math. 309, No. 17, 5360-5369 (2009; Zbl 1206.05050)] and Section 2.4 of the book by \textit{A. Kelarev}, [Graph algebras and automata. New York: Marcel Dekker (2003; Zbl 1070.68097)]). In this paper, the author first presents the following definition of generalized Cayley graphs of semigroups to unify the Cayley graphs of semigroups defined by right translations and left translations (note that the classical definition of Cayley graphs has no problem and the difference between the results about Cayley graphs defined by left and right actions, is because of the close relation between semigroups and these structures (similar to left and right \(S\)-acts)). Let \(T\) be an ideal extension of a semigroup \(S\) and \(\rho\subseteq T^1\times T^1\). The `generalized Cayley graph' \(\text{Cay}(S,\rho)\) of \(S\) relative to \(\rho\) is defined as the graph with vertex set \(S\) and edge set \(E(\text{Cay}(S,\rho))\) consisting of those ordered pairs \((a,b)\), where \(xay=b\) for some \((x,y)\in\rho\). The generalized Cayley graph \(\text{Cay}(S,\omega)\), where \(\omega=S^1\times S^1\) is called `universal Cayley graph of \(S\)'. Clearly, for \(\rho_1=T^1\times \{1\}\) and \(\rho_2=\{1\}\times T^1\), \(\text{Cay}(S,\rho_1)\) and \(\text{Cay}(S,\rho_2)\) are the classical definition of Cayley graph of semigroup defined by left and right transformations, respectively. After presenting some fundamental properties and general results about generalized Cayley graphs of semigroups, the author focuses on universal Cayley graphs and after introducing some notions, she describes the universal Cayley graph of a \(\mathcal J\)-partial order of complete graphs with loops.