正则多部竞赛图的控制图

The Domination Graph of a Regular Multipartite Tournament

设D=(vA)是一个有向图,x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D.有向图D的控制图记为dom(D),它是—个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D.1998年,Fisher等人首次提出控制图的概念,并完全刻画了竞赛图的控制图.本文研究正则多部竞赛图的控制图,并给出了—个无向图是某个正则多部竞赛图的控制图的一个刻画.

Given a digraph D = （V, A） and x, y ∈ V（D）, let O（x） denote the set of vertices which x beats. Two vertices x and y dominate D if O（x） O（y） [2 {x,y} = V（D）. The domination graph of D, denoted by dora （D）, is a graph with vertices V（D） and for any x, y ∈ V（D）, xy is an edge of dom （D） if and only if vertices x and y dominate D. The definition of the domination graph of a digraph was given by Fisher et al. in 1998, and in the same article they also gave a characterization of the domination graphs of tournaments. In this paper, we investigate the domination graph of a regular multipartite tournament and characterize the graph which is the domination graph of regular multipartite tournament.