 Open Access
 Total Downloads : 435
 Authors : Dr. Shailaja S. Shirkol, Dr. Prabhakar R. Hampiholi, Smt. Meenal M. Kaliwal
 Paper ID : IJERTV5IS020004
 Volume & Issue : Volume 05, Issue 02 (February 2016)
 DOI : http://dx.doi.org/10.17577/IJERTV5IS020004
 Published (First Online): 01022016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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

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. Xadominating 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.

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 ntuples, 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] : fsedge and fpedge
fsedge is an edge which is either a full edge or a subedge and fpedge 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 mvertices) 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 middlecumend((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 () = ( )

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:

For = even number we have
3+ 3 3 = 2
2 2
Figure 4

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 with2
+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

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

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) 311312

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

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

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

S.Gomathi, R.Sundareswaran and V.Swaminathan, (m,e)domination in Semigraphs, Electronic Notes in Discrete Mathematics 33 (2009) 7580
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.


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.

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

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

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

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. 106111.

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

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

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

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