正则多部竞赛图的控制图  

The Domination Graph of a Regular Multipartite Tournament

作　　者：李瑞娟[1] 刘冬婷 

机构地区：[1]山西大学数学科学学院,太原030006

出　　处：《应用数学学报》2016年第4期555-561,共7页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11401353);山西省青年科技研究基金(2013021001-5);山西省回国留学人员科研(2013-017)资助项目

摘　　要：设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.

关 键 词：正则多部竞赛图 控制图 控制对 

分 类 号：O157.5[理学—数学]