Structures And Properties Of Undirected Cayley Graphs Of Completely Simple Semigroups

The study of symmetric graphs is an active area in graph theory. Their structureshave broad applications in network design and optimization, information science,communications subjects and other fields. Let S be a finite semigroup, and let Abe a subet of S. The (left) Cayley graph Cay (S,A) of S relative to A is definedas the digraph with vertex set S and arcs set consisting of those pairs (x, y)suchthat ax=y for some a∈A. The conditions for Cayley graphs ofseimgroups to beundirected and vertex-transitivity are reduced to the case of completely simplesemigroups. There are two minimal undirected Cayley graphs of completely simpleseimgroups Cay (S, A[a, j]) and Cay (S, A[a,Ï„, j]).This paper aims at the structures and properties of the minimal undirectedCayley graph Cay(S, A [a, j]) of completely simple semigroups S=M(G; I, A; P)in the following cases: (1) p_λi∈Z_n, p_λ0j=p_λ0i(λ,λ₀∈∧, i,j∈I); (2) n isprime and I={1,2}; (3) G=Z₃, I={1,2,3}. They are cycles, complete graphs,lexicographic products of cycles and the complement graphs of complete graphs.And they are all Cayley graphs of groups.