Research On Neighborhood Total Domination Numbers Of Graphs

Let G = (V,E) be a simple graph. A dominating set D of G is a subset of V such that every vertex in V \ D is adjacent to at least one vertex in D. The domination number of G, denoted by γ(G). is the minimum cardinality of a dominating set of G. A total dominating set D of G is a subset of V such that every vertex in V is adjacent to at least one vertex in D. The total domination number of G, denoted by γt(G), is the minimum cardinality of a total dominating set. A neighborhood total dominating set D of G is a subset of V such that D is a dominating set of G with an extra property:every vertex u ∈V\D,u has at least one neighbor in N(D). The neighborhood total domination number of G, denoted by γnt(G), is the minimum cardinality of a neighborhood total dominating set of G. If G is a graph with no isolated vertex, then γ(G) ≤γnt(G) ≤ γt(G) ≤ 2γ(G). In this paper, we consider the neighborhood total domination problem and its related problems. The main results are as follows:The neighborhood total domination problem concerns testing whether γnt(G)≤ (?) for a given graph G and a positive integer (?), that is, whether there is a neigh-borhood total dominating set S such that |S| ≤ (?)? In Chapter II, we prove that the neighborhood total domination problem is NP-complete for bipartite graphs and split graphs. Furthermore, by using dynamic programming, we give a linear algorithm for determining the neighborhood total domination number of trees. Besides, we extends the algorithm to vertex-weighted trees, that is, each vertex of tree will be assigned a positive value as its weight.In Chapter III, we give a family T which contains every tree T such that γnt(T) = 2γ(T), and characterize a constructive property of these trees. A pack-ing of a graph G is a set S of vertices of G such that the distance in G of any two vertices in S is at least 3. The packing number ρ(G) is the largest cardinality of a packing of G:We also give a family which contains every graph G such that γnt(G)= ρ(G) and a forest family which contains every forest whose domination number equals to neighborhood total domination number.In Chapter Ⅳ, considering the relationship between order, size and neigh-borhood total domination number of a graph G, we prove that if G ≠ K2 is a connected graph with order n and size m, then m≤1/2(n － γnt(G))(n － γnt(G)+3). Considering the relationship between diameter of a graph and the neighborhood total domination number of its complement graph, we prove that if G is a graph without isolated vertex and diam(G)≥ 3, then γnt(G) = 2.In Chapter Ⅴ, by using the probabilistic method, we give an upper bound of the neighborhood total domination number of a graph G with order n and δ(G)≥ 2. We also give an upper bound of the neighborhood total domination number of a connected graph G with minimum degree δ(G)≥ 2 and girth g(G)≥ 5.In Chapter Ⅵ. considering the neighborhood total domination number of a Mycielski’s graph μ(G), we prove that if G is a graph without isolated vertex, then γnt(μ(G)) ≤ γnt(G)+1. We prove that for any nonnegative integer k, there exists a graph G without isolated vertex such that the difference γnt(G) － γnt(μ(G)) is equal to k. Considering the relationship between the neighborhood total domination number of μ(G) and the domination number of G, We prove that γ(G)+1 ≤ γnt (μ(G)) ≤ γ(G)+2 for any graph G. We also give a necessary and sufficient condition for γnt(μ(G)) = γ(G)+1 when γ(G) = 1, and a sufficient condition for γnt(μ(G)) = γ(G)+1 when γ(G)≥ 2.