The Domination Number And Roman Domination Number Of The Cartesian Products Of Graph

For any graph G, a nonempty subset of its vertex set is a domination set, if every vertex in V(G)-D, N(x)∩D≠(?). The domination number of a graphG is the minimum concentration of domination set. Let γ(G) be the domination number of a graph G and Gâ–¡H denote the Cartesian product of graphs G and H. In the Cartesian product of graphs G and H,(u,v) and (u’,v’) are adjacent if and only if v=v’, uu’∈E(G) or u=u’, w’∈E(H). In this paper, we determine the domination number of the Cartesian products of Cmâ–¡Pn (m=2,3,4) and Pmâ–¡Cn (m=2,3,4).A function f:V(G)â†'{0,1,2} is a Roman dominating function (RDF) if for any vertex u∈V0must have NG (u)∩V2≠(?), where Vi={u∈V(G)|f(u)=i). The weight of f is given by f(V(G))=∑u∈V(G)f(u), The Roman domination number γR(G) is the minimum weight among all RDF fs of G, and we point that a function f is a γR(G)-function if it is an RDF and f(V(G))=γR(G). In1963, Vizing made the well-known conjecture on the domination in Cartesian product, point out the lower bound on domination number of any two graphs’ Cartesian product, i.e. γ(Gâ–¡H)≥γ(G)γ(H), thus causing a great deal of attention and obtain many relevant conclusions related to Vizing’s conjecture. This paper given a lower bound on γ(Gâ–¡H) relate to Vizing’s conjecture:for any graphs G and H, γR(G)γR(H)≤4γ(Gâ–¡H).We obtain a lower bound on γR(Gâ–¡H) related to Vizing’s conjecture:for any graphs G and H, γR(Gâ–¡H)≥γ(G)γ(H)+min{γ(G),γ(H)}.The structure of this paper is:In chapter1,2, we introduce the background and the research status of the domination number and Vizing’s conjecture, the basic concept and professional knowledge of Graph theory. From chapter3to chapter5, we given the three main research results respectively in this paper. In chapter5, we summarize the main research results and discuss the problems for further research.