The Clique Neighbourhood Domination Number in Graphs

The Clique Neighbourhood Domination Number in Graphs

1. Mohanaselvi1

   1Assistant Professor of Mathematics, Nehru Memorial College, Puthanampatti, Tiruchirappalli-621 007.

   1. Nandhini2

      2Assistant Professor of Mathematics, Kongunadu College Of Engineering and Technology,

      Thottiyam, Tiruchirappalli-621 007.

      Abstract – A dominating set ()of graph G=(V,E) is a clique neighbourhood dominating set (cln-set) of G, if D is a clique dominating set of G and dominating set of N(G). The clique neighbourhood domination number is the minimum cardinality taken over all clique neighbourhood dominating sets of G and is denoted by (). In this paper, () are obtained for some standard graphs.

      Key words: Domination number, Clique domination number, Neighbourhood domination number, Clique Neighbourhood Domination number.

      1. INTRODUCTION

         In this paper, G=(V,E) is a finite, undirected, simple, connected graph. In general the graph has p vertices and q edges. Terms not defined here are used in the sense of Harary[1]. The complement of G is the graph with vertex set V in which two vertices are adjacent iff they are not adjacent in G. Degree of a vertex v is denoted by d(v). The maximum(minimum) degree of a graph G is denoted by ()(()). A vertex v is said to be isolated vertex if d(v)=0.

         A set () of a graph G=(V,E) is a dominating set of G, if every vertex in V\D is adjacent to some vertex in D. The domination number () of G is the minimum cardinality of a dominating set of G. This concept was introduced by Ore in [6].

         The concept of clique domination number was introduced by Cozzers and Kelleher in [2], in which a set () is said to a dominating clique, if the induced subgraph <D> is a complete graph. The clique domination number () of G is the minimum cardinality of a dominating clique.

         In [3],S.V. Siva Rama Raju, I.H. Nagaraja Rao introduced the concept of global neighbourhood domination number as follows: A set () is called a global neighbourhood dominating set(gnd-set), if G is a dominating set for both G and N(G), where N(G) is the neighbourhood graph of G. The global neighbourhood domination number () is the minimum cardinality of a global neighbourhood dominating set of G.

         In this paper, we introduced the clique neighbourhood domination by combining the concept of clique domination and global neighbourhood domination for a connected graph. The characteristics was studided and the exact value of the parameter was found for some standard graphs.

      2. MAIN RESULTS

         Definition 2.1

         A dominating set ()of graph G=(V,E) is a clique neighbourhood dominating set (cln-set) of G, if D is a clique dominating set of G and dominating set of N(G). The clique neighbourhood domination number is the minimum cardinality taken over all clique neighbourhood dominating sets of G and is denoted by ().

         Example :2.2

         v1 v4 v1 v4

         G1: N(G1):

         v2 v3 v2 v3

         Figure 2.1 Figure 2.2

         For the graph G1, figure 2.1&2.2, the vertex set D={v2} is the – set and hence (1) = 1 . And also the clique domination, global domination is 1. (1) = (1) = (1) = 1

         Theorem: 2.3

         1 , 3

         For the complete graph ,() = {2 , = 2

         Proof:

         Let G be a complete graph with atleast 1 vertex.

         Case (i): n=2

         Since the vertex set V(G) itself is a , -set of G and hence () = |()| which proves the result Case(ii): 3

         Let () be the maximum degree in G then the set = {} forms a clique neighbourhood set of G. Hence () || = 1 (1)

         Let S be the -set of G. The domination set in N(G) must contain atleast one vertex in N(G). Hence the -set has atleast one vertex.

         () = || 1 (2)

         The result follows from (1) and (2)

         Example

         In the below example K5, A vertex set D = {v1} is a minimum clique neighborhood dominating set. Therefore (5) = 1.

         v1 v2 v1 v2

         v5 v3 v5 v3 v4 v4

         5 N(5)

         Theorem: 2.4

         For the complete bipartite graph ,, (,) = 2 for m, n2

         Proof:

         Let G be a complete bipartite graph with atleast 3 vertices and let the vertex set of G is () =

         {1, 2, , , 1, 2, , }.

         Let () has the maximum degree in G and be any vertex adjacent to in G then the set = {, } forms a clique neighbourhood set of G.

         Hence () || = 2 (1)

         Let S be the -set of G. Since N(G) contains two complete components, then for the domination of N(G), S must contain atleast one vertex from each component. Hence S has atleast two vertices.

         Therefore () = || 2 (2) The result follows from (1) and (2).

         Example u1

         u1 u2

         v3 u2

         v1 v2 v3 v2 v1

         2,3 N(2,3)

         In the above example K2,3, A vertex set D = {u1 , v1} is a minimum clique neighborhood dominating set. Therefore (2,3) = 2

         Theorem: 2.5

         For star graph K1,n, (1,) = 2 for n2.

         Proof:

         Let G be a star graph 1, with atleast 3 vertices and () = {, 1, 2, , }.be the vertex set of G.

         Let () has the maximum degree in G, and be any vertex adjacent to in G then the set = {, } forms a

         clique neighbourhood set of G.

         Hence () || = 2 (1)

         Let S be the -set of G. The dominating set in N(G) must contain atleast one isolated vertex and one maximum degree vertex in N(G). Hence the clique neighbourhood set must contain atleast 2 vertices.

         Therefore () = || 2 (2)

         The result follows from (1) and (2).

         Example

         v1 u1 v1

         v5 u1 v2 v5 v2

         v4 v3 v4 v3

         1,5 N(1,5)

         In the above example K1,5,

         A vertex set D = {u1,v1} is a minimum clique neighborhood dominating set, therefore (1,5) = 2

         Theorem: 2.6

         For the Wheel , () = 1, 2.

         Proof:

         Let G be a wheel graph with atleast 3 vertices and () = {, 1, 2, , } be the vertex set of G.

         Let () has the maximum degree in G, then the set = {} forms a clique neighbourhood set of G. Hence () || = 1 (1)

         Let S be the -set of G. The dominating set in N(G) must contain atleast one vertex in N(G) and hence the clique neighbourhood set has atleast 1 vertex.

         Hence () = || 1 (2)

         The result follows from (1) and (2) Example u

         v1 v2 v1 v2 u

         v5 v3 v5 v3

         v4 v4

         5 N(5)

         In the above example W5,

         A vertex set D = {u} is a minimum clique neighborhood dominating set. Therefore (5) = 1

         Theorem: 2.7

         For the fan , () = 1, for n2. Proof:

         Let G be a fan graph with atleast 3 vertices and () = {, 1, 2, , } be the vertex set of G.

         Let () has the maximum degree in G then the set = {} forms a clique neighbourhood set of G.

         Hence () || = 1 (1) Let S be the

         -set of G. The dominating set in N(G) must contain atleast one vertex in N(G) and hence the clique neighbourhood set has atleast 1 vertex.

         Therefore () = || 1 (2)

         The result follows from (1) and (2)

         Example

         • u u

         v1 v3 v2 v4

         v4 v1

         4 N(4)

         v3 v2

         In the above example F4, A vertex set D = {u} is a minimum clique neighborhood dominating set. Therefore (4) = 1

         Theorem: 2.8

         For the banana tree , , (,) = 2 for n2.

         Proof:

         Let G be a banana tree with atleast 6 vertices and () = {, , 1, 2, ,, 1, 2, , } be the vertex set of G. Let , () such that d(u)=d(v)= () in G then the set = {, } forms a clique neighbourhood set of G.

         Hence () || = 2 (1)

         Let S be the -set of G. Since N(G) contains two complete components, then for the domination of N(G) , S must contain atleast one vertex from each component. Hence S has atleast two vertices.

         Therefore () = || 2 (2)

         The result follows from (1) and (2).

         u1 v1 u1 v1

         u v u v N(B2,2)

         2,2

         u2 v2 u2 v2

         In the above example 2,2, A vertex set D = {u,v} is a minimum clique neighborhood dominating set. Therefore (2,2) = 2

         Theorem: 2.9

         For the book graph , () = 2 for n2.

         Proof:

         Let G be a book graph with atleast 6 vertices and () = {, , 1, 2, , , 1, 2, , } be the vertex set of G. Let , () such that d(u)=d(v)= () in G then the set = {, } forms a clique neighbourhood set of G.

         Hence () || = 2 (1) Let S be the -set of G. Since N(G) contains two complete components, then for the domination of N(G) , S must contain atleast one vertex from each component. Hence S has atleast two vertices.

         Therefore () = || 2 (2) From (1) and (2) the result follows.

         Example N(3)

         u3

         v3 u

         u2

         3: v2 u1

         1. u1

         2. v1 v1 u2

            v2

            v3 v u3

            In the above example B3, A vertex set D = { u, v} is a minimum clique neighborhood dominating set, therefore (3) = 2

            Theorem: 2.10

            For the n-barbell graph,() = 2 , for n2.

            Proof:

            Let G be a n-barbell graph with atleast 6 vertices and () = {, , 1, 2, , , 1, 2, , } be the vertex set of G. Let , () such that d(u)=d(v)= () in G then the set = {, } forms a clique neighbourhood set of G.

            Hence () || = 2 (1)

            Let S be the -set of G. Since N(G) contains two complete components, then for the domination of N(G) , S must contain atleast one vertex from each component. Hence S has atleast two vertices.

            Therefore () = || 2 (2)

            From (1) and (2) the result follows. Example

            v2 v1 u2 u3

            v3 v5 u1 u4

            G

            v4 u5

            v1 u5

            v2 u4

            v3 u3

            v4 u2

            v5 u1 N(G)

            In the above example 5-barbell graph,

            A vertex set D= {u1, v1} is a minimum clique neighborhood dominating set, therefore () = 2

            Theorem: 2.11

            3

            For the friendship graph, () = 1 , for m 2.

            Proof:

            Let G be a friendship graph with atleast 5 vertices and () = {, 1, 2, , } be the vertex set of G. Let () has the maximum degree in G then the set = {} forms a clique neighbourhood set of G.

            Hence () || = 1 (1)

            Let S be the -set of G. The dominating set in N(G) must contain atleast one vertex in N(G) and hence the clique neighbourhood set has atleast 1 vertex.

            Therefore () = || 1 (2)

            The result follows from (1) and (2)

            Example:

            v2 v3 u

            v1 v4 v6 v1

            • u

         v6 v5

         v5 v2

         v4 v3

         3 (3)

         3 3

         3

         In the above example 3

         The vertex set S = {u} is a minimum clique neighbourhood dominating set. Therefore () = 1.

      3. CONCLUSION

In this paper, we found the exact values of clique neighbourhood domination number for Complete graph, Complete bipartite graph, Star graph, Wheel graph, Fan graph, Banana tree, Book graph, n-barbell graph, Friendship graph.

REFERENCES

1. F. Harary, Graph theory,Addison Wesley Reading Mass,1969.

2. M.B. Cozzers and L.L. Kelleher, Dominating cliques in graphs, Discrete Math. 86(1990) 101-116.

3. S.V. Siva Rama Raju, I.H. Nagaraja Rao, Global neighbourhood domination, Proyescciones Journal of Mathematics. Vol 33, pp 25-41, March 2014.

4. T.W. Haynes, S.T.Hedetniemi and P.J. Slater, Fundamentals of Domination in graphs, Marcel Dekker, Inc, Newyork(1998).

5. V.R. Kulli, Theory of Domination in graphs, Vishwa International Publication, Gulbarga India(2010).

6. O.Ore, Theory of graphs, Amer.Math.Soc.Colloq.Publ.,38, Providence,(1962).