On undirected Cayley graphs
Andrei V. Kelarev · 2002
We determine all periodic (and, therefore, all finite) semigroups G for which there exists a non-empty subset S of G such that the Cayley graph of G relative to S is an undirected Cayley graph. Let G be a semigroup, and let S be a nonempty subset of G. TheCayley graph Cay(G, S) ofG 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 ∈ S. Cayley graphs of groups are significant both in group theory and in constructions of interesting graphs with nice properties. They have received serious attention in the literature (see, in particular, [1], [2], [5]). The Cayley graph of a semigroup has been introduced by Bohdan Zelinka [9]. In the investigation of the Cayley graphs of semigroups it is first of all interesting to find the analogues of natural conditions which have been used in the group case. For example, it is well known that the Cayley graph Cay(G, S) of a group G is symmetric or undirected if and only if S = S−1. A graph D =(V,E) issaidtobe