Domination In Generalized De Bruijn Digraphs And Hypergraphs

Within the past near fifty years, concurrent with the growth of computer science, internet and communication networks, graph theory has been explosive growth. The study of domination in graphs is one of the fastest growing areas within it. As an important research fields in graph theory, domination theory has many and varied applications in related fields, such as computer science, combina-torial optimization, communication networks, coding theory, monitor system and operations research. In this paper, we study the domination in important network topologies -generalized de Bruijn and Kautz digraphs and in hypergraphs.Generalized de Bruijn digraphs Gs(n,d) and generalized Kautz digraphs GK(n,d) are extended from de Bruijn and Kautz digraphs. As the important topology candidate of the internet, because of their good structures and perfor-mances, the research of various network parameters in GB(n, d) and GB(n, d) has received great attention.First, we discuss the domination number of GB(n, d). The domination num-ber of G, denoted by γ(G), is the cardinality of the minimum dominating set of G. In 2003, Kikuchi and Shibata show that [n/d+1]≤γ(GB(n,d))≤[n/d]. Further, they propose a conjecture:each generalized de Bruijn digraph has a minimum dominating set that is consecutive. By constructing a minimum (consecutive) dominating set of a generalized de Bruijn digraph, we prove that its domina-tion number has exactly two values, that is,γ(GB(n,d))=[n/d+1] or [n/d+1]+1. Additionally, using a related result in number theory, we provide a complete char-acterization of generalized de Bruijn digraphs with the domination number equal to [n/d+1]or[n/d+1]+1. As a consequence of the above results, we prove the above conjecture posed by Kikuchi and Shibata.Secondly, we stuty the distance l-domination in GB(n, d) and GK(n, d). The distance l-domination number of G, denoted by γl(G), is the cardinality of a minimum distance l-dominating set of G. By constructing a l-dominating set, we prove that every generalized de Bruijn digraph has the distance l-domination number and the distance l-domination number of each generalized Kautz digraph bounded above by [n/(dl-1+dl)]. Addition-ally, we present various sufficient conditions for the equality.Then we discuss the twin domination in GB(n,d) and GK(n, d). The twin domination number γ*(G) of G is the cardinality of a minimum twin dominat-ing set of G. we present a new upper bound on the twin domination number of GB(n,d) and GK(n,d), which improves the known upper bound in previous literature.Finally, we present the domination of hypergraphs. Hypergraphs are natural generalization of undirected graphs and in recent years the dominating set of Hypergraph is just proposed and studied. In this paper, we study the domination number in hypergraphs. The domination number γ(H), matching number v(H) and transversal τ(H) are several important parameters of hypergraphs. While a long-standing open problem is known as Ryser’s conjecture in an r-partite hypergraph, which states that any r-partite hypergraph satisfies τ(H)≤ (r 1)v(H). The conjecture turns to be notoriously difficult for r≥4 and remains open. We establish a Ryser-like bound relating the domination number to the matching number for hypergraphs. and prove that every hypergraph of rank r satisfies the inequality γ(H)≤ (r-1)v(H). A constructive characterization of general hypergraphs of rank r satisfying γ(H)= (r -1)v(H) seems difficult to obtain. And we provide a complete characterization of the hypergraphs of rank 3 with γ(H)=2v(H).Further, we give a complete characterization of the linear intersecting hypergraphs of rank r=4 whose domination number is equal to 3.