Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Explicit Cayley covers of Kautz digraphs. | Explicit Cayley covers of Kautz digraphs Josep M. Brunat Departament de Matematica Aplicada II Universitat Politecnica de Catalunya Submitted Mar 3 2010 Accepted Apr 27 2011 Published May 8 2011 Mathematics Subject Classifications 05E18 05C25 05C20 Abstract Given a finite set V and a set S of permutations of V the group action graph GAG V S is the digraph with vertex set V and arcs v vơ for all v E V and ơ E S. Let S be the group generated by S. The Cayley digraph Cay S S is called a Cayley cover of GAG V S . We define the Kautz digraphs as group action graphs and give an explicit construction of the corresponding Cayley cover. This is an answer to a problem posed by Heydemann in 1996. 1 Introduction The importance of graph symmetry from theoretical and applied points of view has been emphasized many times see for instance 1 2 11 12 14 . Furthermore the idea of associating a Cayley digraph to a non-symmetric digraph in such a way that the properties of one gives information about the other has been frequently used. For instance Fiol et al. 7 8 9 have shown that in the context of dynamic memory networks the idea of associating a Cayley digraph on a permutation group on the set of vertices of the network plays a central role in a unified approach to the topic. The idea of symmetrization of a digraph is used by Espona and Serra in 6 to construct Cayley covers of the de Bruijn digraphs and by Mansilla and Serra in the context of k-arc transitivity 15 16 . The group action graphs defined by Annexstein et al. in 2 give a way to associate to each non-symmetric digraph a number of Cayley graphs. The de Bruijn and Kautz digraphs are the iterated line digraphs from the complete digraph with and without loops respectively 10 . They are dense digraphs and they have high connectivity and many other good properties 3 . But in general they are not symmetric. Serra and Fiol have calculated the permutation groups of the de Bruijn Work partially supported by .
