Vertex-transitivity Of Cayley Graphs Of Completely Simple Semigroups

The study of symmetric graphs is an active area in graph theory.It has broad application prospects in network design and optimization, information science, communications subjects and other fields.Let S be a finite semigroup,and let A be a subet of S.The (left)Cayley graph Cay(S,A) of S relative to A is defined as the digraph with vertex set S and arcs set consisting of those pairs (x,y) such that ax=y for some a∈A.The conditions for Cayley graphs of semigroups to be undirected and vertex-transitivity are reduced to the case of completely simple semigroups.There are two minimal undirected Cayley graphs of completely simple semigroups Cay(S,A[a,j])and Cay (S,A[a,τ,j]) .Thispaper aims at the structures and properties of the minimal undirected Cayley graph of completely simple semigroups, shows the structure of Cay (S,A[a,j]), proves its vertex-transitivity, and thence deduces it is the Cayley graph of groups; shows the structure of Cay(S,A[a,τ,j]), designs acomputer algorithm to get the structure and the number of loop of Cay(S,A[a,τ,j]), and obtains the sufficient and necessary conditions for vertex-transitivity of Cay(S,A[a,τ,j]) in the situation of small orders (less then 46).