# Some New Results on Distancek-Domination in Graphs

Authors: Samir K. Vaidya; Nirang J. Kothari
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

We determine the distancek-domination number for the total graph, shadow graph, and middle graph of path Pn.


---

## Body

## 1. Introduction

We begin with finite, connected, and undirected graphs,G=(V(G),E(G)) without loops or multiple edges. A dominating set D of a graph G is a set of vertices of G such that every vertex of V(G)-D is adjacent to some vertex of D. The domination number γ(G) is the minimum cardinality of a dominating set of G. Further, the open neighbourhood of v∈V(G) is the set N(v)={u∈V(G)/uv∈E(G)}. The closed neighbourhood N[v] of v∈V(G) is the set N[v]=N(v)∪{v}. The distance d(u,v) between two vertices u and v is the length of shortest path between u and v in G, if exists otherwise, d(u,v)=∞. The open k-neighbourhood set Nk(v) of vertex v∈V(G) is the set of all vertices of G which are different from v and at distance at most k from v in G, that is, Nk(v)={u∈V(G)/d(u,v)≤k}. The closed k-neighbourhood set Nk[v] of v is defined as Nk[v]=Nk(v)∪{v}. Obviously N(v)=N1(v).Thetotal graphT(G) of a graph G is the graph whose vertex set is V(G)∪E(G) and two vertices are adjacent whenever they are either adjacent or incident in G.TheShadow graphD2(G) of a connected graph G is obtained by taking two copies of G, say G′ and G′′. Join each vertex u′ in G′ to the neighbours of corresponding vertex u′′ in G′′.The middle graphM(G) of a graph G is the graph whose vertex set is V(G)∪E(G) and in which two vertices are adjacent whenever either they are adjacent edges of G or one is a vertex of G 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 k-dominating set was coined by Henning et al. [4]. For an integer k≥1, a D⊆V(G) is a k-dominating set of G if every vertex in V(G)-D is within distance k from some vertex v∈D. That is, Nk[D]=V(G). The minimum cardinality among all k-dominating sets of G is called the k-domination number of G and it is denoted by γk(G). It is obvious that γ(G)=γ1(G). A k-dominating set of cardinality γk(G) is called a γk-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 k-domination as k-covering and characterized connected graphs of order (k+1)n with distance k-domination (k-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 k-domination can be found in a survey paper by Henning [9].


## 2. Some Definitions and Main Results

Proposition 1 (see [9]).
Fork≥1, let D be a k-dominating set of a graph G. Then D is a minimal k-dominating set of G if and only if each d∈D has at least one of the following properties.(1)
There exists a vertexv∈V(G)-Dsuch thatNk(v)∩D={d}.(2)
The vertexdis at distance at leastk+1from every other vertexdofDinG.Theorem 2.
Forn≤2k,  γk(T(Pn))=1.Proof.
Letv1,v2,…,vn and e1,e2,…en-1 be the vertices and the edges of Pn, respectively. Then v1,v2,…,vn,e1,e2,…,en-1 will be the vertices of T(Pn). Then D={v⌊n/2⌋} is distance k-dominating set of T(Pn) as n≤2k. The set D being a singleton set it is obviously a minimal distance k-dominating set of T(Pn).Theorem 3.
Forn>2k,
(1)γk(T(Pn))={⌊n2k⌋forn≡0,1(mod2k)⌊n2k⌋+1forn≡2,3,…,2k-1(mod2k).Proof.
Letv1,v2,…,vn and e1,e2,…,en-1 be the vertices and the edges of Pn respectively. Then v1,v2,…,vn, e1,e2,…,en-1 will be the vertices of T(Pn). Now every vertex from vk+1,vk+2,…,vn-k dominates 2k+1 vertices of vi’s and 2k vertices of ei’s at a distance k while every vertex from ek,ek+1,…,en-k dominates 2k vertices of vi’s and 2k+1 vertices of ei’s at a distance k. Therefore at least one vertex from {v1+(2k)j,v2+(2k)j,…,v(k+1)+(2k)j,v(k+2)+(2k)j,…,v(2k)+(2k)j} must belongs to any distance k dominating set D of T(Pn).
Hence,(2)γk(T(Pn))≥⌊n2k⌋.
Now depending upon the number of vertices ofPn, consider the following subsets.
Forn≡0,1(mod(2k)),
(3)D={v(k+1)+(2k)j∣0≤j<⌊n2k⌋},|D|=⌊n2k⌋,
for n≡2,3,…,k(mod(2k)),
(4)D={v(k+1)+(2k)j,vn∣0≤j<⌊n2k⌋},|D|=⌊n2k⌋+1,
for n≡k+1,k+2,…,2k-1(mod(2k)),
(5)D={v(k+1)+(2k)j∣0≤j≤⌊n2k⌋},|D|=⌊n2k⌋+1.
We claim that each D is a distance k dominating set because
(6)d(v(k+1)+(2k)j,vi+(2k)j)≤k,d(v(k+1)+(2k)j,ei+(2k)j)≤k,
where 1≤i≤2k, d(vn,vn-l)≤k, and d(vn,en-l)≤k, where, 1≤l≤k.
Therefore(7)Nk(v(k+1)+(2k)j)={v1+(2k)j,v2+(2k)j,…,vk+(2k)j,v(k+2)+(2k)j,…,v(2k)+(2k)j,e1+(2k)j,e2+(2k)j,…ek+(2k)j,e(k+1)+(2k)j,…e(2k)+(2k)j},Nk(vn)={vn-1,vn-2,…,vn-k,en-1,en-2,…,en-k}.
This implies that Nk[D]=V(T(Pn)) for n≡1,2,…,2k(mod(2k)). Now from the nature of T(Pn), one can observe that every vertex d of D is at a distance at least k+1 apart from every other vertex of D in T(Pn).
Thus by Proposition1, above defined D is a minimal distance k-dominating set of T(Pn). Hence, from (2), for n>2k,
(8)γk(T(Pn))={⌊n2k⌋forn≡0,1(mod2k)⌊n2k⌋+1forn≡2,3,…,2k-1(mod2k).Theorem 4.
Forn≤2k+1, γk(D2(Pn))=1.Proof.
Consider two copies of pathPn. Let v1,v2,…,vn be the vertices of first copy of path Pn and u1,u2,…,un be the vertices of second copy of path Pn. Then D={v⌊n/2⌋} is distance k-dominating set as n≤2k+1. The set D being a singleton, set it is obviously a minimal distance k-dominating set of D2(Pn).Theorem 5.
Forn>2k+1,
(9)γk(D2(Pn))={⌊n2k+1⌋+1forn≡1,2,…,2k(mod(2k+1))n2k+1forn≡0(mod(2k+1)).Proof.
Consider two copies of pathPn. Let v1,v2,…,vn be the vertices of first copy of path Pn and u1,u2,…,un be the vertices of second copy of path Pn. Now every vertex from vk+1,vk+2,…,vn-k dominates 2k+1 vertices of vi’s and 2k+1 vertices of ui’s at a distance k while every vertex from uk+1,uk+2,…,un-k dominates 2k+1 vertices of vi’s and 2k+1 vertices of ui’s at a distance k. Therefore at least one vertex from {v1+(2k+1)j,v2+(2k+1)j,…,v(k+1)+(2k+1)j,v(k+2)+(2k+1)j,…,v(2k+1)+(2k+1)j} must belongs to any distance k-dominating set D of D2(Pn).
Hence(10)γk(D2(Pn))≥⌊n2k+1⌋.
Now depending upon the number of vertices of Pn, consider the following subsets.
Forn≡1,2,…,k(mod(2k+1)),
(11)D={v(k+1)+(2k+1)j,vn∣0≤j<⌊n2k+1⌋},|D|=⌊n2k+1⌋+1,
for n≡k+1,k+2,…,2k(mod(2k+1)),
(12)D={v(k+1)+(2k+1)j∣0≤j≤⌊n2k+1⌋},|D|=⌊n2k+1⌋+1,
for n≡0(mod(2k+1)),
(13)D={v(k+1)+(2k+1)j∣0≤j<n2k+1},|D|=n2k+1.
We claim that each D is a distance k-dominating set because
(14)d(v(k+1)+(2k+1)j,vi+(2k+1)j)≤k,d(v(k+1)+(2k+1)j,ui+(2k+1)j)≤k,
where 1≤i≤2k+1, d(vn,vn-l)≤k and d(vn,un-l)≤k, where 1≤l≤k.
Therefore(15)Nk(v(k+1)+(2k+1)j)={v1+(2k+1)j,v2+(2k+1)j,…,vk+(2k+1)j,v(k+2)+(2k+1)j,…,v(2k+1)+(2k+1)j,u1+(2k+1)j,u2+(2k+1)j,…uk+(2k+1)j,u(k+1)+(2k+1)j,…u(2k+1)+(2k+1)j},Nk(vn)={vn-1,vn-2,…,vn-k,un,un-1,…,un-k},
which implies that Nk[D]=V(D2(Pn)) for any n. Now from the nature of D2(Pn), one can observe that every vertex d of D is at a distance at least k+1 apart from every other vertex of D in D2(Pn).
Thus by Proposition1, above defined D is a minimal distance k-dominating set of D2(Pn). Hence from (10), for n>2k+1,
(16)γk(D2(Pn))={⌊n2k+1⌋+1forn≡1,2,…,2k(mod(2k+1))n2k+1forn≡0(mod(2k+1)).Theorem 6.
Forn≤2k,  γk(M(Pn))=1.Proof.
Letv1,v2,…,vn and e1,e2,…en-1 be the vertices and the edges of Pn, respectively. Then v1,v2,…,vn,e1,e2,…,en-1 will be the vertices of M(Pn). Then D={v⌊n/2⌋} is distance k-dominating set of M(Pn) as n≤2k. The set D being a singleton set, it is obviously a minimal distance k-dominating set of M(Pn).Theorem 7.
Forn>2k,
(17)γk(M(Pn))={⌊n2k⌋+1forn≡1,2,…,2k-1(mod(2k))n2kforn≡0(mod(2k)).Proof.
Letv1,v2,…,vn and e1,e2,…en-1 be the vertices and the edges of Pn respectively. Then v1,v2,…,vn,e1,e2,…,en-1 will be the vertices of M(Pn). Now every vertex from vk,vk+1,…,vn-k dominates 2k-1 vertices of vi's and 2k vertices of ei's at a distance k while every vertex from ek,ek+1,…,en-k dominates 2k vertices of vi's and 2k+1 vertices of ei's at a distance k. Therefore at least one vertex from {e1+(2k)j,e2+(2k)j,…,ek+(2k)j,ek+1+(2k)j,…,e2k+(2k)j} must belong to any distance k-dominating set D of M(Pn).
Hence,(18)γk(M(Pn))≥⌊n2k⌋.
Now depending upon the number of vertices of Pn, consider the following subsets.
Forn≡1,2,…,k(mod(2k)),
(19)D={ek+(2k)j,en-1∣0≤j<⌊n2k⌋},|D|=⌊n2k⌋+1,
for n≡k+1,k+2,…,2k-1(mod(2k)),
(20)D={ek+(2k)j∣0≤j≤⌊n2k⌋},|D|=⌊n2k⌋+1,
for n≡0(mod(2k)),
(21)D={ek+(2k)j∣0≤j<n2k},|D|=n2k.
We claim that each D is a distance k-dominating set because
(22)d(ek+(2k)j,ei+(2k)j)≤k,d(ek+(2k)j,vi+(2k)j)≤k,
where 1≤i≤2k, d(en-1,en-l)≤k, and d(en-l,vn-l)≤k, where 1≤l≤k.
Therefore(23)Nk(ek+(2k)j)={e1+(2k)j,e2+(2k)j,…,e(k-1)+(2k)j,e(k+1)+(2k)j,…,e(2k)+(2k)j,v1+(2k)j,v2+(2k)j,…vk+(2k)j,v(k+1)+(2k)j,…v(2k)+(2k)j},Nk(en-1)={en-2,en-3,…,en-k,vn-1,vn-2,…,vn-k}.
This implies that Nk[D]=V(M(Pn)) for n>2k. Now from the nature of M(Pn), one can observe that every vertex d of D is at a distance at least k+1 apart from every other vertex of D in M(Pn).
Thus by Proposition1, above defined D is a minimal distance k-dominating set of M(Pn). Hence from (18), for n>2k,
(24)γk(M(Pn))={⌊n2k⌋+1forn≡1,2,…,2k-1(mod(2k))n2kforn≡0(mod(2k)).



---

*Source: 795401-2013-12-26.xml*