The Cycle non Split Domination Number of Fuzzy Graphs

The Cycle non Split Domination Number of Fuzzy Graphs

C. Y. Ponnappan1

1 Department of Mathematics , Government Arts College Paramakudi, Tamilnadu,India

P. Surulinathan2

2Department of Mathematics, Lathamathavan Engineering college, Kidaripatti, Alagarkovil, Madurai-625301, Tamilnadu,India.

S. Basheer Ahamed3

3Department of Mathematics,

P.S.N.A. College of Engineering and Technology, Dindigul,Tamilnadu,India.

Abstract A dominating set D of a fuzzy graph G=( ,µ) is a cycle non split dominating set if the induced fuzzy subgraphH=(<V- D>,,µ) is a cycle. The cycle non split domination number cns(G)of G is the minimum fuzzy cardinality of a cycle non split dominating set. In this paper we study a cycle non split dominating sets of fuzzy graphs and investigate the relationship of cns(G) with other known parameters of G.

Keywords Fuzzy graphs, Fuzzy domination, Split fuzzy domination number, Non Split fuzzy domination number, cycle non split domination number.

Subject classification No. 05C72, 05C75

1. INTRODUCTION

   Kulli V.R. et.alintroduced the concept ofsplit domination and non-split domination in graphs [3]. Rosenfield introduced the notion of fuzzy graph and several fuzzy analogs of graph theoretic concepts such as path,cycles and connectedness[10].A.Somasundram and S.Somasundram discussed domination inFuzzy graphs[11]. MahyoubQ.M.and Sonar N.D.discussed the split domination number of fuzzy graphs[6].Ponnappan C.Y and et. al. discussed the strong non split domination number of fuzzy graphs [9]. In this paper we discuss the cycle non split domination number of fuzzy graph and obtained the relationshipwith other knownparametersof G.

2. PRELIMINARIES

   Definition:2.1 [2]

   Let G=(V,E) be a graph. A subset D of V is called a dominating set in G if every vertex in V-D is adjacent to some vertex in D. The domination number of G is the minimum cardinatliy taken over all dominating sets in G and is denoted by (G).

   Definition:2.2 [3]

   A dominating set D of a graph G=(V,E) is a split dominating set if the induced subgraph<V-D>is disconnected. The split domination number s(G) of a graph G is the minimum cardinality of a split dominating set.

   Definition:2.3 [3]

   A dominating set D of a graph G=(V,E) is a non split dominating set if the induced subgraph<V-D>is connected. The non split domination number ns(G) of a graph G is the minimum cardinality of a non split dominating set.

   Definition:2.4 [4]

   A dominating set D of a graph G=(V,E) is a cycle non split dominating set if the induced subgraph<V-D>is a cycle. The cycle non split domination number cns(G) of a graph G is the minimum cardinality of a cycle non split dominating set.

   Definition:2.5 [4]

   A dominating set D of a graph G=(V,E) is a path non split dominating set if the induced subgraph <V-D>is a path. The path non split domination number pns(G) of a graph G is the minimum cardinality of a path non split dominating set.

   Definition : 2.6 [10]

   Let V be a finite non empty set. Let E be the collection of all two element subsets of V. A fuzzy graph G=(,µ) is a set with two functions :V[0,1] and µ: E[0,1] such that µ({u ,v})(u)(v) for all u,v V.

   Definition : 2.7 [11]

   Let G=( ,µ) be a fuzzy graph on V and V1 V. Define 1 on V1 by 1(u)=(u)for all u V1 and µ1 on the collection E1 of two element subsets of V1 by µ1({u ,v}) =

   µ({u ,v}) for all u,v V1, then (1,µ1) is called the fuzzy subgraph of G induced by V1 and is denoted by <V1>.

   Definition : 2.8 [11]

   The fuzzy subgraph H=(V1,1,1) is said to be a spanning fuzzy subgraph of G=(V,,) if 1(u)=(u) for all uV1 and 1(u,v)(u,v) for all u,vV. Let G (V,,) be a fuzzy graph and1 be any fuzzy subset of , i.e. , 1(u)(u) for all u.

   Definition : 2.9 [11]

   Let G=(,) be a fuzzy graph on V. Let u,vV. We say that u dominates v in G if ({u,v})=(u)(v). A subset D of V is called a dominating set in G if for every vD, there exists uD such that u dominates v. The minimum fuzzy cardinality of a dominating set in G is called the domination number of G and is denoted by (G) or .

   Definition : 2.10 [6]

   A dominating set D of a fuzzy graph G=(,µ) is a split dominating set if the induced fuzzy subgraph H=(<V- D>,,µ) is disconnected.

   The split domination number () of G is the minimum fuzzy cardinality of a split dominating set.

   Definition : 2.11 [6]

   A dominating set D of a fuzzy graph G=(,µ) is a non split dominating set if the induced fuzzy subgraph H=(<V-D>,',µ') is connected.

   The non split domination number() of G is the minimum fuzzy cardinality of a non split dominating set.

   Definition : 2.12

   A dominating set D of a fuzzy graph G=(,µ) is a

   Definition : 2.17 [11]

   Let :V[0,1] be a fuzzy subset of V. Then the complete fuzzy graph on is defined to be (,) where

   ({u,v})=(u)(v) for all uvE and is denoted by K.

   Definition : 2.18 [11]

   A fuzzy graph G=(,µ) is said to be bipartite if the vertex V can be partitioned into two nonempty sets V1 and V2 such that µ(v1,v2)=0 if v1,v2V1 or v1,v2V2. Further if

   (u,v)=(u) (v) for all uV1 and vV2 then G is called a

   complete bipartite graph and is denoted by 1 ,2 where 1

   and 2 are, respectively, the restrictions of to V1 and V2.

   Definition : 2.19 [11]

   A dominating set D of a fuzzy graph G is said to be a minimal dominating if no proper subset D of D is dominating set of G such that |D|<|D|.

3. MAIN RESULTS

Proposition : 1

For any complete fuzzy graph K then

() = () = min{()/}

Proposition :2

cycle non split dominating set if the induced fuzzy subgraph

For fuzzy bipartite graph

, ,

H=(<V-D>,',µ') is a cycle.

1 2

( )

The cyclenon split domination number () is the minimum fuzzy cardinality of a cyclenon split dominating set.

Definition : 2.13

(1,2 ) = min{

vV2

Proposition :3

u } + min{

(v)} , where u

V1 and

A dominating set D of a fuzzy graph G=(,µ) is a path non split dominating set if the induced fuzzy subgraphH=(<V-D>,',µ') is a path.

The path non split domination number () is the minimum fuzzy cardinality of a path non split dominating set.

Definition : 2.14[11]

The order p and size q of a fuzzy graph G=(,µ) are defined to be p=uV(u) and q=(u ,v)E µ({u ,v}).

Definition : 2.15 [11]

An edge e={u ,v} of a fuzzy graph is called an effective edge if µ({u ,v}) = (u) (v).

N(u) = { vV/ µ({u ,v}) = (u) (v)} is called the neighborhood of u and N[u]=N(u) {u} is the closed neighborhood of u.

The effective degree of a vertex u is defined to be the sum of the weights of the effective edges incident at u and is denoted by dE(u). () ()is called the neighborhood degree of u and is denoted by dN(u). The minimum effective degree E(G)=min{dE(u)|uV(G)} and the maximum effective degree E (G) = max{dE(u)|uV(G)}.

Definition : 2.16 [11]

The complement of a fuzzy graph G denoted by is defined to be = (, ) where ({, }) = ()()

({, }).

For fuzzy wheelcns(G)=(u)such that u is the spoke of the wheel.

Proposition :4

cns( G K1)= (ui).whereui is the pendant vertices

i

of the corona and G contains atleast one cycle.

Proposition :5

The cycle non plit dominating set exists for Petersen graph and Davidson graph.

Note :

The cycle non split dominating set does not exists for path, tree and fan.

Theorem : 1

For any fuzzy graph G=(,µ), () ()<p

Proof

Let G=(,µ) be a fuzzy graph. Let D be the minimum dominating set. Dcns is the fuzzy cycle non split dominating set. Dcns is also a dominating set but need not be a minimum fuzzy dominating set.

Therefore we get |D||Dcns|

That is () ().

Example : Fig. (i)

u2 (0.2)

Proof

Let G=(,µ) be a fuzzy graph and let H = (,µ) be

u1 (0.5)

0.3

0.1 0.2

0.4

0.3

u3 (0.3)

0. 3

the fuzzy spanning sub graph of G. Dcns(G) be the fuzzy minimum cycle non-split dominating set of G. Dcns(H) is fuzzy cycle non-split dominating set of H but not minimum.

Therefore () ().

Example:

Spanning fuzzy sub graph H of G (Fig (ii))

u5 (0.3)

0.2

u4 (0.4)

u1(0.5)

u2 (0.4)

0.4

0.3

u5 (0.3)

u6(0.2)

D={u3,u5}, () = 0.6

Dcns={u1,u2},() = 0.7

Theorem 1.1

() () < .

Theorem :2

For any fuzzy graph G=(,µ),

() min{(), ()}

Proof :

Let G=(,µ) be a fuzzy graph. D be the minimum fuzzy dominating set. LetDs and Dcns the minimum fuzzy split dominating set and minimum fuzzy cycle non split dominating set of G respectively. The cardinality of fuzzy dominating set need not exceeds either one of the minimum of cardinality of fuzzy split dominating set or fuzzy cycle non split dominating set.

0.3

u3 0.3 u4

(0.3) Fig. (i) (0.6)

() = 0.7, () = 1.0

Theorem 3.1() ().

Theorem : 4

Let G be a complete fuzzy graphkthen

cns(G) = min {(u)}, where u is the vertex having minimum cardinality.

Let Gi is subgraph of G induced by<V-u> where u is the vertex of minimum cardinality,Gi has a vertex set Vi = {V- u} then

Therefore |D| min {|Ds|, |Dcns|}

Hence () min {(), ()}

cns(G) cns (G1) cns (G2) cns (Gn) provided the fuzzy graph Gn is a elementary cycle with three vertices.

example :Fig. (ii)

u2 (0.4)

0.4

0.4

0.3

u5 (0.3)

0.2

Example :Fig.(iii)

u1(0.1)

0.1 0.1

0.3 0.2 0.1

u (0.2)

u1 (0.5)

0.3

0.3

0.3

u6(0.2)

u5 (0.5) 2

0.1

u3(0.3)

0.3

Fig. (i)

u4(0.6)

0.2

0.4 0.2 0.3 0. 2

0.3

Here D = {u3,u5} = {1, 6}, Ds = {u2,u3,u4}

() = 0.6, () = 0.7, () =1.3

u4 (0.4)

u3 (0.3)

Theorem 2.1 () min {(), ()}

Theorem : 3

For any spanning fuzzy sub graph

= (, µ)of G=(,µ),

() ()

() = () = 0.1

G is a fuzzy graph induced by <V-u1>

cns (G1) = (u2) = 0.2

cns(G) cns(G1).

Theorem : 5

For any fuzzy graph without isolated vertices

cns(G) p/2.

Proof :

Any graph without isolated vertices has two disjoint dominating sets and hence the result follows.

Example :Fig.(iv)

Theorem 8.1.pns – set satisfies ores theorem. Theorem : 9

For the domination number cnsthe following theorem gives a Nordhaus Gaddum type result.

For any fuzzy graph G, cns (G) + cns ( G ) 2p.

Proof :

v1 (0.2)

(0.2)

v2 (0.2)

(0.2)

v3 (0.2)

Let G be a connected fuzzy graph it may or may not contains a cycle.

Suppose G contains a cycle then by theorem cns (G) p.

Also G may or may not contains a cycle. We have

v6 (0.2)

(0.2)

cns ( G ) p or cns ( G ) = 0

(0.2) (0.2)

Vice versa. Hence the inequality is trivial.

v5(0.2)

Dcns (G) = {v1,v4}

< V Dcns> is a cycle p = 1.2, cns(G) = 0.4

cns(G) p/2

Theorem : 6

(0.2)

(0.2)

(0.2)

v4 (0.2)

Theorem 9.1pns (G) + pns ( G ) 2p.

ACKNOWLEDGEMENT

Thanks are due to the referees for their valuable comments and suggestions.

REFERENCES

1. Harary, E., 1969. Graph Theory. Addison Wesley, Reading, MA.

   Proof :

   For any fuzzy graph, cns (G) p – E

   Let v be a vertex of a fuzzy graph, such that

   McAlester, M.L.N., 1988. Fuzzy intersection graphs. Comp. Math. Appl. 15(10), 871-886.

2. Haynes, T.W., Hedetniemi S.T. and Slater P.J. (1998). Fundamentals of domination in graphs, Marcel Dekker Inc. New York, U.S.A.

3. Kulli, V.R. and Janakiram B. (1997). The non split domination number

   dN(v) = E, then V\N(v) is a dominating set of G, so that

   cns (G) | V \ N(v)| = P E.

   Example :

   From fig. (iv) p = 1.2, E = 0.6, cns (G)=0.4 Theorem : 7

   For any non trivial connected fuzzy graph G,

   (G) + pns(G) p and this bound this sharp, the path P4 and cycle C4 achieve this bound.

   Theorem :8

   A cycle non split dominating set D of G=(,µ) is minimal if and only if for each vD one of the following two conditions holds

   1. N(v)Dcns=

   2. there is a vertex uV-Dcns such that N(u)Dcns={v}

      of graph. Graph Theory notes of New York. New York Academy of Sciences, XXXII, pp. 16-19.

4. Kulli, V.R. and Janakiram B. (2000). The non-split domination number of graph. The Journal of Pure and Applied Math. 31(5). Pp. 545-550.

5. Kulli, V.R. and Janakiram B. (2003). The strong non-split domination number of a graph. International Journal of Management and Systems. Vol. 19, No. 2, pp. 145-156.

6. MahioubQ.M.andSoner N.D.(2007), The split domination number of fuzzy graph Accepted for publication in Far East Journal of Applied Mathematics.

7. MordesonJ.N.andNairP.S. Fuzzy Graph and Fuzzy Hypergraph Physica-Verilog, Heidelberg (2001).

8. Ore, O. (1962). Theory o Graphs. American Mathematical Society Colloq. Publi., Providence, RI, 38.

9. PonnappanC.Y,Surulinathan .P,BasheerAhamed .S, The strong non split domination number of fuzzy graphs International Journal of Computer & Organization Trends Volume 8 Number 2 May 2014.

10. Rosenfeld, A., 1975. Fuzzy graphs. In :Zadeh, L.A., Fu, K.S., Shimura,

    M. (Eds.), Fuzzy Sets and Their Applications. Aca-demic Press, New York.

11. Somasundaram, A., and Somasundaram, S., Domination in fuzzy graphs, Pattern Recognit. Lett. 19(9) 1998), 787-791.

Proof :

Let D be a minimal cycle non split dominating set

and vD, then D=D-{v} is not a cycle non-split dominating set and hence there exist uV-D such that u is not dominated by any element of D. If u=v we get (i) and if uv we get (ii). The converse is obvious.