Research On K-power Domination Number Of Graphs

The domination problem of graphs is a classic problem in graph theory research.The k-power domination problem studied in this paper was birthed from the problem of monitoring electrical networks,and it is a generalization of the domination problem.S is a k-power dominating set of a graph G if and only if all vertices of G can finally obtain messages by the following two ways:（1）If u∈ S,then u can send messages to itself and all its neighbors;（2）If a vertex u has messages and it has at most k neighbors without messages,then u can send messages to neighbors without messages.The minimum cardinality of k-power dominating sets is called k-power domination number,denoted by γp,k（G）.The k-power domination problem of graphs is to study the k-power domination number of graphs.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.This dissertation consists of four chapters.In the first chapter,we first introduce some related concepts,and introduce the origin and development of the domination problem of graphs.Then,some variants of the domination problem are introduced,mainly including total domination problem and k-power domination problem.Finally,our main results are presented.In the second chapter,we study the upper bound of k-power domination number for regular graphs.In 2013,Dorbec et al.proposed the following related conjectures and open questions.Conjecture.For integers k≥1 and r≥ 3.If G（?）Kr,r is a connected r-regular graph of order n,then γp,k（G）≤n/（r+1）.Question.For an integer r≥3,let G ≠Kr,r be a connected r-regular graph of order n.Determine the smallest positive value,kmin（r）,of k such that γp,k（G）≤n/（r+1）.In this chapter,we give a series of counterexamples to negate the conjecture of Dorbec et al.,and answer their open question,that is,kmin（r）=r-2.In the third chapter,we study the case of claw-free graphs of the above conjecture,and prove the following results.Theorem.For integers l∈{2,3} and k≥l,if G is a connected claw-free（k+l+1）regular graph of order n,then γp,k（G）≤n/（k+l+2）and the bound is tight.In the fourth chapter,we study the upper bound of the power domination number of regular connected graphs,and give the best upper bound of the power domination number of 4-regular connected graphs.Theorem.If G is a connected 4-regular graph of order n,then γp,1（G）≤2n/7 and the bound is tight.This theorem partially answers an open question about the power domination number in the book " Topics in Domination in Graphs".This theorem is also a generalization of Lu et al.’s results on the power domination number for 4-regular claw-free graphs.In addition,we also prove the following theorem.Theorem.If G is a connected 5-regular graph of order n,then γp,2（G）≤2n/9.