The Domination Number Of Several Kinds Of Digraphs

Domination parameters theory in graphs is an important research direction of graphtheory, it has wide applications in many fields such as communication network, monitoringsystem and so on. Determine the domination number of graphs is a fundamental problemof domination parameters theory, it provides an important premise for the development offault-tolerant parameter problem.The line graph method, cartesian product method and strong product method are veryimportant techniques for constructing a large graph from a given graph or some given graphs.This methods have been widely used in the design of interconnection networks. Study thedomination number of the graphs constructed by this method will help us more in-depthknow its structural properties and provide a rich theoretical support for many applicationareas such as network optimization design.The text of the paper consists of four chapters. In the first chapter, the research back-ground and some research results of domination parameters theory in graphs are Introduced,the common concepts and symbols of the following tree chapters are given. In the secondchapter, the domination problem of iterated line digraph of a complete bipartite digraph isinvestigated and the exact value of the domination number of iterated line digraph of a com-plete bipartite digraph is determined. In the third chapter, the domination number of thestrong product of n(≥2) directed cycles is studied. The exact value of the domination num-ber of the strong product of two directed cycles is determined; Furthermore, a lower boundand an upper bound of the domination number of the strong product of n(≥3) directedcycles are given; Especially, the exact value of the domination number of the strong productof n(≥3) directed cycles are given when there are at least n2cycles are even. In thefourth chapter, the domination number of the strong product of a digraph and n(≥1) direct-ed paths is geven; Especially, the exact value of the strong product of n(≥2) directed pathsis determined; Furthermore, an upper bound and a lower bound of the domination numberfor the strong product of two arbitrary digraphs and the strong product of a directed cycleand a arbitrary digraph are given.