International Journal of Emerging Trends & Technology in Computer Science (IJETTCS)

Web Site: www.ijettcs.org Email: [email protected]

Volume 6, Issue 2, March - April 2017 ISSN 2278-6856

DISTANCE k-DOMINATION
PARAMETER OF SOME GRAPHS AND
ITS REALISATION
B.Stephen John1, C. T. Brigitha2
1
Associate Professor, Department of Mathematics, Annai velankanni College; Tholayavattam, Tamil Nadu; India.
2
Department of Mathematics, Annai velankanni College; Tholayavattam, Tamil Nadu; India.

ABSTRACT: A set D V is called a distance k-dominating A subset D V(G) is called a distance k-dominating set
set of G if each vertex v V(G) D is within distance k from of G if every vertex in V(G) D is within distance k from
some vertex of D. The distance k-dominating set of the graph G some vertex of D. The minimum cardinality among all
is denoted by Dk(G) and the distance k-domination number of G distance k-dominating set of G is called the distance k-
is denoted by k(G) is the minimum cardinality over all distance
k-dominating sets. In this paper we established a general domination number denoted by k (G).
formulae for finding the k-dominating set of some graphs such Definition:1.5
as (Cn)r, (Pn)r, (Cn Pm) and rth power of the centipede graph Let G be any graph the rth power of G is denoted by Gr
with 2n vertices. and is obtained from G by joining all the vertices vi G
Keywords: Dominating set, Domination number, Distance whose distance is at most r from each vertices of G.
k- dominating set, Tensor Product. Definition: 1.6
The n centipede is the tree on 2n nodes obtained by
1.INTRODUCTION joining the bottoms of n copies of the path graph p2 laid in
Application of domination in graph lies in various fields a row with edges denoted by Cn .
in solving real life problems such as social network Definition: 1.7
theory, land surveying, radio stations, computer The floor and ceiling functions gives us the nearest
communication networks, school bus routing, sets of integer up or down. The symbols for floor and ceiling are
representatives, interconnection networks etc. A graph is like the square brackets [ ] with the top or bottom part
an ordered pair (V,E) where V is a non empty set of missing.
vertices and E is the set of edges, formed by pair of floor (x) ceil (x).
vertices. A subset D V(G) is called a dominating set of G Theorem: 1.8 Let Pn be a path graph with n vertices. If
if every vertex in V(G) D is adjacent to at least one
G = (Pn)r then k(G) = , where 1 r .
vertex of D. The domination number (G) is the Proof: Let Pn be a path graph with n vertices. Let G =
cardinality of the minimum dominating set of G. (Pn)r.
Definition:1.1
A walk of a graph G is an alternating sequence of
vertices and edges v0, e1, v1, e2,
v2,,vn-1,en,vn beginning and ending with vertices such
that each edges ei is incident with vi-1 and vi. A walk is Figure 1.1 (Pn)3
called a path if all its vertices are distinct. A path of n The vertex set of G is denoted by V = {v1,v2,v3,,vn}.
vertices is denoted by Pn. Now divide the vertices of G in to m sets Si, 1 i m such
Definition:1.2 that each set consists of 2rk+1 vertices. Therefore
A closed walk v0, v1, v2,, vn = v0 in which n 3 and S1 = { v1, v2,, v2rk+1}
v0, v1, v2,,vn-1 are distinct is called a cycle. The graph S2 = { v2rk+2, v2rk+3,, v4rk+2}
consisting of a cycle having n vertices is denoted by Cn. S3 = { v4rk+3, v4rk+4,,v8rk+3}
Definition:1.3 . . . . . .
Let G and H be two graphs the tensor product of G and H . . . . . .
. . . . . .
is denoted by G H the vertices of G H is the Sm-1 = { v2(m-2)rk+(m-1) ,,v2(m-1)rk+(m-1)}
cartesian product V(G)V(H) and any two vertices (u,u') Sm = { v2(m-1)rk+m, ,,vn}.
and (v,v') are adjacent in G H iff u' is adjacent with v' Case (i) If n 0 (mod 2rk+1), where 1 r and k is
the k-distance domination of G. Then |S | = 2rk+1,for all
and u is adjacent with v, for all u,v G and u',v' H.
1 i m, then collect all the middle vertices from each Si,
Definition:1.4
1 i m. Therefore, Dk(G) = { v(2rk+1) i - rk / 1 i m}

Volume 6, Issue 2, March April 2017 Page 136

 International Journal of Emerging Trends & Technology in Computer Science (IJETTCS)
Web Site: www.ijettcs.org Email: [email protected]
Volume 6, Issue 2, March - April 2017 ISSN 2278-6856
is the required k- dominating set of G = [since n is a multiple of 2rk+1].
Dk(G)= m Case (ii) If n 0 (mod 2rk+1), where 1 r and k is
= the k-distance domination of G. Then the last partition Sm
containing less than 2rk+1 vertices, choose p =
( )
= [since n is a multiple of 2rk+1].
Case (ii) If n 0 (mod 2rk+1), where1 r and k is Now, Dk(G) = {{v(2rk+1)i - rk / 1 i m-1} {vp}} is the
the k-distance domination of G. Then the last partition Sm required k-dominating set of G andDk(G)= m 1 + 1
containing less than 2rk+1 vertices, choose p = =m
( )
=
Now, Dk(G) = {{v(2rk+1) i - rk / 1 i m-1} {vp}} is the k (G) = .
required k- dominating set of G and Result:1.10 Let G = (Cn)r be the graph with k(G) =
Dk(G)= m 1 + 1 then k(G,p) = k(G,q),where p=q=rk.
=m Proof: We know that k (G) =
= k (G,p) = [ since p = rk]
k (G) = .
= [ since p = q]
Theorem: 1.9 Let Cn be a cycle graph with n vertices. If
G = (Cn)r then k(G) = , where 1 r . = k(G,q).
Theorem: 1.11 Let G = (Cn Pm), m > 1 be the graph with
Proof: Let Cn be a cycle graph with n vertices, Let G =
mn vertices. Then the distance k-domination number of
(Cn)r.
G is k(G) = .
Proof: Let G = (Cn Pm), m > 1 be the graph with mn
vertices is given in (figure 1.3).

Figure 1.2 (Cn)3

The vertex set of G is denoted by V = {v1,v2,v3,,vn}.

Each vertex vi G is adjacent with 2r vertices. Now divide
the vertices of G in to m sets Si, 1 i m such that each set
consists of 2rk+1 vertices. Therefore,
S1 = { v1, v2,, v2rk+1}
S2 = { v2rk+2, v2rk+3,,v4rk+2}
S3 = { v4rk+3, v4rk+4,,v8rk+3}
. . . . . .
. . . . . . Figure 1.3
. . . . . . Now the vertex set of G is denoted by V = {vi,j / 1 i m,
Sm-1 = { v2(m-2)rk+(m-1) ,, v2(m-1)rk+(m-1)} 1 j n}. Each vertex vi G is adjacent with at most 4
Sm = { v2(m-1)rk+m, ,,vn}. vertices that is d(v1,j) = d(vm,j) = 3,1 j n and d(vi,j) = 4,
Case (i) If n 0 (mod 2rk+1), where 1 r and k is 2 i m-1, 1 j n. Now divide the vertices of G into
the k-distance domination of G. Then |S | = 2rk+1,for all m sets Si, 1 i m such that
1 i m, then collect all the middle vertices from each Si, S1 = { vi,j / 1 j n}
1 i m. Therefore, Dk(G) = { v(2rk+1) i -rk / 1 i m S2 = { v2,j / 1 j n}
} is the required k- dominating set of G and S3 = { v3,j / 1 j n}
. . . .
Dk(G)= m
. . . .
= . . . .

Volume 6, Issue 2, March April 2017 Page 137

 International Journal of Emerging Trends & Technology in Computer Science (IJETTCS)
Web Site: www.ijettcs.org Email: [email protected]
Volume 6, Issue 2, March - April 2017 ISSN 2278-6856
Sm-1 = { vm-1,j / 1 j n } = [since n is a multiple of 2rk-1 ].
Sm = { vm,j / 1 j n }. Case (ii) If n 0 (mod 2rk-1), where 1 r and k is
Case (i) If n 0 (mod 4k), where k is the k-distance the k-distance domination of G. Then the last partition Sm
domination of G. Then |S | = n, for all containing less than 2rk-1 vertices, choose
1 i m, then collect all the vertices from each Si, 1 i ( )( )
p=
m as follows: i) Let t = . If m is odd then collect
Now, Dk(G) = {{v(2rk-1)i (rk-1) / 1 i m-1} {vp}} is the
all vertices { vi,t / i = 1,3,5,,m}. ii) If m is even required k-dominating set of G and
then collect all vertices { vi,t +2k / i = 2,4,6,,m}.
Dk(G) = {{ vm,k(4i-3) + 1 / 1 i m , for odd m} { vm,k(4i- Dk(G) = m 1 + 1
1) + 1 / 1 i m ,for even m}} is the required k-dominating
=m
=
set of G and Dk(G) = +
k (G) = .
= m
=
REFERENCES
= [since n is a multiple of 4k]. [1] N. Alon, Transversal numbers of uniform hypergraphs,
Case (ii) If n 0 (mod 4k), where k is the k-distance Graphs Combin. 6(1990), 14.
domination of G. Then the last partition Sm containing less [2] J. Cyman, M. Lemanska and J. Raczek, Lower bound
than n vertices, choose p = on the distance kdomination number of a tree, Math.
Slovaca 56, (2006), 235243.
Dk(G) = {{ vm,k(4i-3) + 1 /1 i m, for odd m}{ vm,k(4i-1) +
[3] A. Hansberg, D. Meierling and L. Volkmann, Distance
1 / 1 i m , for even m}{vmp}} is the required k-
Domination and Distance Irredundance in Graphs, Elec.
dominating set of G and
J. Combin. (2007), R35.
Dk(G)= + +1 [4] J. Harant and A. Pruchnewski, A note on the
=m domination number of a bipartite graph, Annals Combin.
= 5 (2001), 175178.
k (G) = . [5] J.H. Hattingh and M.A. Henning, The ratio of the
distance irredundance and domination numbers of a
Theorem:1.12 Let Cn be the centipede graph with 2n
graph, J. Graph Theory 18 (1994), 19.
vertices. If G = (Cn)r then k(G) = , where 1 r .
r th [6] T.W. Haynes, S. T. Hedetniemi and P. J. Slater,
Proof: Let G = (Cn) be the r power of the centipede Domination in Graphs (Advanced Topics), Marcel
graph with 2n vertices. Dekker, New York, 1998.

Figure 1.4 (Cn)3

The vertex set of G is denoted by V = V1 V2, where V1
={ vi / 1 i n},V2={ ui / 1 i n}.
Now divide the vertices of V1 into m sets Si, 1 i m
such that each set consists of 2rk-1 vertices. Therefore,
S1 = { v1, v2,,v2rk-1}
S2 = { v(2rk-1)+1,v(2rk-1)+2,,v4rk-2}
S3 = { v(4rk-2)+1,v(4rk-2)+2,,v6rk-3}
. . . . .
. . . . .
. . . . .
Sm-1 = { v(m-2) (2rk-1)+1, v(m-2) (2rk-1)+2,,v(m-1) (2rk-1)}
Sm = { v(m-1) (2rk-1)+1, v(m-1) (2rk-1)+1,,vn}.
Case (i) If n 0 (mod 2rk-1), where 1 r and k is
the k-distance domination of G. Then |S | = 2rk-1,for all
1 i m, then collect all the middle vertices from each Si,
1 i m Therefore, Dk(G) = { v(2rk-1)i (rk-1) /1 i
m} is the required k-dominating set of G and
Dk(G) = m
=

Volume 6, Issue 2, March April 2017 Page 138