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.


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.
Full Text: DOI


[1] 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
[2] Dénes, J.: Connections between transformation semigroups and graphs. In: Theory of Graphs. Gordon & Breach, New York (1967)
[3] Howie, J.M.: Fundamentals of Semigroup Theory. Clarendon, Oxford (1995) · Zbl 0835.20077
[4] Kelarev, A.V.: Graph Algebras and Automata. Dekker, New York (2003) · Zbl 1070.68097
[5] Kelarev, A.V.: On Cayley graphs of inverse semigroups. Semigroup Forum 72, 411–418 (2006) · Zbl 1107.20057
[6] Kelarev, A.V.: On undirected Cayley graphs. Australas. J. Combin. 25, 73–78 (2002) · Zbl 0993.05085
[7] 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
[8] Kelarev, A.V., Quinn, S.J.: A combinatorial property and Cayley graphs of semigroups. Semigroup Forum 66, 89–96 (2003) · Zbl 1016.20047
[9] 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
[10] Kelarev, A.V., Quinn, S.J.: Directed graphs and combinatorial properties of semigroups. J. Algebra 251(1), 16–26 (2002) · Zbl 1005.20043
[11] 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
[12] 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
[13] 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
[14] Panma, S., Chiangmai, N.N., Knauer, U., Arworn, S.: Characterizations of Clifford semigroup digraphs. Discrete Math. 306(12), 1247–1252 (2006) · Zbl 1096.05045
[15] Petrich, M., Reilly, N.: Completely Regular Semigroups. Wiley, New York (1999) · Zbl 0967.20034
[16] White, A.T.: Graphs, Groups and Surfaces. Amsterdam, Elsevier (2001) · Zbl 1054.05001
[17] Wilson, R.J.: Introduction to Graph Theory, 3rd edn. Longman, New York (1982) · Zbl 0489.03017
[18] Yang, D., Gao, X.: D-saturated property of the Cayley graphs of semigroups. Semigroup Forum 80, 174–180 (2010) · Zbl 1198.20046
[19] Zelinka, B.: Graphs of semigroups. Čas. Pěst. Mat. 106, 407–408 (1981) · Zbl 0479.05033
[20] 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.