## Generalized Cayley graphs of semigroups. I.(English)Zbl 1252.20052

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 A. Kelarev, J. Ryan and J. Yearwood, [Discrete Math. 309, No. 17, 5360-5369 (2009; Zbl 1206.05050)] and Section 2.4 of the book by 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.

### MSC:

 20M05 Free semigroups, generators and relations, word problems 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C20 Directed graphs (digraphs), tournaments 20M20 Semigroups of transformations, relations, partitions, etc.

### Citations:

Zbl 1206.05050; Zbl 1070.68097
Full Text:

### References:

  Arworn, Sr., Knauer, U., Chiangmai, N.N.: Characterization of digraphs of right (left) zero unions of groups. Thai J. Math. 1(1), 131–140 (2003) · Zbl 1055.05075  Dénes, J.: Connections between transformation semigroups and graphs. In: Theory of Graphs. Gordon & Breach, New York (1967)  Howie, J.M.: Fundamentals of Semigroup Theory. Clarendon, Oxford (1995) · Zbl 0835.20077  Kelarev, A.V.: Graph Algebras and Automata. Dekker, New York (2003) · Zbl 1070.68097  Kelarev, A.V.: On Cayley graphs of inverse semigroups. Semigroup Forum 72, 411–418 (2006) · Zbl 1107.20057  Kelarev, A.V.: On undirected Cayley graphs. Australas. J. Combin. 25, 73–78 (2002) · Zbl 0993.05085  Kelarev, A.V., Praeger, C.E.: On transitive Cayley graphs of groups and semigroups. Eur. J. Comb. 24(1), 59–72 (2003) · Zbl 1011.05027  Kelarev, A.V., Quinn, S.J.: A combinatorial property and Cayley graphs of semigroups. Semigroup Forum 66, 89–96 (2003) · Zbl 1016.20047  Kelarev, A.V., Quinn, S.J.: A combinatorial property and power graphs of semigroups. Comment. Math. Univ. Carol. 45(1), 1–7 (2004) · Zbl 1099.05042  Kelarev, A.V., Quinn, S.J.: Directed graphs and combinatorial properties of semigroups. J. Algebra 251(1), 16–26 (2002) · Zbl 1005.20043  Kelarev, A., Ryan, J., Yearwood, J.: Cayley graphs as classifiers for data mining: The influence of asymmetries. Discrete Math. 309, 5360–5369 (2009) · Zbl 1206.05050  Panma, S., Knauer, U., Arworn, S.: On transitive Cayley graphs of right (left) groups and of Clifford semigroups. Thai J. Math. 2(1), 183–195 (2004) · Zbl 1063.05068  Panma, S., Knauer, U., Arworn, S.: On transitive Cayley graphs of strong semilattices of right (left) groups. Discrete Math. 309(17), 5393–5403 (2009) · Zbl 1198.05095  Panma, S., Chiangmai, N.N., Knauer, U., Arworn, S.: Characterizations of Clifford semigroup digraphs. Discrete Math. 306(12), 1247–1252 (2006) · Zbl 1096.05045  Petrich, M., Reilly, N.: Completely Regular Semigroups. Wiley, New York (1999) · Zbl 0967.20034  White, A.T.: Graphs, Groups and Surfaces. Amsterdam, Elsevier (2001) · Zbl 1054.05001  Wilson, R.J.: Introduction to Graph Theory, 3rd edn. Longman, New York (1982) · Zbl 0489.03017  Yang, D., Gao, X.: D-saturated property of the Cayley graphs of semigroups. Semigroup Forum 80, 174–180 (2010) · Zbl 1198.20046  Zelinka, B.: Graphs of semigroups. Čas. Pěst. Mat. 106, 407–408 (1981) · Zbl 0479.05033  Zhu, Y.: On (n,m)-semigroups. Semigroup Forum (2011). doi: 10.1007/s00233-011-9360-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.