Some New Results on Distance -Domination in Graphs

We determine the distance -domination number for the total graph, shadow graph, and middle graph of path . 1. Introduction We begin with finite, connected, and undirected graphs, without loops or multiple edges. A dominating set of a graph is a set of vertices of such that every vertex of is adjacent to some vertex of . The domination number is the minimum cardinality of a dominating set of . Further, the open neighbourhood of is the set . The closed neighbourhood of is the set . The distance between two vertices and is the length of shortest path between and in , if exists otherwise, . The open -neighbourhood set of vertex is the set of all vertices of which are different from and at distance at most from in , that is, . The closed -neighbourhood set of is defined as . Obviously . The total graph of a graph is the graph whose vertex set is and two vertices are adjacent whenever they are either adjacent or incident in . The Shadow graph of a connected graph is obtained by taking two copies of , say and . Join each vertex in to the neighbours of corresponding vertex in . The middle graph of a graph is the graph whose vertex set is and in which two vertices are adjacent whenever either they are adjacent edges of or one is a vertex of and the other is an edge incident with it. For standard terminology and notations we rely upon Balakrishnan and Ranganathan [1] and Haynes et al. [2]. The concept of distance dominating set was initiated by Slater [3] while the term distance -dominating set was coined by Henning et al. [4]. For an integer , a is a -dominating set of if every vertex in is within distance from some vertex . That is, . The minimum cardinality among all -dominating sets of is called the -domination number of and it is denoted by . It is obvious that . A -dominating set of cardinality is called a -set. The distance domination in the context of spanning tree is discussed by Griggs and Hutchinson [5] while bounds on the distance two-domination number and the classes of graphs attaining these bounds are reported in the work of Sridharan et al. [6]. In [7] Topp and Volkmann have discussed distance -domination as -covering and characterized connected graphs of order with distance -domination ( -covering). Application of distance domination in Ad Hoc wireless networking is briefly discussed by Wu and Li [8]. More details and bibliographic references on distance -domination can be found in a survey paper by Henning [9]. 2. Some Definitions and Main Results Proposition 1 (see [9]). For , let be a -dominating set of a graph . Then is a minimal -dominating