| Within the last thirty years, concurrent with the growth of computer science, graph theory has seen explosive growth. Perhaps the faster growing area within graph theory is the study of domination in graphs. The wide variety of domination parameters that can be defined, about 40-50 different types of domination have been defined.In this paper, we pay our attention mainly on the following two parts of function domination in graphs: (1) Determining the upper minus domination number and the upper signed domination number in a claw-free cubic graph. (2) Discussing some problms on Roman domination in graphs.In Chapter 1, we discuss the upper minus domination number and the upper signed domination number in a claw-free cubic graph, and obtain the following results.Theorem 1.2.9 The upper minus domination number -(G) of a claw-free cubic graph G is at most 1/2|V(G)|.Corollary 1.2.10 If G is a claw-free cubic graph, then -(G) ≤ s(G).Theorem 1.3.6 Every connected claw-free cubic graph satisfies γS(G) ≤2/3n.In Chapter 2, we investigate Roman domination in graphs, and obtain the following results.Theorem 2.3.1 If G is a connected graph of order n, then γr{G) = γ(G) + k if and only if(a) G does not have a vertex set S (?) V with |S| = j such that|N|S|| ∈ {n- (γ(G) +i) + 2j : j ≤i≤k-1}for 1 ≤ j ≤ k - 1.(b) There is a vertex set S0(?) V with 1 ≤ |S0| ≤ k such thatCorollary 2.3.2 If G is a connected graph of order n, and k = min Theorem 2.3.3 If T is a connected tree of order n≥2, then γR(G) = γ(G) + 3 if and only if either one of the following two conditions holds(1) T consists of a healthy spider T1 and a wounded spider T2 with a single edge joining v1∈ V(T1) and v2 ∈ V(T2), subject to the following conditions:(1a) If T2 is P2, then neither vertices in P2 is jointed to the head vertex of T1. (1b) v1 and v2 are not both foot vertices.(2) T consists of three wounded spiders T1, T2, T3 with one edge joining v1 ∈ V(T1) and v2∈ V(T2) and one edge joining v'2 ∈ V(T2) and v3∈ V(T3), subject to the following conditions:(2a) If either tree is P2, then neither vertices in P2 is jointed to the head vertex of other trees.(2b) v1 and v2 are not both foot vertices.(2c) v'2 and v3 are not both foot vertices.Theorem 2.3.4 If G is a connected graph with D(G) = 2, then G is either Roman graph or a graph with γr(G) = 2γ(G) - 1.Theorem 2.3.5 If G is a connected graph with D(G) = 2 and γR(G) = 2γ(G) - 1, then there is a vertex v ∈ V(G) such that G — v is a Roman graph.Theorem 2.3.6 If G is any graph and u is any vertex of G, then the graph H obtained from G by attaching a path of length 3 to u satisfies γR(H) = γR(G) + 2.Corollary 2.3.7 If G is connected Roman graph, then H is also Roman.Theorem 2.3.8 Suppose G0 is a graph with |V(G0)| ≥ 3, u, v ∈ V(G0), and dG0(u) = |V(G0)| - 1, dG0(v) = 1. Let G be any Roman graph and w is any vertex of G, let H = G∪G0 + vw. Then H is also Roman.Theorem 2.3.10 If graph G is strongly Roman, then for every 7-set S each vertex v G 5 has at least three S-pns.
|
PDF Full Text Request