The Minimum Dominating Set Of Local Semicomplete Digraphs

A local semicomplete digraph is an important kind of graphs in digraph theory.Bang-Jensen et al.described the structures,classification and related conclusions of local semicomplete digraphs.Since then,this class of graphs has aroused extensive interest from researchers and also obtained many meaningful results.The domination theory of graphs derived from a board game in ancient India.Later,the problems of the five queens and the eight queens aroused the interest again of people.In 1962,Berge and Ore gave the concepts of the dominating set and the domination number.Since then,more and more scholars have studied deeply and meticulously on domination theory of graphs.Domination theory is not only widely used in computer,communication,network,etc.,but also closely related to the research of the famous Caccetta-Haggkvist conjecture in digraphs.Therefore,the domination theory of a graph has been one of the most important aspects of graph theory.There are four chapters in this paper.It introduces the research contents and significance of the article,as well as the structures and the related conclusions of local semicomplete digraphs in Chapter 1.In Chapter 2,the minimum dominating set of a round digraph is studied and characterized.In Chapter 3,we research the minimum dominating set of a pure local tournament which is non-round decomposable.In Chapter 4,we summarize the research contents of this article.A round digraph is an important subclass of local semicomplete digraphs.In Chapter 2,according to the structures of a round digraph,the minimum dominating set of a round digraph is completely characterized by studying the minimum dominating set of a round pure local tournament,a round digraph and a round non-local tournament.A pure local tournament which is non-round decomposable belongs to another subclass graph of local semicomplete digraphs.In Chapter 3,wecharacterize the minimum dominating set of a pure local tournament which is non-round decomposable.By analyzing the possible values of the order of the minimum dominating set of a pure local tournament which is non-round decomposable,and then the characterization of the minimum dominating set of this kind of digraphs is completed.