J Anal https://doi.org/10.1007/s41478-018-0088-3 ORIGINAL RESEARCH PAPER

Non split hop domination number for some mirror graphs and cartesian product of two distinct paths G. Mahadevan1 • V. Vijayalakshmi1 • Selvam Avadayappan2

Received: 31 January 2018 / Accepted: 12 May 2018 Ó Forum D’Analystes, Chennai 2018

Abstract In a graph G ¼ ðV; EÞ let S be the subset of V. A set S  V is a hop dominating set of G, if for every vertex v 2 V  S there exists u 2 S such that d(u,v) = 2. A set S  V is a non split hop dominating set of G if S is a hop dominating set and hV  Si is connected. The minimum cardinality of non split hop dominating set is called non split hop domination number of G and it is denoted by NSHD(G). In this paper we found NSHD number for some mirror graphs and cartesian product of two distinct paths. Keywords Hop domination  Non split hop domination  Mirror graph  Cartesian product Mathematics Subject Classification 05C69

1 Introduction  denote the complement Let G = (V,E) be a simple, undirected, connected graph. G of G. For any two graph G and H let GhH denotes the cartesian product of G and H. & G. Mahadevan [email protected] V. Vijayalakshmi [email protected] Selvam Avadayappan [email protected] 1

The Gandhigram Rural Institute (Deemed to be University), Gandhigram, Tamil Nadu 624 302, India

2

Department of Mathematics, VHNSN College, Virudhunagar, India

123

G. Mahadevan et al. 0

Let G be a graph and G be the copy of G. The Mirror graph M(G) of G is defined as 0 the disjoint union of G and G with additional edges joining each vertex of G to its 0 corresponding vertex in G . It is easy to note that MðGÞ ¼ GhK2 . byc denotes the largest integer less than or equal to y. dye denotes the smallest integer greater than or equal to y. A subset S of V is called a Dominating set of G if every vertex in V  S is adjacent to at least one vertex in S. cðGÞ is the minimum cardinality taken over all dominating sets in G which is called the domination number of G. If hV  Si is connected then S is said to be Non split dominating set of G. The minimum cardinality taken over all non split dominating set is the non split domination number and is denoted by cns ðGÞ. C. Natarajan, S.K. Ayyaswamy introduced the concept of Hop dominating set [4]. A set S  V of a graph G is a Hop dominating set of G if for every v 2 V  S there exists u 2 S such that d(u, v) = 2. The minimum cardinality of a hop dominating set is called a hop domination number and it is denoted by ch ðGÞ . A vertex u in a hop dominating set is said to hop dominate an another vertex v if d(u, v) = 2. G.Mahadevan, V. Vijayalakshmi, C. Sivagnanam introduced the concept of Non split hop dominating set [5]. S  V is a Non split hop dominating set of G if S is a hop dominating set and hV  Si is connected. The minimum cardinality of non split hop dominating set is called non split hop domination number of G and it is denoted by NSHD(G). It is clear that NSHDðGÞ  2 for any graph G. x2

x1 x6

x5

x8 x7

x13

x10 x11

x9 x14

x15

y1

x4

x3

y2

y5

x12 y6

y7

x16 y3

G

y4 H

For example in the above figure for the graph G, Nonsplit hop dominating set = fx1 ; x4 ; x6 ; x7 ; x10 ; x11 g; NSHD(G) = 6 and for the graph H, Nonsplit hop dominating set = fy1 ; y5 g and NSHD(H) = 2.

2 Some results on NSHD number Theorem 1 In a graph G if there exist two adjacent vertices u and v such that dðuÞ ¼ n  2 and dðvÞ ¼ 1. Then NSHDðGÞ ¼ 2: Proof Since dðuÞ ¼ n  2 there exists a vertex w which is not adjacent to u. Take S ¼ fv; wg then S is a NSHD-set and hence NSHDðGÞ ¼ 2:

123

Non split hop domination number

Theorem 2 For given r, 2  r  n, any connected graph G is an induced subgraph of a graph H for which NSHDðHÞ ¼ r: Proof Consider any connected graph G with n vertices. Then the vertices of G will be parititioned into r  n partitions. Name that partitions as Xi where 1  i  r: Let Kr be the complete graph with the vertices fy1 ; y2 ; . . .yr g. Now construct a new graph H from G [ Kr by joining each yi to all vertices of Xi for 1  i  r . Clearly all the vertices of Kr is the NSHD-set and NSHDðHÞ ¼ r: Theorem 3

For the mirror graph MðPn Þ, 8 2n > þ1 > > > 5 > > > > 2ðn þ 4Þ > > > > 5 > > < 2ðn þ 3Þ NSHDðMðPn ÞÞ ¼ > 5 > > > > 2ðn þ 2Þ > > > > > 5 > > > > : 2ðn þ 1Þ 5

if n  0ðmod5Þ; if n  1ðmod5Þ; if n  2ðmod5Þ; if n  3ðmod5Þ; if n  4ðmod5Þ;

Proof Let VðPn Þ = fa1 ; a2 ; . . .an g. Clearly VðMðPn ÞÞ = fa1 ; a2 ; . . .an ; b1 ; b2 ; . . .bn g and EðMðPn ÞÞ EðPn Þ [ fbi biþ1 [ aj bj : 1  i  n  1; 1  j  ng. Let S1 = fai ; aiþ1 ; bj ; bjþ1 : i  2ðmod10Þ ; j  7ðmod10Þg and 8 S1 if n  3; 4ðmod5Þ; > > > < S [ fa g if n  0ðmod5Þ; n is even; 1 n let S ¼ > S [ fb g if n  0ðmod5Þ; n is odd; n > > 1 : S1 [ fan ; bn g if n  1; 2ðmod5Þ;

=

It is clear that S is a NSHD-set of MðPn Þ and hence 8 2n > þ1 if n  0ðmod5Þ; > > > 5 > > > > 2ðn þ 4Þ > > if n  1ðmod5Þ; > > 5 > > < 2ðn þ 3Þ NSHDðMðPn ÞÞ  if n  2ðmod5Þ; > 5 > > > > 2ðn þ 2Þ > > if n  3ðmod5Þ; > > > 5 > > > > : 2ðn þ 1Þ if n  4ðmod5Þ; 5

123

G. Mahadevan et al.

Let S be any NSHD-set of MðPn Þ. Since any vertex fai g in MðPn Þ hop dominates ai2 ; bi1 and itself. Similarly fbi g in MðPn Þ hop dominates bi2 ; ai1 and itself. By this way fai ; aiþ1 g hop dominates fai1 ; ai2 ; aiþ3 ; bi ; bi1 ; biþ2 g. 8 S1 if n  3; 4ðmod5Þ; > > > < S1 [ fan g if n  0ðmod5Þ; n is even; Then clearly S > S1 [ fbn g if n  0ðmod5Þ; n is odd; > > : S1 [ fan ; bn g if n  1; 2ðmod5Þ; 8 2n > þ1 > > > 5 > > > > 2ðn þ 4Þ > > > > 5 > > < 2ðn þ 3Þ Thus NSHDðMðPn ÞÞ  > 5 > > > > 2ðn þ 2Þ > > > > > 5 > > > > : 2ðn þ 1Þ 5

if n  0ðmod5Þ; if n  1ðmod5Þ; if n  2ðmod5Þ; if n  3ðmod5Þ; if n  4ðmod5Þ;

which proves the theorem. Theorem 4

For the mirror graph Pn of a path Pn , NSHDðMðPn ÞÞ ¼ 2, for n  4:

Proof Let VðPn Þ ¼ fa1 ; a2 ; . . .an g: Clearly = fa1 ; a2 ; . . .an ; b1 ; b2 ; . . .bn g and EðM ðPn ÞÞ = VðM ðPn ÞÞ fai bi ; ai aj ; bi bj : 1  i  n, j 6¼ i  1g: Let S = fa1 ; b1 g: Then clearly S is an NSHD set of MðPn Þ and hence NSHD(MðPn Þ) = 2. Theorem 5

For any n  3, MðPn Þ of a path Pn , 8 n > < d e if n is odd; NSHDðMðPn ÞÞ ¼ n 2 > : þ1 if n is even; 2

Proof Let VðPn Þ = fa1 ; a2 ; . . .an g. Clearly VðMðPn ÞÞ = fa1 ; a2 ; . . .an ; b1 ; b2 ; . . .bn g and EðMðPn ÞÞ ¼ fai aj ; bi bj ; ai bk : 1  i; j; k  n, j 6¼ i  1; k 6¼ i } . Let S1 = fai ; bj : i  1ðmod4Þ , j  3ðmod4Þg and 8 if n is odd; > < S1 [ S 2 let S ¼ S1 [ S2 [ fan g if n  0 ðmod4Þ; > : S1 [ S2 [ fbn g if n  2 ðmod4Þ;

123

Non split hop domination number

It is clear that S is a NSHD-set of MðPn Þ and hence 8 n > < d e if n is odd; NSHDðMðPn ÞÞ  n 2 > : þ1 if n is even; 2 Let S be any NSHD-set of MðPn Þ. For a vertex fai g , dMðPn Þ ðai ; xÞ ¼ 1 for any x in fbi ; aiþ1 ; ai1 g. Therefore dMðPn Þ ðai ; xÞ ¼ 2. By this way we choose vertices fai ; bj : i  1ðmod4Þ, j  3ðmod4Þg. If n is odd jSj  dn2e. If n is even there is no vertex to hop dominate either an or bn . With out loss of generality assume that an is not hop dominated. In this case we include an in S. Then jSj  n2 þ 1 for n is even. Theorem 6

For the mirror graph MðCn Þ of a cycle Cn 8 2n > > if n  0ðmod10Þ; > > 5 > > > > 2n > > þ1 if n  5ðmod10Þ; > > > 5 > > > > 2ðn þ 4Þ > > if n  6ðmod10Þ; > > 5 > > < 2ðn þ 3Þ NSHDðMðGÞÞ ¼ if n  2; 7ðmod10Þ; > 5 > > > > 2ðn þ 2Þ > > if n  3; 8ðmod10Þ; > > 5 > > > > 2ðn þ 1Þ > > > if n  4; 9ðmod10Þ; > > 5 > > > > > : 2ðn  1Þ þ 1 if n  1ðmod10Þ 5

Proof Let VðCn Þ = fa1 ; a2 ; . . .an ; a1 g. Clearly VðMðCn ÞÞ = fa1 ; a2 ; . . .an ; b1 ; b2 ; . . .bn g and EðMðCn ÞÞ ¼ EðCn Þ [ fbi biþ1 ; aj bj : 1  i  n  1, 1  j  ng. Let S1 = fai ; aiþ1 ; bj ; bjþ1 : i  2ðmod10Þ, j  7ðmod10Þg and let 8 S1 if n  0; 3; 4; 8; 9ðmod10Þ; > > > < S [ fa g if n  7ðmod10Þ; 1 n S¼ > S1 [ fbn g if n  1; 2; 5ðmod10Þ; > > : S1 [ fan ; bn g if n  6ðmod10Þ: It is clear that S is a NSHD-set of MðCn Þ and hence

123

G. Mahadevan et al.

8 2n > > > > 5 > > > > 2n > > þ1 > > > 5 > > > > 2ðn þ 4Þ > > > > 5 > > < 2ðn þ 3Þ NSHDðMðCn ÞÞ  > 5 > > > > 2ðn þ 2Þ > > > > 5 > > > > 2ðn þ 1Þ > > > > > 5 > > > > 2ðn  1Þ > : þ1 5

if n  0ðmod10Þ; if n  5ðmod10Þ; if n  6ðmod10Þ; if n  2; 7ðmod10Þ; if n  3; 8ðmod10Þ; if n  4; 9ðmod10Þ; if n  1ðmod10Þ

Let S be any NSHD-set of MðCn Þ. Since any vertex fai g in MðCn Þ hop dominates ai2 ; bi1 and itself. Similarly fbi g in MðCn Þ hop dominates bi2 ; ai1 and itself. By this way fai ; aiþ1 g hop dominates fai1 ; ai2 ; aiþ3 ; bi ; bi1 ; biþ2 g. Then clearly 8 S1 if n  0; 3; 4; 8; 9ðmod10Þ; > > > < S [ fa g if n  7ðmod10Þ; 1 n S > S [ fb g if n  1; 2; 5ðmod10Þ; n > > 1 : S1 [ fan ; bn g if n  6ðmod10Þ: 8 2n > > > 5 > > > > > 2n > > þ1 > > > 5 > > > > 2ðn þ 4Þ > > > > 5 > > < 2ðn þ 3Þ Thus NSHDðMðCn ÞÞ  > 5 > > > > 2ðn þ 2Þ > > > > 5 > > > > 2ðn þ 1Þ > > > > > 5 > > > > 2ðn  1Þ > : þ1 5

if n  0ðmod10Þ; if n  5ðmod10Þ; if n  6ðmod10Þ; if n  2; 7ðmod10Þ; if n  3; 8ðmod10Þ; if n  4; 9ðmod10Þ; if n  1ðmod10Þ

which proves the theorem. Theorem 7 n  5.

For the mirror graph of Cn of a cycle Cn , NSHDðMðCn ÞÞ ¼ 2, for

Proof Let VðCn Þ= fa1 ; a2 ; . . .an g. Clearly VðM ðCn ÞÞ = fa1 ; a2 ; . . .an ; b1 ; b2 ; . . .bn g and EðM ðCn ÞÞ = fai bi ; ai aj ; bi bj :

123

Non split hop domination number

1  i  n , j 6¼ i  1g. Let S = fa1 ; b1 g . Then clearly S is an NSHD set of MðCn Þ and hence NSHD(MðCn Þ) = 2. 8n > if n  0ðmod4Þ; > > < 2n þ1 if n  2ðmod4Þ; Theorem 8 For any n  3, NSHDðMðCn ÞÞ ¼ > 2 > n > :d e if n  1; 3ðmod4Þ: 2 Proof Let VðCn Þ= fa1 ; a2 ; . . .an g. Clearly VðMðCn ÞÞ = fa1 ; a2 ; . . .an ; b1 ; b2 ; . . .bn g and EðMðCn ÞÞ = fai aj ; bi bj ; ai bk : 1  i; j; k  n, j 6¼ i  1; k 6¼ ig. Let S1 = fai ; bj : i  1ðmod4Þ , j  3ðmod4Þg and  S1 if n  0; 1; 3ðmod4Þ; let S ¼ S1 [ fbn g if n  2ðmod4Þ: It is clear that S is a NSHD-set of MðCn Þ and hence 8n > if n  0ðmod4Þ; > > > < 2n þ1 if n  2ðmod4Þ; NSHDðMðCn ÞÞ  > 2 > > > : d ne if n  1; 3ðmod4Þ: 2 Let S be any NSHD-set of MðCn Þ. For a vertex fai g , dMðCn Þ ðai ; xÞ ¼ 1 where x = fbi ; ai1 g. Therefore that three vertices in x has distance dMðCn Þ ðai ; xÞ ¼ 2. By this way choose vertices fai g where i  1ðmod4Þ and fbi g where i  3ðmod4Þ. Thus clearly  S1 if n  0; 1; 3ðmod4Þ; S S1 [ fbn g if n  2ðmod4Þ: 8n > > > > < 2n þ1 Hence NSHDðMðCn ÞÞ  > 2 > > > : d ne 2

if n  0ðmod4Þ; if n  2ðmod4Þ; if n  1; 3ðmod4Þ:

Thus the result follows. Theorem 9 for n  1.

For the mirror graph of a complete graph Kn , NSHDðMðKn ÞÞ ¼ 2,

Proof Let VðKn Þ= fu1 ; u2 ; . . .un g: Clearly VðMðKn ÞÞ = fu1 ; u2 ; . . .un ; v1 ; v2 ; . . .vn g and EðMðKn ÞÞ = fui uj ; vi vj ; ui vi : 1  i; j  n , j 6¼ ig. Let S = fu1 ; v1 g: Then clearly S is an NSHD set of MðKn Þ and hence NSHD(MðKn Þ) = 2.

123

G. Mahadevan et al.

Theorem 10

NSHDðMðKn ÞÞ ¼ 2, for n  3.

Proof Let VðKn Þ= fu1 ; u2 ; . . .un g: Clearly VðMðKn ÞÞ = fu1 ; u2 ; . . .un ; v1 ; v2 ; . . .vn g and EðMðKn ÞÞ = fui vj : 1  i; j  n , j 6¼ ig. Let S = fu1 ; v1 g: Then clearly S is an NSHD set of MðKn Þ and hence NSHDðMðKn ÞÞ ¼ 2. Observation 1. If G = ðMðPn ÞÞ, then hG  Si is a mirror graph of complement of a path where S is a NSHD set. Observation 2. If G = ðMðPn ÞÞ, then hG  Si is complement of mirror graph of a path where S is a NSHD set. Observation 3. If G = ðMðCn ÞÞ, then hG  Si is a mirror graph of complement of a cycle where S is a NSHD set. Observation 4. If G = ðMðCn ÞÞ, then hG  Si is complement of mirror graph of a cycle where S is a NSHD set. Observation 5. If G = MðKn Þ, then hG  Si is a mirror graph of a complete graph where S is a NSHD set. Observation 6. If G = ðMðKn ÞÞ then hG  Si is a complement of mirror graph of a complete graph where S is a NSHD set. Observation 7. NSHD-set does not exist for the graph, Kn Kn MðKn Þ and for any n  1.

3 NSHD number of Pm hPn In this section we find the exact value of the NSHD number of the product graph Pm hPn . Let Pm be a path with m vertices fx1 ; x2 ; . . .xm g . By the definition of hop domination, each xi can hop dominate exactly two vertices xi 2 where 3  i  n-1 and the remaining vertices can hop dominate only one vertex each. Let the vertices of Pm hPn be fx11 ; x21 ; . . .xn1 ; x12 ; x22 ; . . .xn2 ; . . .x1m ; x2m ; . . .xnm g. 8 n > < if n  0ðmod4Þ; Proposition 1 NSHD (Pm h Pn ) = 2n þ 1 > :d e if n  1; 2; 3ðmod4Þ 2 where m ¼ 2 or 3; n  m: Proof

let S1 ¼ fx2j : j  2; 3ðmod4Þg. 8 1 2 fx2 ; x2 g > > > < S [ fxn g 1 1 Take S ¼ n n > S [ fx > 1 1 ; x2 g > : S1

if n ¼ 2; 3; if n  1ðmod4Þ; if n  2ðmod4Þ; if n  0; 3ðmod4Þ;

Clearly S is a NSHD-set of Pm h Pn where m = 2,3.

123

Non split hop domination number

 Proposition 2

NSHD(P4 h Pn ) =

2r 2r þ 1

if n ¼ 3r  2; if n ¼ 3r or 3r  1:

where n  4 Proof

Let S1 ¼ fx14 ; xi2 ; x3j : i  2; 3ðmod6Þ; j  0; 5ðmod6Þg. 8 S1 [ fx44 g if n ¼ 4; > > > > 1 3 > if n ¼ 5; > < S1  fx4 g [ fx4 g Let S ¼ S1 if n  0ðmod4Þ; > > n > > S1 [ fx1 g if n  1; 2ðmod6Þ; > > : S1 [ fxn4 g if n  4; 5ðmod6Þ;

Clearly S is a NSHD-set of P4 h Pn . Proposition 3

NSHD (P5 h Pn ) = n for all n  5:

Proof Let S ¼ fx22 ; x32 ; x25 ; x35 g [ fxi3 : 5  i  ng: Clearly S is a NSHD-set of P5 h Pn for all n  5: Proposition 4

NSHD(P7 h Pn ) = n?2 for all n  7:

j 1 i Proof 8 Let S1n ¼ fx5 ; x2 ; x6 : 1  i; j  n; i  2; 3ðmod4Þ; j  0; 1ðmod4Þg and let if n  0ðmod4Þ; < S1 [ fx5 g if n  1; 2ðmod4Þ; S = S1 [ fxn3 g : S1 [ fxn7 g if n  3ðmod4Þ; Clearly S is a NSHD-set of P7 h Pn for all n  7:

For the value m ¼ 6 or 9 or 12 and m  n 8 mn > if m ¼ 6 or 9 or 12; n  0ðmod4Þ; > > 6 > > > mn m > > > d eþb c if m ¼ 9; n  1; 3ðmod4Þ; > > 6 > < mn m 6 þ if m ¼ 6 or 12; n  1; 3ðmod4Þ; NSHDðPm hPn Þ ¼ > 6 6 > > mn m > > > þd e if m ¼ 9; n  2ðmod4Þ; > > 6 15 > > > mn m > : þd eþ1 if m ¼ 6 or 12; n  2ðmod4Þ; 6 15

Proposition 5

Proof Let S1 ¼ fxij : i  2ðmod3Þ; j  2; 3ðmod4Þ; 1  i  12; 1  j  ng. Let S2 ¼ S [ fxni : i  2; 3; 7; 8ðmod12Þ; 1  i  12g. Let S3 ¼ fxni : i  3; 4ðmod6Þ; 1  i  12g and

123

G. Mahadevan et al.

8 S1 > > > > > > < S1 [ S3 Let S ¼ S1 [ fxn3 ; xn4 ; xn9 g > > > S2 > > > : n S2 [ fxn1 m ; xm g

if m ¼ 6 or 9 or 12; n  0; 3ðmod4Þ; if m ¼ 6 or 12; n  1ðmod4Þ; if m ¼ 9; n  1ðmod4Þ; if m ¼ 9; n  2ðmod4Þ; if m ¼ 6 or 12; n  2ðmod4Þ;

Clearly S is a NSHD-set of Pm h Pn for all n  m where m ¼ 6 or 9 or 12. For 15  m  n, 8 mðn  1Þ 2m n > > þ þb c > > > 9 3 3 > > > > mðn  2Þ 2m n > > þ þb cþ1 > > 9 3 3 > > > > mn m m þ n 3 > > þd eþ > > > 9 6 3 > > > mn m n > > þ þ > > 9 2 3 > > > > mðn þ 3Þ m > > > þb c < 9 2 NSHDðPm hPn Þ ¼ mðn þ 3Þ m þ2 > > þ > > > 9 2 > > > > mðn þ 2Þ 2m > > þ > > 9 3 > > > > mðn þ 2Þ 2m > > > þ þ2 > > 9 3 > > > > mðn þ 1Þ n m > > þd eþ > > > 9 3 3 > > > > mðn þ 1Þ 2m > : þ þ3 9 3

Theorem 11

if n  1ðmod6Þ; if n  2ðmod6Þ; if n  0ðmod6Þ; m  odd; if n  0ðmod6Þ; m  even; if n  3ðmod6Þ; m  odd; if n  3ðmod6Þ; m  even; if n  4ðmod6Þ; m  odd; if n  4ðmod6Þ; m  even; if n  5ðmod6Þ; m  odd; if n  5ðmod6Þ; m  even

where m  0ðmod3Þ. Proof Let S1 = fx11 ; xki ; xlj : i  3(mod 6), j  0(mod 6), k  2,3(mod 6), l  0,5(mod 6), 1  i; j  m, 1  k; l  ng, let S2 = fx1i ; x2i : i  0(mod 6), 1  i  mg, let S3 = fxni : i  0(mod 6), 1  i  mg, let S4 = fxn1 : i  0(mod 6), 1  i  mg, let S5 = i fxn1 ; xni : i  0(mod 6), 1  i  mg, let S6 = fxn1 ; xn1 : i  0(mod 6), 1  i  mg, let 1 i n n S7 = fxi : i  3(mod 6), 9  i  mg, let S8 = fxi : i  3(mod 6), 1  i  mg, let S9 = : i  3(mod 6), 1  i  mg, let S10 = fx1j : j  0,5(mod 6), 1  j  ng. fxn1 i Case 1: n  0ðmod6Þ: In this case S1 [ S2 [ S7 [ S10 is the NSHD-set of Pm h Pn : Case 2: n  1ðmod6Þ In this case S1 [ S2 [ S8 [ S9 [ S10 is the NSHD-set of Pm h Pn : Case 3: n  2ðmod6Þ: In this case S1 [ S2 [ S9 [ S10 is the NSHD-set of Pm h Pn .

123

Non split hop domination number

Case 4: n  3ðmod6Þ: In this case S1 [ S2 [ S3 [ S10 is the NSHD-set of Pm h Pn : Case 5: n  4ðmod6Þ: In this case S1 [ S2 [ S4 [ S5 [ S10 is the NSHD-set of Pm h Pn : Case 6: n  5ðmod6Þ: In this case S1 [ S2 [ S6 [ S10 is the NSHD-set of Pm h Pn : 8 S1 [ S2 [ S7 [ S10 if n  0ðmod6Þ; > > > > > S1 [ S2 [ S8 [ S9 [ S10 if n  1ðmod6Þ; > > > if n  3ðmod6Þ; > > S1 [ S2 [ S3 [ S10 > > > S [ S [ S [ S [ S if n  4ðmod6Þ; > 1 2 4 5 10 > : S1 [ S2 [ S6 [ S10 if n  5ðmod6Þ; It is clear that S1 is a NSHD-set of Pm hPn and hence 8 mðn  1Þ 2m n > > þ þb c if n  1ðmod6Þ; > > 9 3 3 > > > mðn  2Þ 2m n > > > þ þb cþ1 if n  2ðmod6Þ; > > 9 3 3 > > > mn m mþn3 > > þd eþ if n  0ðmod6Þ; m  odd; > > 9 6 3 > > > mn m n > > þ þ if n  0ðmod6Þ; m  even; > > 9 2 3 > > > mðn þ 3Þ m > > þb c if n  3ðmod6Þ; m  odd; < 9 2 NSHDðPm hPn Þ ¼ mðn þ 3Þ m þ 2 > > þ if n  3ðmod6Þ; m  even; > > 9 2 > > > mðn þ 2Þ 2m > > > þ if n  4ðmod6Þ; m  odd; > > 9 3 > > > mðn þ 2Þ 2m > > þ þ2 if n  4ðmod6Þ; m  even; > > > 9 3 > > > mðn þ 1Þ n m > > þd eþ if n  5ðmod6Þ; m  odd; > > 9 3 3 > > > > : mðn þ 1Þ þ 2m þ 3 if n  5ðmod6Þ; m  even 9 3 where m  0ðmod3Þ; 15  m  n. Theorem 12

For 10  m  n,

123

G. Mahadevan et al.

8 ðm  1Þn m þ n  1 m > > þ þd e > > 9 3 6 > > > > n m1 m > ðm  1Þðn  1Þ > > þb cþ þd e > > 9 3 3 6 > > > > > dmne þ m  1 þ dne > > > > 9 3 3 > > > > ðm  1Þn m mþnþ2 > > þd eþ > > 9 6 3 > > > > ðm  1Þðn þ 2Þ m n > > > þd eþd e > > 9 6 3 > > > > ðm  1Þðn þ 1Þ m  1 n > > þ þd eþ1 < 9 3 3 NSHDðPm hPn Þ ¼ > ðm þ 2Þn m > > þ 3d e > > 9 6 > > > > ðm þ 2Þðn  1Þ m > > > þ 3d e > > 9 6 > > > > ðm þ 2Þðn  2Þ m > > þ 4d e > > > 9 6 > > > > ðm þ 2Þðn þ 3Þ m > > þd e > > 9 6 > > > > m > ðm þ 2Þðn þ 2Þ > > þd e > > 9 6 > > > > > : ðm þ 2Þðn þ 1Þ þ 2dme 9 6

if n  0ðmod6Þ; m  odd; if n  1ðmod6Þ; m  odd; if n  2ðmod6Þ; m  odd; if n  3ðmod6Þ; m  odd; if n  4ðmod6Þ; m  odd; if n  5ðmod6Þ; m  odd; if n  0ðmod6Þ; m  even; if n  1ðmod6Þ; m  even; if n  2ðmod6Þ; m  even; if n  3ðmod6Þ; m  even; if n  4ðmod6Þ; m  even; if n  5ðmod6Þ; m  even

where m  1ðmod3Þ: Proof Let S1 = fx11 ; xki ; xlj : i  1(mod 6), j  4(mod 6), k  4,5(mod 6), l  1,2(mod 6), 1  i; j  m, 1  k; l  ng, let S2 = fx1i : i  1(mod 6), 1  i  mg, let S3 = fxni : i  4(mod 6), 1  i  mg, let S4 = fxn1 : i  4(mod 6), 1  i  mg, let S5 = i fxni : i  1(mod 6), 1  i  mg, let S6 = fxn1 : i  1(mod 6), 1  i  mg, i Case 1: n  0ðmod6Þ: In this case S1 [ S2 [ S3 [ S4 is the NSHD-set of Pm h Pn : Case 2: n  1ðmod6Þ In this case S1 [ S2 [ S4 is the NSHD-set of Pm h Pn : Case 3: n  2ðmod6Þ: In this case S1 [ S2 [ S5 is the NSHD-set of Pm h Pn : Case 4: n  3ðmod6Þ: In this case S1 [ S2 [ S5 [ S6 is the NSHD-set of Pm h Pn : Case 5: n  4ðmod6Þ: In this case S1 [ S2 [ S6 is the NSHD-set of Pm h Pn : Case 6: n  5ðmod6Þ: In this case S1 [ S2 [ S3 is the NSHD-set of Pm h Pn :

123

Non split hop domination number

8 S1 [ S2 [ S3 [ S4 > > > > S1 [ S2 [ S4 > > < S1 [ S2 [ S5 Now let S1 ¼ S1 [ S2 [ S5 [ S6 > > > > S [ S 2 [ S6 > > : 1 S1 [ S2 [ S3

if if if if if if

n  0ðmod6Þ; n  1ðmod6Þ; n  2ðmod6Þ; n  3ðmod6Þ; n  4ðmod6Þ; n  5ðmod6Þ;

It is clear that S1 is a NSHD-set of Pm hPn and hence 8 ðm  1Þn m þ n  1 m > > þ þd e > > 9 3 6 > > > > n m1 m > ðm  1Þðn  1Þ > > þb cþ þd e > > 9 3 3 6 > > > > > dmne þ m  1 þ dne > > > > 9 3 3 > > > > ðm  1Þn m mþnþ2 > > þd eþ > > 9 6 3 > > > > ðm  1Þðn þ 2Þ m n > > > þd eþd e > > 9 6 3 > > > > ðm  1Þðn þ 1Þ m  1 n > > þ þd eþ1 < 9 3 3 NSHDðPm hPn Þ ¼ > ðm þ 2Þn m > > þ 3d e > > 9 6 > > > > ðm þ 2Þðn  1Þ m > > > þ 3d e > > 9 6 > > > > ðm þ 2Þðn  2Þ m > > þ 4d e > > > 9 6 > > > > ðm þ 2Þðn þ 3Þ m > > þd e > > 9 6 > > > > m > ðm þ 2Þðn þ 2Þ > > þd e > > 9 6 > > > > > : ðm þ 2Þðn þ 1Þ þ 2dme 9 6

if n  0ðmod6Þ; m  odd; if n  1ðmod6Þ; m  odd; if n  2ðmod6Þ; m  odd; if n  3ðmod6Þ; m  odd; if n  4ðmod6Þ; m  odd; if n  5ðmod6Þ; m  odd; if n  0ðmod6Þ; m  even; if n  1ðmod6Þ; m  even; if n  2ðmod6Þ; m  even; if n  3ðmod6Þ; m  even; if n  4ðmod6Þ; m  even; if n  5ðmod6Þ; m  even

where m  1ðmod3Þ; 10  m  n Theorem 13

For

8  m  n,

123

G. Mahadevan et al.

NSHDðPm hPn Þ ¼

8 ðm þ 1Þn m n > > þ 3b c þ > > 9 6 3 > > > > ðm þ 1Þðn þ 2Þ m n > > > þb cþb c > > 9 6 3 > > > > ðm þ 1Þðn þ 1Þ m n > > þ 2b c þ b c > > > 9 6 3 > > > > > ðm þ 1Þn þ 2dme þ bmc þ bn  1c > > > 9 6 6 3 > > > > ðm þ 1Þðn þ 2Þ m n > > > þb cþd e > > 9 6 3 > > > > ðm þ 1Þðn þ 1Þ ðm  11Þ m n > > þ þb cþd e > > < 9 6 6 3

ðm þ 1Þn m n > þ 3b c  1 þ > > 9 6 3  > >  > > ðm þ 1Þðn  1Þ m m8 n > > > þ 2d e þ þb c > > 9 6 6 3 > >   > > > ðm þ 1Þðn  2Þ m m  8 n > > þ 2d e þ 2 þb c > > > 9 6 6 3 > >   > > ðm þ 1Þðn þ 3Þ m m  8 > > > þ 2b c þ > > 9 6 6 > >   > > > ðm þ 1Þðn þ 2Þ m  8 n > > þ þd e > > > 9 6 3 > >   > > > ðm þ 1Þðn þ 1Þ m  8 n > : þ2 þd e 9 6 3

if n  0ðmod6Þ; m  odd; if n  1ðmod6Þ; m  odd; if n  2ðmod6Þ; m  odd; if n  3ðmod6Þ; m  odd; if n  4ðmod6Þ; m  odd; if n  5ðmod6Þ; m  odd; if n  0ðmod6Þ; m  even; if n  1ðmod6Þ; m  even; if n  2ðmod6Þ; m  even; if n  3ðmod6Þ; m  even; if n  4ðmod6Þ; m  even; if n  5ðmod6Þ; m  even;

where m  2ðmod3Þ; . Proof

Let S1 = fxki ; xlj : i  3(mod 6), j  0(mod 6), k  1,2(mod 6), l  4,5(mod

6), 1  i; j  m, 1  k; l  ng, let S2 = fx1j : j  4,5(mod 6), 1  j  ng, let S3 = fxmj : j  4,5(mod 6), 1  j  ng, let S4 = fxmj : j  1,2(mod 6), 1  j  ng, let S5 = fx1i : i  0(mod 6), 1  i  m  3g, let S6 = fxni : i  0(mod 6), 1  i  m  3g, let S7 = fxn1 : i i  0(mod 6), 1  i  m  3g, let S8 = fxn1 ; xni : i  0(mod 6), 1  i  mg, let S9 = n1 fxn1 : i  0(mod 6), 1  i  mg, let S10 = fxni : i  3(mod 6), 9  i  m  3g, let 1 ; xi n1 S11 = fxi : i  3(mod 6), 9  i  m  3g, let S12 = fxni : i  3(mod 6), 1  i  mg, let S13 = fxn1 : i  3(mod 6), 1  i  mg. i Case 1: n  0ðmod6Þ: Subcase a) m is odd. In this case S1 [ S2 [ S3 [ S5 [ S11 [ S12 is the NSHD-set of Pm h Pn : Subcase b) m is even. In this case S1 [ S2 [ S4 [ S5 [ S11 [ S12 [ fxnm g is the NSHD-set of Pm h Pn : Case 2: n  1ðmod6Þ Subcase a) m is odd. In this case S1 [ S2 [ S3 [ S5 [ S13 is the NSHD-set of Pm h Pn : Subcase b) m is even. In this case S1 [ S2 [ S4 [ S5 [ S13 [ fxn1 m g is the NSHD-set of Pm h Pn : Case 3: n  2ðmod6Þ:

123

Non split hop domination number

Subcase a) m is odd. In this case S1 [ S2 [ S3 [ S5 [ S6 is the NSHD-set of Pm h Pn : Subcase b) m is even. In this case S1 [ S2 [ S4 [ S5 [ S6 is the NSHD-set of Pm h Pn : Case 4: n  3ðmod6Þ: Subcase a) m is odd. In this case S1 [ S2 [ S3 [ S5 [ S7 [ S8 [ fxnm g is the NSHD-set of Pm h Pn : Subcase b) m is even. In this case S1 [ S2 [ S4 [ S5 [ S7 [ S8 is the NSHD-set of Pm h Pn : Case 5: n  4ðmod6Þ. Subcase a) m is odd. In this case S1 [ S2 [ S3 [ S5 [ S9 [ fxn1 m g is the NSHD-set of Pm h Pn : Subcase b) m is even. In this case S1 [ S2 [ S4 [ S5 [ S9 is the NSHD-set of Pm h Pn : Case 6: n  5ðmod6Þ: Subcase a) m is odd. In this case S1 [ S2 [ S3 [ S5 [ S10 is the NSHD-set of Pm h Pn : Subcase b) m is even. In this case S1 [ S2 [ S4 [ S5 [ S10 is the NSHD-set of Pm h Pn : 8 if n  0ðmod6Þ; m  odd; S1 [ S2 [ S3 [ S5 [ S11 [ S12 > > > > > S [ S [ S [ S [ S if n  1ðmod6Þ; m  odd; > 1 2 3 5 13 > > > > S1 [ S2 [ S3 [ S5 [ S6 if n  2ðmod6Þ; m  odd; > > > > n > > S [ S [ S [ S [ S [ S [ fx g if n  3ðmod6Þ; m  odd; 2 3 5 7 8 > m > 1 > n1 > > S1 [ S2 [ S3 [ S5 [ S9 [ fxm g if n  4ðmod6Þ; m  odd; > > > S1 [ S2 [ S4 [ S5 [ S11 [ S12 [ fxm g if n  0ðmod6Þ; m  even; > > > > n1 > S [ S [ S [ S [ S [ fx g if n  1ðmod6Þ; m  even; > 1 2 4 5 13 m > > > > S1 [ S2 [ S4 [ S5 [ S6 if n  2ðmod6Þ; m  even; > > > > > S [ S [ S [ S [ S [ S if n  3ðmod6Þ; m  even; > 1 2 4 5 7 8 > > > > S1 [ S2 [ S4 [ S5 [ S9 if n  4ðmod6Þ; m  even; > > > : S1 [ S2 [ S4 [ S5 [ S10 if n  5ðmod6Þ; m  even; It is clear that S1 is a NSHD-set of Pm hPn and hence

123

G. Mahadevan et al. 8 ðm þ 1Þn m n > > þ 3b c þ > > 9 6 3 > > > > ðm þ 1Þðn þ 2Þ m n > > > þ b cþb c > > 9 6 3 > > > > ðm þ 1Þðn þ 1Þ m n > > þ 2b c þ b c > > > 9 6 3 > > > > > ðm þ 1Þn þ 2dme þ bmc þ bn  1c > > > 9 6 6 3 > > > > ðm þ 1Þðn þ 2Þ m n > > > þ b c þ d e > > 9 6 3 > > > > ðm þ 1Þðn þ 1Þ ðm  11Þ m n > > þ þb cþd e > > < 9 6 6 3 NSHDðPm hPn Þ ¼ ðm þ 1Þn m n > þ 3b c  1 þ > > 9 6 3  > >  > > ðm þ 1Þðn  1Þ m m8 n > > > þ 2d e þ þb c > > 9 6 6 3 > >   > > > ðm þ 1Þðn  2Þ m m  8 n > > þ 2d e þ 2 þb c > > > 9 6 6 3 > >   > > ðm þ 1Þðn þ 3Þ m m8 > > > þ 2b c þ > > 9 6 6 > >   > > > ðm þ 1Þðn þ 2Þ m  8 n > > þ þd e > > > 9 6 3 > >   > > > ðm þ 1Þðn þ 1Þ m8 n > : þ2 þd e 9 6 3

if n  0ðmod6Þ; m  odd; if n  1ðmod6Þ; m  odd; if n  2ðmod6Þ; m  odd; if n  3ðmod6Þ; m  odd; if n  4ðmod6Þ; m  odd; if n  5ðmod6Þ; m  odd; if n  0ðmod6Þ; m  even; if n  1ðmod6Þ; m  even; if n  2ðmod6Þ; m  even; if n  3ðmod6Þ; m  even; if n  4ðmod6Þ; m  even; if n  5ðmod6Þ; m  even;

where m  2ðmod3Þ; n  m  8: The value of NSHD(Pm hPn ) for 6  m; n  19 is shown in the following Table 1:

Table 1 Nonsplit Hop Domination number for Cartesian product of two distinct paths m/ n

6

7

8

9

10

11

12

13

14

15

16

17

18

19

6

8

8

8

10

12

12

12

14

16

16

16

18

20

20

9

10

11

12

13

14

15

16

17

18

19

20

21

12

15

16

16

18

20

20

23

24

24

26

28 30

7 8 9 10 11 12 13 14 15 16 17 18 19

123

15

16

18

18

21

22

24

24

27

28

18

20

22

22

24

26

26

28

30

30

21

23

25

26

29

31

31

33

35

24

28

30

32

32

36

38

40

27

30

33

33

35

37

37

32

35

37

38

41

43

37

40

41

43

47

39

42

45

45

45

48

50

51

54 52

Non split hop domination number Funding No funding. Compliance with ethical standard Conflict of interest The authors have no conflict of interest. Ethical approval Not applicable. Informed consent Not applicable.

References 1. Haynes, T., S. Hedetniemi, and P. Slater. 1998. Fundamentals of domination in graphs. New York: Marcel Dekker. 2. Kulli, V.R., and B. Janakiram. 2000. The non split domination number of a graph. Indian journal of pure and applied mathematics. 31 (4): 441–447. 3. Mahadevan, G., V. Vijayalakshmi, and C. Sivagnanam. 2017. Non split hop domination in graphs. Global Journal of Pure and Applied Mathematics 13 (3): 0973–1768. 4. Natarajan, C., S. K. Ayyaswamy. 2015. Hop domination in graphs I., An. St. Univ. ovidius Constanta, VERSITA 23(2): 187-199. 5. Samu Alanko, Simon Crevals, Anton Isopoussu, Patric Ostergard, Ville Pettersson. 2011. Computing the domination number of grid graphs. The Electronic Journal of Combinatorics. 18.

123