The(1,2)-step Competition Graphs Of Bipartite Tournaments And Hypertournaments

The notion of the competition graph was introduced by Cohen in the study of food chain network model and the competition graph can be applied to the economic systems.Besides,it also has applications in the study of communication over noisy channel and in the problem of assigning channels to radio or television transmitters.So many researchers have paid attention to the competition graph.As Factor et.al.defined the(1,2)-step competition graph of a digraph in 2011 and characterized the(1,2)-step competition graph of a tournament,the(i,j)-step competition graphs of several tournament-like digraphs have also become one of research focuses.In this thesis,we study the competition graph of a bipartite tournament and the relation between the graph and the(1,2)-step competition graph.On the basis of the(1,2)-step competition graph of a tournament,we characterize the(1,2)-step competition graph of a hypertournament.The thesis consists of four sections.Chapter 1 is the preface.The application background,the development of competition graphs and basic concepts are introduced.And the contents of this thesis is proposed.In Chapter 2,we study the independence number of its competition graph for any bipartite tournament with bipartition(X,Y),where |X| =m and |Y| = n.We obtain the maximum independence number amax(m,n)and the minimum independence number?min(m,n).And get the following conclusions:3.If m,n satisfies(m,n)?(1,1),then for any integer k ? {3,4,...,max{m,n} + 1},there exists a bipartite tournament H with bipartition(X,Y),where |X| = m and |Y| = n,such that the independence number of the competition graph G of H is exactly k.In Chapter 3,we consider the relation of the edge sets between the competition graph and the(1,2)-step competition graph of a bipartite tournament.The lower bound ?min1,2(m,n)and the upper bounde ?max1,2(m,n)of the difference of the edges' numbers of the two graphs are obtained.And some examples show the sharpness of the bounds.We prove the conclusions:1.Let m and n be integers such that m?2 and n? 2.Thene ?min1,2(m,n)= 0.Moreover,H?H(m,n)satisfying ?1,2(H)=?min1,2(m,n)?0 if and only if one of the following is true:(a)X?Y or Y?X;(b)H is a 4-cycle.2.Let m and n be integers such that m? 4 and n?4.Then ?max1,2(m,n)= mn.Moreover,H?H(m,n)satisfies ?1,2(H)=?max1,2(m,n)=mn if and only if the out-degree of each vertex in H is not less than 2.In Chapter 4,we characterize the(1,2)-step competition graph of a hypertournament and extend some results to the(i,j)-step competition graph of a hypertournament.We prove the conclusions:1.A graph G with n vertices is the(1,2)-step competition graph of some strong k-hypertournament T with 3?j?n-1 if and only if G is Kn,Kn-E(P2),or Kn-E(P3).2.A graph G with n vertices is the(1,2)-step competition graph of some k-hypertournament T with 3?k?n-1 if and only if G is Kn,Kn-E(P2),Kn-E(P3),or Kn-1 U K1.3.Let T be a k-hypertournament with n vertices satisfying 3 ? k ? n-1 and i>1,j? 2 be integers.Then Ci,j(T)= C1,2(T).