The Domination Graphs Of Several Multipartite Tournaments

The definition of the domination graph of a digraph was given by D.C.Fisher et al.when they studied the competition graphs of digraphs.They also gave a characterization of the domination graphs of tournaments.The following result has been proved:The com-plement of the domination graph of a digraph is isomorphic to the competition graph of the complement of the digraph.The competition graph can be applied to the eco-system,radio broadcast and communication over noisy channel.So a large number of researcher-s have paid attention to the domination graph.Multipartite tournament is an important generalization of tournament.In this paper,on the basis of the predecessors’ results,the domination graphs of several multipartite tournaments(such as regular multipartite tour-naments,extended tournaments,bipartite tournaments)are investigated.By observing the property of the domination graph of multipartite tournaments with less number of vertices,we will find the regulation of the domination graphs of the studied digraphs,and give the proof.The thesis consists of four sections.In Chapter 1,we introduce the application background,the development of domination graphs and some basic concepts related to this paper.In Chapter 2,we study the domination graph of a regular multipartite tournament,and characterize the domination graph of a regular multipartite tournament.We prove the following results:Let G be the domination graph of a regular n-partite tournament(n≥3),whose each set contains m vertices,if and only if G is one of the following graphs:(ⅰ)If m = 2,then G is a graph consist of k K2 and 2n-2k isolated vertices,where k is 0,1,2,...,n-2,n;(ⅱ)If m≥3,then G is an empty graph.In Chapter 3,we investigate the domination graph of an extended tournament,and an algorithm to check the domination graph of an extended tournament is given.We prove the following results:Let D= T[S1,S2,…,Sn]be an extended tournament,where T is a tournament on n vertices,V(T)= {v1,v2,…,vn},Si(i = 1,2,…,n)is a set of isolated vertices.For vertices x,y ∈ V(D),dom(D)is the domination graph of D,then xy is an edge of dom(D),if and only if one of the following is true:(i)There exist i,j∈ {1,2…,n} such that Si = {x},Sj = {y},i ≠j,where Si,Sj correspond to vi,vj in T and vivj is an edge of dom(T);(ii)There exist i,j ∈{1,2…,n} such that Si = {x},|Sj|≥2,y ∈ Sj,whcrc Si,iSj correspond to vi,vj in T,vivj is an edge of dom(T),and vi→vj in T;(iii)There exists i ∈ {1,2…,n} such that Si = {X,y},where Si corresponds to vi in T and vi dominates all other vertices of T.In Chapter 4,we study the bipartite tournament and its competition graph by the ad-jacent matrices and the relation between the domination graph and the competition graph of a digraph.Furthermore,the competition graph of the complement of a bipartite tournament is also presented.We prove the following results:(1)Let D =(V,A)be a digraph,the domination graph of D is dom(D),then dom(D)=[C(Dc)]c where C(Dc)is the competition graph of the complement of D.(2)Let m and n be integers such that m≥1 and n≥1.Let G be a graph with n + m vertices.Then the following statements are equivalent:(i)G is the competition graph of a bipartite tournament H with bipartition(X,Y),where |X|= m and |Y| = n.(ii)There exists a Boolean matrix A=(?),such that G is the row graph of A,where O1 and O2 are m x m and n x n zero matrices,respectively.B and C are m ×n and n × m Boolean matrices,respectively.Moreover,BT + C is an n x m full-one matrix.