Perfect Codes Of Bi-Cayley Graphs

A subset of the vertex set of a graph Γ is called a perfect code in Γ if every vertex ofΓ is adjacent to exactly one vertex of .Perfect code(also called an efficient dominating set or independent perfect dominating set)is one of the important research objects in graph theory.Cayley graphs are constructed from groups.The easy construction and high symmetry of Cayley graphs have made them important models in graph theory.Up to now,there are many results on perfect codes of Cayley graphs.While Bi-Cayley graphs are constructed quite similarly to Cayley graphs,they are generally not vertex transitive.But,they are next to vertex transitive.There are quite few results on perfect codes of Bi-Cayley graphs.This thesis is mainly on perfect codes of Bi-Cayley graphs.There are four parts as follows.In Chapter 1,we introduce definitions,symbols and related results that are used in this thesis.The background and known results of perfect codes in Cayley graphs and Bi-Cayley graphs are surveyed.In Chapter 2,We extend István Estélyi’s theory of Haar graphs isomorphic to algebraically Cayley graphs to general Bi-Cayley graphs.We give necessary and sufficient conditions for Bi-Cayley graphs to be isomorphic to algebraically Cayley graphs.In Chapter 3,some equivalent conditions for the existence of perfect codes of regular Bi-Cayley graphs are given.we also give equivalent conditions for the existence of subgroup perfect codes.In Chapter 4,several equivalent conditions for the existence of total perfect code of regular Bi-Cayley graphs are given.And,equivalent conditions for the existence of total subgroup perfect codes are given,as well.