Properties of Bondage Arcs

Properties of Bondage Arcs

R. Jahir Hussain1

1 Associate Professor of Mathematics, Jamal Mohamed College, Trichy,Tamil Nadu,

India.

R. M. Karthik Keyan2

2Research Scholar of Mathematics, Jamal Mohamed College,

Trichy, Tamil Nadu, India.

Abstract:- In this paper, we de ne the non-bondage number bn( G ) for any fuzzy graph and de ne fuzzy strong line graph. A characterization is obtained for fuzzy strong line graphs Ls(G) such that Ls(G) is tree . A necessary condition for a fuzzy double strong line graph of cycle is a fuzzy trees and the exact value of bn(G) for any graph G is found. Moreover we de ne neighbourhood extension also analysis it extendable by using bondage arcs and relationships between bn(G) and b.

Keywords: (G)Minimum dominating set , maximum non-bondage number bn(G) , minimum bondage number b(G); Ls(G) is strong line graph,Ls(G) is double strong line grpah .GE neigh-bour extendable

1. Introduction

   Fuzzy graph theory was introduced by A. Rosenfeld [8] in 1975. Fuzzy graph theory is now finding numerous applications in modern science and technology especially in the fields of neural networks, expert systems, information theory, cluster analysis, medical diagnosis, control theory, etc. Sunil Mathew, Sunitha M.S [10] has obtained the fuzzy graph-theoretic concepts like f- bonds, paths, cycles, trees and connectedness and established some of their properties.

   V.R. Kulli and B. Janakiram [7] have established the non-bondage number of a graph. First we give the definitions of basic concepts of fuzzy graphs and define the non-bondage and it is properties. All graphs consider here are finite, undirected, distinct labeling with no loop or multi arc and p nodes and q (fuzzy) arcs. Any undefined term in this paper may be found in Harary[5]. Among the various applications of the theory of domination that have been

   considered, the one that is perhaps most often discussed concerns a communication network. Such a network consists of existing communication links between a fixed set of sites. The problem is to select a smallest set of sites at which to place transmitters so that every site in the network that does not have a transmitter is joined by a direct communication link to one that does have a transmitter. This problem reduces to that of finding a minimum dominating set in the graph corresponding to the network. This graph has a node representing each site and an arc between two nodes iff the corresponding sites have a direct communications link joining them. To minimize the direct communication links in the network, we introduce the following section.

2. Preliminaries

   is denoted by G), = (V, E), where V = {uEV : (u) > 0} and E = {(u, v)EV × v : µ(u, v) > 0}.

   A fuzzy subset of a non-empty set V is a mapping : V [0, 1]. A fuzzy relation on V is a fuzzy subset of E(V × V ). A fuzzy graph G = (, µ) is a pair of function : V [0, 1] and µ : V ×V [0, 1], where µ(u, v) (u)(v)for all u, v EV . The underlying crisp graph of G=(, µ)

   The order P =

   veD (v). The graph G = (, µ) isdenoted by G, if unless otherwise mentioned.

   Let be a fuzzy graph on. The degree of a vertex u is dG(u) = ), µ(uv). The minimum degree

   (u

   v)

   (u

   v)

   { }

   of G is (G) = d(G)(u), vEV and the maximum degree of G is (G) = d(G)(u), EV The

   strength of connectedness between two nodes u and v in a fuzzy graph G is define as the maximum of the strength of all paths between u and v and is denoted by CON NG(u, v). A u-v path P is called a strongest path if its strength equals CON NG(u, v). The fuzzy graph H = (, ) is called a fuzzy sub graph of G if (x) (x)for all xEV and (x, y) (x, y) for all(x, y)EV . A fuzzy sub graph H =(, ) is said to be a spanning fuzzy sub graph of G, if (x) = (x)for all x. A fuzzy G is said to be connected if there exists a strongest path A path

   P of length n is a sequence of distinct nodes u0u1, u2, un such that (ui1, ui) > 0 and degree of membership of a weakest arc is defined as its strength. If u0 = un and n 3, then P is called a

   J{ } }

   ),

   cycle and it is a fuzzy cycle if there is more than one weak arc. Let u be a node in fuzzy graphs G then N (u) = v : (u, v) is strong arc is called neighborhood of u and N[u] = N(u) u is called closed neighborhood of u. Neighborhood degree of the node is defined by the sum of the

   weights of the strong neighbor node of u is denoted by ds(u) =

   veN (u)

   (v)

3. Fuzzy dominating set

   Definition 3.1. Let G be a fuzzy graph and u be a node in G then there exist a node v such that (u, v) is a strong arc then u dominates v .

   Definition 3.2. Let G be a fuzzy graph. A subset D of V is said to be a fuzzy dominating set if for every node vEV \ D, there exists uED such that u dominates v.

   ),

   Definition 3.3. The domination number of G is the minimum cardinality taken over all dom- inating sets in G and is denoted by (G),where (G) = (v). A dominating set with

   veD

   cardinality (G) is called – set of G.

4. Fuzzy non bondage number

   Definition 4.1. The bondage number b(G) of a fuzzy graph G(V, E, , µ)) is minimum number of fuzzy arcs among all sets of arcs X = (x,y) sub set of E such that

   CON NG(x,y)(u, v) < CON NG(u, v) for all uEV (G) and a v E(G). Here (G) represent minimum dominate set

   Definition 4.2. The non-bondage number bn(G) of a fuzzy graph G(V, E, , µ)) is maximum number of fuzzy arcs among all sets of arcs X = (x,y) sub set of E such that

   CON NG(x,y)(u, v) = CON NG(u, v) for all uEV (G) and a v E(G).Here (G) represent minimum dominate set

   Theorem 4.3. For any fuzzy graph G,

   bn(G) = q p + (G) (1)

   , where q is total number of fuzzy arcs and p is total number of node.

   Theorem 4.4. For any graph G.

   bn(G) q n (2)

   where n is number total number of strong arcs in of G .

   Theorem 4.5. For any fuzzy graph, (x, y) is a non bondage iff (x, y) is a weakest arc of any cycle.

   { }

   Remark 1. Let G: (, µ)be a fuzzy graph such that G : (, µ) is a cycle and Let t = min µ(u, v) : µ(u, v) > 0 .Then all arcs (u,v) of G such thatµ(u, v) > t are fuzzy bondage of G.

   µ(u, v) = t is only non-bondage of G.

   Theorem 4.6. Let G:(, µ) be fuzzy graph such that G : (, µ) is a cycle. Then a node is a not fuzzy cut node of G iff it is incident with a non-bondage arc.

   Theorem 4.7. If G is a fuzzy forest, the arcs of F are not fuzzy non -bondage of G.

   Theorem 4.8. A complete fuzzy graph with n notes has n-1 non bondage.

   Theorem 4.9. A complete fuzzy graph has no fuzzy cut nodes.

5. Exact values of bn (G) for some standard graphs

   2

   Proposition 5.1. If Ppis a path with p 4 nodes, then bn(Pp) = ip/31 1. Proposition 5.2. If Cp is a cycle with p 3 nodes, then bn(Cp) = ip/31 . Proposition 5.3. If Kp is a complete graph p 3 nodes, then bn(Kp) = (p1)(p2) .

   Proposition 5.4. If Km,n is a complete bipartite graph ,then bn(Km,n) = mn m n + 2

   Proposition 5.5. If Wp is a wheel with p 4 nodes, then bn(Wp) = p 1.

   Proposition 5.6. For any tree T, bn(T ) = (T ) 1.

6. Relationships between bn(G) and b

   Theorem 6.1. Let T/= P4 be a tree with at least two cut nodes .then

   bn(G) b(T ) (3)

   .

   Theorem 6.2. For any fuzzy graph

   b(G) bn(G) + 1 (4)

   Theorem 6.3. If G be a cycle graph then

   <>

   bn(G¯) + bn

   (G) p(p 3) 2

   (5)

   , p 4

   Proof. by theorem 6 bn(G) = q p + (G) bn(G¯) = q¯ p + (G¯)

   bn(G¯) + bn(G) = q p + (G) + q¯ p + (G¯)

   = q + q¯ 2p + (G¯) + (G)

   2

   = (p(p1)) 2p + (G¯) + (G)

   2

   (p(p1)) 2p + p

   2

   (p(p3)) .

   .

   Theorem 6.4. For any graph G,

   bn(G¯) + bn

   (G) ((p 1)(p 2))

   2

   (6)

   Proof. by Theorem 7 bn q n,then

   bn(G¯) + bn(G) q¯ + q (n + n)

   2

   = (p(p1)) (n + n)

   2

   (p(p1)) (p 1)

   2

   ((p2)(p1)) .

   Theorem 6.5. If G be a cycle graph then

   Proof. by Theorem 9

   b(G) bn(G) + 1

   b(G¯) + b(G) (p(p 3)) + 2 (7)

   2

   b(G¯) + b(G) bn(G¯) + bn(G) + 2 by Theorem 10

   2

   b(G¯) + b(G) (p(p3)) + 2

   Theorem 6.6. Any graph G,

   b(G¯) + b(G) ((p 1)(p 2)) + 2 (8)

   2

   Theorem 6.7. If G be a tree then

   if p 4

   bn(G¯) + bn(G) (G¯) + (G) 2, (9)

   Proof. bn(G) (G) 1 , then

   bn(G¯) + bn(G) (G) + (G) 2.

7. Block

   Definition 7.1. A connected fuzzy graph is called block if all nodes are satisfies the condition

   CON NGv(u, v) = CON NG(u, v) for every u, v in G..

8. Strong line graph

   Definition 8.1. Given a fuzzy graph G, its strong line graph Ls(G) is a fuzzy graph, Ls(G) is a graph G such that

   Each node of Ls(G) represents an arc of G; and Two nodes of Ls(G) are adjacent if and only if their corresponding arcs are strong and share a common end point in G.

   Definition 8.2. Given a fuzzy graph G, its double strong line graph Ls (G) is a fuzzy graph,

   Ls (G)(, ) is a graph G such that

   Each node of Ls (G) represents a strong arc of G; and Two nodes of Ls (G) (say u and v) are adjacent if and only if their corresponding arcs are strong and share a common end point in G say x.(u, v) = µ(k, x) µ(x, w)

   Theorem 8.3. For any cycle fuzzy graph, then Ls(G) has one isolate node iff G has a non bondage arc.

   Proof. Let Ls(G) has one isolated node, so G has one weakest arc (x, y) by theorem 4.5 then (x, y)is non bondage. Conversely, let G has a non-bondage arc ( x, y), clearly (x, y) weakest arc and node x and y does not common node for two strong arcs. So corresponding vertex of arc (x, y) in Ls(G) is isolated.

   Theorem 8.4. Let Ls(G) be fuzzy black graph such that Ls(G) is a tree. Then a node in Ls(G)

   iff G has non-bondage or a arc adjacent with a non-bondage arc.

   Proof. Given Ls(G) be fuzzy block then CON NGv(u, w) = CON NG(u, w) by definition here node of Ls(G) is a arc of G, so we clearly that CON NG(x,y)(r, v) = CON NG(r, v), converse true trivially.

   Theorem 8.5. A complete fuzzy graph of Ls(G) is not a complete.

   Proof. Given that G is compete fuzzy graph so there exist a cycle in G and every node of even pair does not adjacent with odd pair so corresponding nodes not adjacent in Ls(G).

   Theorem 8.6. Let G be a path graph with n nodes then Ls (G) has n-2 arcs.

   Proof. Given G be a path with n nodes then n-1 arcs so Ls (G) has a path with n-1 nodes so it has n-2 arcs.

   Theorem 8.7. Let G be complete graph with n nodes then Ls (G) is 2(n-2) regular graph.

   Proof. Given G be complete graph so every node has n-1 strong arc then every arc adjacent with 2n-4, so Ls (G) has 2(n-2) regular graph.

   .

9. Neighbourhood Extension

   Definition 9.1. Let G be graph andSi V , each Si is collection of each node in G and let GE(, ) be underlying crisp graph. If GE(, )said to be Neighbourhood extension, then satisfied following condition.

   • Each node of GE represents an strong neighbourhood set of G

     Two nodes of GE are adjacent iff their correspond neighbour set have at least one common node

     where(Si, Sj) = min{µ(x, vi), µ(vj, x)/xESi Sj}

     Definition 9.2. Let G* be Connected graph and if GE = G then G said be C- Neighbour Extendable graph also called strong Neighbourhood Extendable otherwise weak Neighbourhood Extendable

     Definition 9.3. Let G* be tree graph,if GE = G then G said be t- Neighbour Extendable graph also called semi strong Neighbourhood Extendable

     Theorem 9.4. Let G be cycle graph and if all arcs are bondage arc , then GE is complement of G.

     Proof. We know that G is connected graph and each node adjacent two nodes since G is cycle,so strong neighbour of each node of G is two.Clearly, if vi, vj, are adjacent nodes then Ns(vi) Ns(vj) = but alternative nodes have some same nodes, so make arcs between them it will be form complement of G.

     Corollary 9.5. Let G be cycle graph with n nodes then G is strong neighbour extendable if n is odd, otherwise weak neighbour extendable

     Proof. Case 1: If n is odd, by using theorem 9.4 there exist two paths in GE ie one is v1, v3, …vn, v2 say P1 another path say P2 is v2, v4, …vn1, v1 so P1 and P2 has same nodes say v1andv2 clearly GE is connected graph and G is strong neighbour extendable

     Case 2: If n is even, by using theorem 9.4 there exist two paths in GE ie one is v1, v3, …v2n1v1 say P1 another path say P2 is v2, v4, …v2n, v2 so P1 and P2 does not have same nodes.Clearly GE is disconnected graph and G weak neighbour extendable

     Theorem 9.6. Let G be complete graph with n nodes, then G is strong neighbour extendable

     NS(vi)

     Ns(vj) = {v1, v2, …vi1, vi+1, ..vj1, vj+1, ..vn}vi, vjEG ,this implies that GE is com-

     Proof. We know that G complete graph then every node has n-1 strong arcs so strong neighbour set of envery node has n-1 nodes NS(vi) = {v1, v2, …vi1, vi+1, ..vn}viEG then

     plete graph,so G is strong neighbour extendable

     Theorem 9.7. Let Pn be path with n nodes then G is not neighbour extendable.

     Proof. LetPn be path with n nodes then there exist unique path , so every arcs are strong arc and two nodes have one strong neighbour other nodes have two strong neighbours, but their neighbour sets are distinct, so GE is null graph therefore G is not neighbour extendable.

     Theorem 9.8. Let G be complete bipartite graph then G is not strong neighbour extendable Proof. Given G is complete bipartite graph so node set is partition of two set say V1 and V2

     then each node of V1 is strong neighbour of every node in V2 there two distinct path form in GE

     ,One path connect every node in V1 another path connect every node in V2 so GE is disconnect graph therefore G is not strong neighbour extendable.

     Theorem 9.9. Let G be wheel graph with p nodes then G is Strong neighbour Extendable Proof. Given that G is wheel graph then the domination number of G is one (say vi) clearly vi

     incident with p-1 bondage so strong neighbourhood set of every node of G has node vi therefore

     GE is connected graph implies that G is strong neighbour extendable.

     Definition 9.10. (Deficiency Number) Let G be fuzzy graph but G is not strong neighbour extendable then the deficiency number is required number of arcs to make G is strong neighbour extendable .

     Theorem 9.11. Let G be graph with 2n nodes which G is not neighbour extendable then defi- ciency number of G is one.

     Proof. Given G is cycle with even nodes by using corollary 9.5 there exist two distinct cycle so add one strong arc between any node from one cycle and another cycle then GE is connected graph therefore neighbour extendable .

     Theorem 9.12. Let G be complete bipartite graph which G is not neighbour extendable then deficiency number of G is two .

     Proof. Given G is complete bipartite graph by using theorem 9.8 there exist two open path so need two arcs for make GE is cycle therefore G is strong neighbour extendable.

10. Conclusion

L(G) is not tree, if all arc of G are strong. Above non bondage value (/= 0) is not true for all graphs beause K1,n or star graph and P3 non-bondage value is 0 and also bondage number is equal to 1 for such above graphs

References

1. E.J.Cockayne, B.L.Hartnell, S.T. Hedetniemi and R. Laskar , Efficient domination in graphs, Technical Report 558 Clemson University, department of mathematical Sciences (1988)

2. E.J. Cockayne and S.T Hedetniemi; Towards a theory of domination in graphs, Networks,247-261 (1977)

3. J.F .Fink, M.S.Jacobson, L.F .Kinch and J.Roberts; The bondage number of graph, Dis- crete Math., 86, 47-57 (1990).

4. Gerard Jennhwa Chang , Paul Dorbec ,, Mickael Montassier, Andr Raspaud:Generalized power domination of graphs,Discrete Applied Mathematics 160 (2012) 16911698

5. F. Harary: Graph theory , Addison Wesley , Reading, Massachusetts (1963)

6. R.JahirHussain and R.M. Karthik keyan: Characterization of fuzzy non- bondage number of fuzzy graphs. Mathematical Sciences int., Research Journal vol4 issue 2 ISSN 2278-8697

7. V.R. Kulli and B. Janakiram; The non-bondage number of a graph , New York Acadency of Science, (1996)

8. A.Rosenfeld. Fuzzy graphs, InFuzzysets and their applications to Cognitive and Decision. Eds. Academic press, New York (1975)77-95.

9. K .R. Sandeep Narayan and M.S. Sunitha ; Connectivity in a Fuzzy Graph and its com- plement ICSRS Publication ,2012

10. Sunil Mathew, Sunitha M.S; Fuzzy Graphs: Basic Concepts and Applications, Lap Lam- bert Academic Publication.

11. G. Suresh Singh and Sunitha Grace Zacharia Some Results on Completely Extendable and Weighted Extendable Graphs Int.journal of Mathematics Archive 2016

12. H. B.Walikar, B.D. Acharya and E.Sampathkumar , Recent developments in the Theory of Domination in Graphs, MRI Lecture Notes Math. I (1979)