Dominating Functions in Semigraphs

Dominating Functions in Semigraphs

Shailaja S. Shirkol

Department of Mathematics SDM College of Eng. & Technology

Dharwad, Karnataka, India

Prabhakar. R. Hampiholi

Dept of Mathematics & Research Gogte Institute of Technology Belgaum, Karnataka, India

Meenal M. Kaliwal

Dept of Mathematics & Research

KLS Vishwanathrao Deshpande Rural Institute of Technology Haliyal, Karnataka, India

Abstract:- Let = (, ) be a semigraph. A function

: () {, } and () = () then the function

is a signed adjacent dominating function for the semigraph

if for every vertex , [] . The signed adjacent domination number of a semigraph denoted by () is the minimum weight of a signed adjacent dominating function on . In this paper, we study the properties of signed adjacent dominating function for a class of semigraphs and present their signed adjacenct domination number.

Keywords Dendroids, Semigraphs, Star, Strongly Complete semigraph

1. INTRODUCTION

   The works on Semigraphs by E. Sampathkumar

   [12] introduced the concept of semigraph, which has given scope for emerging trends in the feild of Graph Theory. Domination in Semigraphs has many practical applications such as providing a city with minimum number of security officers, possible light arrangements in the offices, etc. defined the terms such as open adjacent neighbor set, open consecutive adjacent neighbour set, closed adjacent neighbour set, closed consecutive adjacent neighbour set, adjacency domination number and consecutive adjacency domination number of a semigraph. Various parameters of domination in semigraphs such as adjacency domination number, consecutive adjacency domination number was introduced by S.S.Kamath and R.S.Bhat [9]. Strong and weak domination was introduced by S.S.Kamath and Saroja R. Hebbar [10]. S.Gomathi [6] introduced (m,e)- strong domination in semigraphs. Xa-dominating set, Ya- dominating set, Hyperdomination number work was contributed by Y.B.Venkatkrishnan and V. Swaminathan [14].

   In this paper we define signed adjacent dominating function (SADF), signed adjacency domination number (SADN), signed consecutive adjacent dominating function (SCADF) and signed consecutive adjacenct domination number (SCADN) for semigraph. Also find the signed adjacenct domination number for star semigraph, strongly complete semigraphs.

2. PRELIMINARIES

   Definition 2.1 [12] : Semigraph

   A semigraph is a pair = (, ) where is a nonempty set whose elements are called vertices of , and

   is a set of ordered n-tuples, called edges of denoted by

   = (1, 2, . . , ) of distinct vertices, for various 2, satisfying the following conditions: (i) Any two edges have atmost one vertex in common (ii) Two edges (1, 2, , ) and (1, 2, , ) are considered to be equal if and only if (a) = and (b)Either =

   for 1 , or = +1 for 1 . Thus, the edge = (1, 2, , ) is the same as (, 1, , 1). The vertices 1 and are the end vertices of E, while 2, 3, , 1 are called the middle vertices of .

   Definition 2.2 [12] : Subedge

   A subedge of an edge E = (1, 2, , ) is a k- tuple E'= (1 , 2 , , ), where 1 1 < 2 < <

   or 1 < 1 < < 1 .

   Definition 2.2 [12] : Partial edge

   A partial edge of E is a ( + 1)-tuple

   (, ) = (, +1, , ), where 1 . Thus a subedge E' of an edge E is a partial edge if and only if, any two consecutive vertices in E are also consecutive vertices of E.

   Example 2.3:

   1 2 3 4 5 6 7

   Figure 1

   E=(1,2,3,4,5,6,7) is an edge which contains the middle vertices (2,3,4,5,6) and (1,7) as the endvertices. Here E1={1,3,5,7} is a subedge and E2={3,4,5,6,7} is a partial edge.

   Definition 2.4 [12] : fs-edge and fp-edge

   fs-edge is an edge which is either a full edge or a subedge and fp-edge is an edge which is either a full edge or a partial edge.

   Example 2.5: Let = (, ) be a semigraph where

   ={1, 2, 3, 4, 5, 6} and =

   {(1, 2, 3), (1, 6, 5, 4), (2, 4), (3, 4), (3, 6)} as shown in the Figure 2.

   v1 v6

   v1 v1

   v2 v6 v2 v6

   v3 v5 v3 v5

   v2

   v5

   v4

   v3

   Figure 2: Semigraph

   Let G = (V, X) be a semigraph and E=(1, 2, , ) be an edge of G. Then 1 and

   are the end vertices of E and , 2 1 are the middle vertices (or m-vertices) of E. A vertex is an end vertex of G if it appears only as an end vertex. A vertex is a middle vertex of G if it appears only as a middle vertex. A vertex is called middle-cum-end((m,e)) vertex if it is a middle vertex of some edge and an end vertex of some other edge. Two vertices are adjacent if both of them belong to an edge, and two edges are adjacent if they have a common vertex.

   Definition 2.6 [12] : End vertex graph

   The end vertex graph denoted by Ge is a graph in which two vertices in Ge are adjacent if and only if, they are end vertices of an edge in G.

   Definition 2.7 [12] : Adjacency graph

   The adjacency graph denoted by Ga is a graph in which two vertices in Ga are adjacent if and only if, they are adjacent in G.

   Definition 2.8 [12] : Consecutive adjacency graph

   The consecutive adjacency graph Gca is a graph in which two vertices in Gca are adjacent if and only if, they are consecutively adjacent vertices in G.

   v4 v4

   Figure 3: Adjacency graph and Consecutive adjacency graph

   Definition 2.9 [12] : Dendroid

   A star is a dendroid in which all edges have a common vertex.

   Definition 2.10 [12] : Pendant vertex and pendant edge

   A vertex in a semigraph is a pendant vertex if deg = = 1. An edge containing a pendant vertex is a pendant edge.

   Definition 2.11 [12] : Complete and Strongly complete Semigraph

   A semigraph is complete if any two vertices in are adjacent, and strongly complete if is complete and every vertex in appears as an end vertex of an edge.

   Definition 2.12 [9]: Open and Closed Neighbour set

   The set () = { / } is the open adjacent neighbour set and [] = () {} is the closed adjacent neighbour set. Also, () =

   { / } is the consecutive adjacent neighbour set and [] = ()

   {} is the closed consecutive adjacent neighbour set.

   Definition 2.13 [9] : Adjacent and consecutive adjacent dominating set

   A set is said to be an adjacent dominating set if for every , there exists such that is adjacent to in and is a consecutive adjacent dominating set if for every , there exists such that is consecutively adjacent to in .

   Definition 2.14 [9] : Adjacent and consecutive adjacent domination number

   The adjacent domination number () is defined as the minimum cardinality of an adjacent dominating set and the consecutive adjacent domination number () is the minimum cardinality of a consecutive adjacent dominating [9].

   Proposition 2.15 [9] : For any semigraph , () =

   () and () = ( )

3. MAIN RESULTS

   Definition 3.1: Signed adjacent dominating function

   Let = (, ) be a semigraph. A function :

   {1,1} is a signed adjacent dominating function (SADF) if

   [] 1, where [] = [] () .

   Definition 3.2: Signed adjacent domintion number

   Definition 3.7: (m, e)-pendant edge

   A pendant edge of cardinality two containing a (, )-vertex and a pendant vertex is called a (, )- pendant edge.

   Remark 3.8: A star containing an (, )-pendant edge is denoted by .

   Proposition 3.9: For a star containing an (, )-pendant

   The signed adjacent domination number (SADN) of a semigraph is defined by () = min{ ()/ is

   edge, the signed adjacenct domination number

   + 1, where is the number of (, )-pendant ed

   () =

   a signed adjacent dominating function on }

   Definition 3.3: Signed Consecutive adjacent dominating +1

   function

   ges.

   Let = (, ) be a semigraph. A function

   +1

   (m,e)

   : {1,1} is a signed consecutive adjacent

   pendant edge

   dominating function (SCADF) if [] 1, +1

   where [] = [] ().

   Definition 3.4: Signed consecutive adjacent domination +1

   number +1

   The signed consecutive adjacent domination

   number (SCADN) of a semigraph is defined by

   () = min{ ()/ is a signed consecutive

   -1

   +1

   Figure 5

   pendant edge

   adjacent dominating function on }

   As a consequence of the above definitions 3.3 and 3.4 we have the following result.

   Proposition 3.5: Signed consecutive adjacent domination number of a semigraph is equal to the signed domination number of consecutive adjacency graph i,e. () =

   ( ).

   Proof: Let be a star containing atleast one (, )- pendant edge. The end vertex and the (, )-vertex of the pendant edge is assigned with +1, since the satisfying the definition of SADF. The remaining end verticex is assigned with -1. As such if we consider number of (, )- pendant edges, each contributes 1 to the SADN. Hence such number of (, )-pendant edges along with the remaining pendant edge gives () = + 1.

   Proposition 3.10: If 1 is a strongly complete

   Proposition 3.6 : If is a star then

   +1 +1

   +1

   +1

   +1 -1

   () = 1.

   -1

   -1

   -1

   -1

   semigraph of order 3, then

   () = 1, if is odd

   2, if is even

   Proof: Let 1 be a strongly complete semigraph of order

   . The 3 end vertices are assigned with +1. To produce the SADF of weight 1, we assign the remaining 3

   2

   (, ) vertices with -1 and 3 (, ) vertices with +1.

   2

   We have the following two cases:

   1. For = even number we have

      3+ 3 3 = 2

      2 2

      Figure 4

   2. For = odd number we have

   3+ 3 3 = 1

   2 2

   Proof: Let be a star of order . By the definition of a star

   [12], it contains a middle vertex which is common to the rest of the end vertices. Let end vertices be assigned with

   2

   +1 and the remaining 2 end vertices with -1. The only

   vertex left to be assigned with either +1 or -1 is the middle vertex . If () = 1, then [] < 1.Hence() = +1. Therefore, we have () = () = 1.

   -1 -1

   +1

   -1 -1

   +1 +1 +1 +1

   REFERENCES

   1. B.Y.Bam, N.S.Bhave, On Some problems of Graph Theory in Semigraphs, Ph.D Thesis, University of Pune.

   2. J.E.Dunbar, S.T. Hedetniemi, M.A.Henning and P.J. Slater, Signed Domination in Graphs. Graph Theory, Combinatorics, and Applications, Jhon Wiley & Sons, Inc. 1 (1995) 311-312

   3. J.E.Dunbar, S.T. Hedetniemi, M.A.Henning and A.A. McRae, Minus Domination in Regular Graphs. Discrete Math. 49 (1996) 311-312

   4. C.M.Deshpande and Y.S.Gaidhani, Adjacency Matrix of Semigraphs. International Journal of Applied Phy. And Math. (2012), 250-252

   5. D.K.Thakkar and A.A.Prajapati, Vertex covering and independence in semigraph, Annals of Pure and Applied Mathematics, 4(2) (2013) 172-181.

   6. S.Gomathi, R.Sundareswaran and V.Swaminathan, (m,e)-domination in Semigraphs, Electronic Notes in Discrete Mathematics 33 (2009) 75-80

      Figure 6: Strongly complete semigraphs

      Observations:

      Case(i): Let the end vertices be assigned with +1 and the

      (, )-vertices with -1.

      For, = 4 and = 5 the above result holds good. For, > 5 the result does not hold good.

      Case(ii): Let the end vertices be assigned with -1 and

      (, )-vertices with +1.

      For, = 4 and = 5 the above result is not true. For, > 5 the result is true.

4. CONCLUSION

The concept of dominating functions in semigraphs was defined. The signed adjacency domination number was calculated for various classes of semigraphs. We introduced signed consecutive adjacency dominating functions in semigraphs. Another classification of star containing an (m,e) pendant edge was given in this paper. In semigraphs, introducing algorithmic aspects will enrich its existing properties. Further this paper provides scope to establish relationship between Matching and Signed adjacency domination number of semigraphs.

1. T.W.Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Advanced Topics), Marcel Dekker Inc; New York

2. P.R.Hampiholi and J.P.Kitturkar, Strong Circuit matrix and Strong Path matrix, Annals of Pure and Applied Mathematics, Vol. 10, No. 2, 2015, 247- 254

3. S.S. Kamath and R.S.Bhat, Domination in Semigraphs, Electronic notes in Discrete Mathematics 15, 2003, pp. 112.

4. S.S. Kamath and Saroja R. Hebbar, Strong and Weak Domination, Full Sets and Domination Balance in Semigraphs, Electronic notes in Discrete Mathematics 15, 2003, pp. 106-111.

5. Surajit Kr. Nath and P.Das, Matching in Semigraphs, International Journal of computer Application, Issue 3, Volume 6 (November- December 2013).

6. E. Sampathkumar, Semigraphs and Their Applications, Report on the DST Project, May 2000

7. Y.B.Venkatkrishnan and V.Swaminathan, Bipartite theory of Semigraphs, WSEAS Transactions of Mathematics, 11(1), 2012, pp. 1-9

8. Y.B.Venkatkrishnan and V.Swaminathan, Hyper domination in Bipartite Semigraphs, WSEAS Transactions of mathematics, volume 11, 866-875, October 2012.