Research On2-distance Paired Domination Number

Let G=(V, E) be a simple graph without isolated vertices. The distance betweentwo vertices u and v, denoted by d(u,v), is the number of edges in a shortest pathjoining u and v in G. For a positive integer k, a set D of vertices is a k distance paireddominating set if each vertex in V\D is within distance k of a vertex in D and thesubgraph induced by D contains a perfect matching. The distance paired dominationnumber is the cardinality of a minimum distance paired dominating set. The definitionof distance paired dominating set was first introduced by Raczek in2008. Raczek hasproved that the distance paired dominating set problem for k≥2is NP-complete.In this thesis, we considered the2distance paired dominating problem. Weproved that the2distance paired domination number in a graph G which containsat least9vertices with minimum degreeδ(G)≥2has a upper bound of2n14. Thisbound is compact and, under same conditions, better than Raczek’s bound.In the following discussion,we put in the parameter of girth. In a graph G whichhas at least one cycle, the length of a shortest cycle is called its girth. Hence, we givesome upper bounds of2distance paired domination numbers in terms of minimumdegree, maximum degree and girth. We first give a relation between the minimumdegree and2distance paired domination number in a graph with minimum degreeδ(G)≥2and girth g(G)≥8. Then, we show a relationship between minimum degree,maximum degree and2distance paired domination number in a graph with minimumdegreeδ(G)≥3and girth g(G)≥8. At last, we discuss the relationship between2distance domination number and the girth of a graph in a graph whose minimum degreeis at least3.