Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Explicit Cayley covers of Kautz digraphs"

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 Josep.M.Brunat@upc.edu 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 .