Perfect Codes Of Cayley Graphs

A subset D of the vertex set of a graph ? is called a perfect t-code in ? if every vertex of ? is at distance no more than t to exactly one vertex of D.A perfect 1-code is simply called a perfect code.Perfect code(also called an efficient dominating set or independent perfect dominating set)is one of the important research topics in graph theory.Among them,perfect codes in Cayley graphs play a vital role in design and analysis of communication networks,and the optimal configuration of resources.In this thesis,we mainly investigate conditions for a Cayley graph of a finite group to admit a perfect code.This thesis is divided into three chapters as follows.In chapter 1,we introduce definitions,symbols and related theorems that are used in this thesis,and survey the research background as well as progress of perfect codes in Cayley graphs.In chapter 2,we give a new simple proof of Lee's result for the existence of perfect codes of hypercube Qn and generalize it to Cayley graphs of elementary abelian groups.We show that a Cayley graph of an elementary abelian p-group Zpn,where p is an odd prime number,has a perfect code if and only if n=(pm-1)/2 for some integer m and n?2,if and only if it is a regular covering of K2n+1.In Chapter 3,we first give conditions for a subgroup of a finite group to be a perfect code of Cayley graphs of this group.Based on these conditions,we list all subgroup perfect codes in generalized quaternion groups,semi-dihedral groups with order 2n+1 and quasi-dihedral groups,respectively.The subset D of ? is said to be a total perfect code(also called an efficient open dominating set)in ? if every vertex of ? has exactly one neighbour in D.In Chapter 4,we discuss total perfect codes of cubic and quartic Cayley graphs on abelian groups.The fact that cubic Cayley graphs on abelian groups admit total perfect codes if and only if it isomorphic to Mobius ladder M(n)or generalized Petersen graph GP(n,1)is proved in Section 4.2.In Section 4.3,we discuss necessary and sufficient conditions for the existence of total perfect codes of quartic Cayley graphs on abelian groups according to different Cayley subsets separately.