Some Studies On The Cayley Graphs Of Semigroups

This dissertation consists of five chapters. We study the properties and construc-tions of the Cayley graphs of some semigroups.In the first chapter, the Cayley graphs of Brandt semigroups will be investigated. The basic structures and properties of this kind of Cayley graphs are given, and a necessary and sufficient condition is given for the components of Cayley graphs of Brandt semigroups to be strongly regular. As an application, the generalized Petersen graph and k-partite graph, which can not be obtained from the Cayley graphs of groups, can be constructed as a component of the Cayley graphs of Brandt semigroups.In Chapter 2, the Cayley graphs of completely simple semigroups will be investi-gated. The basic structure and properties of this kind of Cayley graph are given, and a condition is given for a Cayley graph of a completely simple semigroup to be a disjoint union of complete graphs. We also describe all the completely simple semigroups with strongly connected bipartite Cayley graphs.In Chapter 3, the Cayley graphs of the left groups and of the right groups are investigated, respectively. The basic structures and properties of these two kinds of Cayley graphs are given. We prove that the undirected Cayley graphs of the right groups are isomorphic to the Cayley graphs of group G×Zn with respect to appropriate connection sets. As an application, we give the structure of the undirected Cayley graphs of the rectangular groups. In particular, we give a complete description of vertex-transitive Cayley graphs of the strong semilattice of rectangular groups.In Chapter 4, let (?)X be the symmetric inverse semigroup on a finite nonempty set X, A be a subset of (?)X* ((?)X\{0}). We obtain a condition of Cay((?)X*, A) (which is obtained by deleting vertex 0 from the Cayley graph of (?)X with respect to A) to be ColAut A((?)X*)-vertex-transitive and AutA((?)X*)-vertex-transitive, respectively. The basic structure of vertex transitive Cay((?)X*, A) is characterized. We also prove that the generalized Petersen graph can be constructed as a connected component of a Cayley graph of a symmetric inverse semigroup, by choosing a appropriate connecting set. In Chapter 5, we investigate the divisibility graphs and power graphs of the com-pletely regular semigroups. We give the structures of these two kinds of graphs and describe a combinatorial property of completely regular semigroups defined in terms of divisibility graphs and power graphs, respectively.