The Independent Set Structure Of The Loop Graph Under The Tensor Product

The extremal combinatorics is one of the most active research area in combinatorics and graph theory.Typical problems is to determine the extremal value and structure of a certain systems.In this field,the Erdos-Ko-Rado theorem of finite set is one of the central theorems.Generalising EKR theorem to general system is equivalent to determine the independence number of graphs.In this paper,we mainly study the independence numbers of the tensor product of vertex-transitive graphs.The main contents of this paper are listed in the following:In the first part,we introduce some results of extremal combinatorics,such as Sperner theorem and EKR theorem.At the same time,we emphatically introduce the background and status of the EKR theorem,as well as some basic concepts and classical theorems to be used in this paper.In the second part,we determine the independence numbers of the tensor product of G,Kn1:r1 and Kn2:r2 and the structure of the maximum independent sets.In the last part,by applying the results obtained in the second part,we determine the independence number of the tensor product of some special graphs.