A Study Of Regular Sets In Cayley Graphs And Hopf Algebras On Subgraphs Of Graphs

Perfect codes have been important objects of study ever since the dawn of coding theory.As generalizations of perfect codes in the classical setting,Biggs first introduced perfect codes into graph theory.In recent years,many scholars have paid attention to the perfect codes of Cayley graphs.Generalizing the concept of perfect codes of a graph obtain the concept of regular sets of a graph.Since it was put forward,regular sets of graphs have attracted the attention of many researchers and have received results of partitions and group representation.In this paper,we will study regular sets of Cayley graphs,semi-Cayley graphs and Cayley sum graphs.An(a,b)-regular set in a graph Γ is a nonempty proper subset D of the vertex set V(Γ)such that every vertex in D has exactly a neighbours in D and every vertex in V(Γ)\D has exactly b neighbours in D,where a,b are nonnegative integers.A(0,1)-regular set is called a perfect code.A(1,1)-regular set is called a total perfect code.A subset D of a group G is called an(a,b)-regular set of G if it is an(a,b)regular set in some Cayley graph(or,Cayley sum graph)of G,and an(a,b)-regular set in a Cayley graph(or,Cayley sum graph)of G is called a subgroup(a,b)-regular set if it is also a subgroup of G.Notice that studying regular sets of a regular graph is actually studying properties of subgraphs induced by some subsets in this regular graph.Continuing this line,we also construct a Hopf algebra on subgraphs of a graph.This thesis contains six chapters.In Chapter 1,we first give some basic concepts,notations and terminology.Then we give the research background and the research progress.Moreover,we point out the motivation and some results.In Chapter 2,we study(a,b)-regular sets in Cayley graphs with a focus on(0,k)-regular sets,where k≥ 1 is an integer.Among other things we determine when a non-trivial proper normal subgroup of a group is a(0,k)-regular set of the group.We also determine all subgroup(0,k)-regular sets of dihedral groups and generalized quaternion groups.We obtain necessary and sufficient conditions for a connected cubelike graph or the Cartesian product of n copies of the cycle of length p to admit(0,k)-regular sets,where p is an odd prime and a cubelike graph is a Cayley graph of an elementary abelian 2-group.Our results generalize several known results from perfect codes to(0,k)-regular sets.In Chapter 3,we obtain the necessary and sufficient condition for the existence of perfect codes in the semi-Cayley graphs SC(G;R,R,T).As an application,we also give the necessary and sufficient condition for the existence of perfect codes for Cayley graphs of two types on a dihedral group,or a generalized quaternion group.In Chapter 4,we obtain two necessary and sufficient conditions for a subgroup of a finite group G to be a total perfect code in a Cayley sum graph of G.We also obtain two necessary and sufficient conditions for a subgroup of a finite abelian group G to be a total perfect code of G.We classify finite abelian groups whose all non-trivial subgroups of even order are total perfect codes of the group,and as a corollary we obtain that a finite abelian group has the property that every nontrivial subgroup is a total perfect code if and only if it is isomorphic to an elementary abelian 2-group.We prove that,for a subgroup H of a finite abelian group G and any pair of positive integers(a,b)within certain ranges depending on H,H is an(a,b)-regular set of G if and only if it is a total perfect code of G.Finally,we give a classification of subgroup total perfect codes of a cyclic group,a dihedral group and a generalized quaternion group.In Chapter 5,we obtain a structural characterization of perfect codes of degree pl-1,p a prime,in connected non-complete circulant graphs.The characterization naturally provides counting results of the number of such perfect codes and give a way to construct connected non-complete circulant graphs of degree pl-1 admitting perfect codes.In Chapter 6,we construct a bialgebraic and further a Hopf algebraic structure on top of subgraphs of a given graph.Further,we give the dual structure of this Hopf algebraic structure.We study the algebra morphisms induced by graph homomorphisms,and obtain a covariant functor from a graph category to an algebra category.