Research On Paired-domination Problem And Power Domination Problem Of Graphs

Dominating set is an important concept in graph theory,which is defined as a vertex subset such that every other vertex not in it must be adjacent to some vertex in this subset.Paired-domination problem and power domination problem are two important domination problems.In this dissertation,we study these two domination problems.Let G =(V,E)be a simple graph without isolated vertices.A set S(?)V is called a paired-domination set if every vertex in V\S has at least one neighbor in S and G[S]contains a perfect matching.The paired-domination number of G,denoted by ?pr(C),is defined as minmin{|S|| S is a paired-domination set}.Let G =(V,E)be a simple graph.A set S(?)V is a power dominating set of G if and only if all vertices of V(G)have messages by the following two ways:(1)If a vertex v? S,then it sends message to itself and all its neighbors.(2)If a vertex v with message has only one neighbor u without message,then v will send a message to u.The power domination number of a graph G,denoted by ?p(G),is defined as min{|S|| S is a power domination set}.The concept of k-power domination in graphs is a natural generalization of power domination.Let G =(V,E)be a simple graph and k be a nonnegative integer.A set S(?)V(G)is a k-power dominating set of G if and only if all vertices of V(G)have messages by the following two ways:(1)If a vertex v? S,then it sends message to itself and all its neighbors.(2)If a vertex v with message has at most k neighbors without message,then v will send message to all its neighbors without message.The k-power domination number of a graph G,denoted by ?p,k(G),is defined as min{|S|| S is a k-power domination set}.When k = 0,the k-power domination problem is the domination problem.When k = 1,the k-power domination problem is the power domination problem.Determining the upper bound on domination number is an important research direction of domination theory.Claw-free graph is an important class of graph-s.Chapter 1 introduces the background and the research status of the paired-domination problem and power domination problem.In Chapter 2 and Chapter 3,we study upper bounds on paired-domination number and power domination number,respectively.In 2009,Goddard and Henning proposed the conjecture:if G(?)P is a connected graph with order n and ?(G)?3,where P is the Petersen graph,then ?pr(G)?4n/7.It is an important conjecture on the study of the upper bound of paired-domination number.In Chapter 2,we consider the paired-domination number of claw-free graph.We prove that if G is a claw-free graph with ?(G)? 4,then ?pr(G)?n/2,and the bound is sharp(see Thm.2.1.1).It improves the result presented by Cao et al.in 2016.In 2013,Dorbec et al.presented this conjecture:For k>1 and r>3,if G(?)Kr,r is a connected r-regular graph of order n,where Kr,r is the complete bipartite graph,then ?p,k(G)?n/r+1 Dorbec et al.also proved this conjecture is correct when k = 1,r = 3.In Chapter 3,we first give the counterexamples for r-regular claw-free graphs,where r>4 is an even number,and partly disprove the conjecture presented by Dorbec et al.Then we study the upper bound of the power domination number of 4-regular claw-free graph.We prove that if G is a connected 4-regular claw-free graph of order n,then ?p(G)?n+1/5 and the bound is sharp(see Thm.3.1.1).