| The interest for Cayley graphs, in fundamental or applied mathematics, comes mainly from their automorphism group. Despite this fact, the problem of determining what this group is equal to in general is still essentially open. This is the first problem we study in this thesis.; The first researchers to work on this question were Babai and Godsil. They conjectured in [4] that almost all Cayley graphs Gamma( G, S) are GRR, which means that they have the group of left translations L(G) as their full automorphism group. Even if this conjecture is probably true, a lot of well known families of Cayley graphs are not constituted of GRR. This phenomena, a priori surprising, can be explained by the fact that the generating sets of these Cayley graphs have symmetries and that these symmetries correspond to automorphisms that are not left translations. In order to include these graphs which are not GRR, we introduce the notion of holomorphic Cayley graph: a Cayley graph Gamma = Gamma(G, S) is holomorphic if its automorphism group is the product of L(G) and AutSG, the subgroup of automorphisms of G that stabilize S, the generating set of the graph.; In chapter 1 we present new tools to determine the automorphism group of a Cayley graph. In chapter 2 we determine the automorphism group of all Cayley graphs generated by transpositions, which are the graphs of the form Gamma = Gamma( Sn , S), where S is a set of transpositions that generates the symmetric group Sn . We prove that all these graphs are holomorphic, thus that their automorphism group is AutGamma = L( Sn )AutS Sn , except for the one such that the transposition graph of S, denoted TS, is a square or a complete graph of order greater than 2. We will show also that AutS Sn ≃ AutTS if n ≥ 3. These two results generalize the theorem of Godsil and Royle [15 ] which states that AutGamma = L( Sn ) if S is a minimal generating set of Sn and the automorphism group of TS is trivial. In chapter 3 we prove the existence of new classes of holomorphic Cayley graphs, the most important being a class based on abelian groups, a class generated by involutions, and a class based on alternate or symmetric groups and generated by transpositions and cycles of length 3.; The second problem we will study is the isomorphism between Cayley graphs, that consist in determining when Gamma(G, S) ≃ Gamma( H, T). This problem is very complex and its solution depends on the automorphism group of the considered Cayley graphs. Since recent research suggest that the majority of Cayley graphs are holomorphic and that we have a precise knowledge of the automorphism group of these graphs, we have restricted ourselves to this class. Our goal is to obtain stronger results than in the general case on an important class of Cayley graphs.; We will approach this question in two steps. We will first study, in chapter 6, the isomorphism between Cayley graphs based on a fixed group. This will allow us in particular to characterize holomorphic Cayley graphs that are CI, which answers a question raised by Cal Heng Li in [21]. Next, in chapter 7, we will work on the isomorphism between Cayley graphs based on different groups. The results of these two chapters will allow us to solve the isomorphism problem for holomorphic Cayley graphs based on a cyclic group, a simple group, a symmetric group, a direct product of two non abelian simple groups, and a non trivial semi-direct product of two simple groups (for complete holomorphic Cayley graphs). (Abstract shortened by UMI.)... |
