Fuzzy graph

Basic Concept

1. DR.M.Sheela Assistant Professor of Mathematics Bon Secours college for Women,Thanjavur Fuzzy Graph

2. FUZZY GRAPH A Fuzzy graph G(σ, µ)on G*(V,E) is a pair of functions σ : V → [0,1 ] and µ: V x V → [0,1] where for all u, v in V, we have µ( u,v ) ≤ min {σ (u), σ (v) }. σ (u)=0.1 σ (v)=0.2 σ (w)=0.3 µ( u,v )=0.1 µ( u,w )= 0.1 µ( v,w )=0.2

3. The degree of any vertex of a fuzzy graph is sum of degree of membership of all those edges which are incident on vertex .And is denoted by d ( ) . A fuzzy sub-graph H : (τ , υ) is called a fuzzy sub-graph of G=(σ,µ) if τ(u) ≤σ(u ) for all u є V. And υ( u, v)≤µ ( u ,v) all u ,v є V  

4. A fuzzy sub-graph H : (τ , υ) is said to be a spanning fuzzy graph of G=(σ,µ) if τ(u) =σ(u) for all u. In this case, two graphs have same vertex set , they differ only in the arc weights . An edge E 1 ( x,y ) of a fuzzy graph is called an effective edge if µ ( x,y ) = min {σ (x), σ (y) }. A fuzzy graph is called an effective fuzzy graph if every edge is an effective edge.

5. The degree of any vertex of an effective fuzzy graph is sum of degree of membership of all those edges which are incident on vertex .And is denoted by dE 1 ( ). The minimum effective incident degree of a fuzzy graph G is ^ { dE 1 (v) / v V} . and it is denoted by δE 1 (G ). The maximum effective incident degree of a fuzzy graph G is v { dE 1 (v) / v V} . and it is denoted by ∆E 1 (G)  

6. The order of a effective fuzzy graph G is O(G)= The size of a effective fuzzy graph G is S(G)= . Let G=( ) be a fuzzy graph on G * =(V,E).If d G (v)=k for all v V that is if each vertex has same degree k, then G is said to be a regular fuzzy graph of degree k or a k-degree fuzzy graph.  

7. . For any real number ,0 a -path in a fuzzy graph ) is a sequence of distinct such that σ ( ) , 0 , and ) , 0 , here n is called the length of .In this case we write =( ) and is called a ( ) – path.  

8. A path P is called effective path if each edge in a path P is an effective edge. An effective path P is called an effective cycle if x0 = xn and n ≥ 3 . A fuzzy graph G = (σ , µ) is said to be effective connected if there exists an effective path between every pair of vertices . A fuzzy tree is an acyclic and connected fuzzy graph.

9. A fuzzy effective tree is an effective acyclic and effective connected fuzzy graph . The fuzzy effective tree T is said to be a fuzzy effective spanning tree of a fuzzy effective connected graph G if T is an effective sub graph of an effective fuzzy graph G and T contains all vertices of G.

10. Fuzzy Domination Number The complement of a fuzzy graph G=(σ , μ) is a fuzzy graph =( )where =σ and (u ,v )=σ(u) Λ σ(v)-μ(u ,v ) for all u ,v in V.   The complement of a complement fuzzy graph = ( ) where = and ( u,v )= Λ - for all u,v in V i.e ( u,v )= σ(u) Λ σ(v)-( σ(u) Λ σ(v)-μ(u ,v )) for all u,v in V then G  

11. u(0.8) v (0.5) 0.5 w(0.7) x(0.5) 0.5 0.5 u(0.8) v(0.5) w(0.7 x(0.5) 0.5 0.5 0.5 Let G=(σ , μ) be a fuzzy graph on G*(V,E) . A subset D of V is said to be fuzzy dominating set of G if for every v є V-D .there exists u in D such that. µ( u,v ) =σ (u)˄ σ (v).

12. A fuzzy dominating set D of a fuzzy graph G is called minimal dominating set of G, if for every vertex v є D ,D-{v} is not a dominating set. The domination number γ (G) is the minimum cardinality teaken over all minimal dominating sets of vertices of G. a(0.3) b(0.2) c (0.1) d (0.2) e(0.2) 0.1 0.1 0.1 0.2 0.2 0.2 0.2 0.2

13. Fuzzy Domination Set D ={a } Fuzzy Domination Number=0.3 Two vertices in a fuzzy graph G are said to be fuzzy independent if there is no strong arc between them . A subset S of V is said to be fuzzy independent set of G if every two vertices of S are fuzzy independent.

14. A fuzzy independent set S of G is said to be maximal fuzzy independent, if for every vertex v є V-S , the set S {v} is not a fuzzy independent . The independence number i(G) is the minimum cardinalities taken over all maximal independent sets of nodes of G.  

15. a(0.1) b (0.1 ) c(0.2) d (0.2 ) 0.1 0.1 0.1 Maximal fuzzy independent={ a,c,d } and i(G)=0.5

16. Fuzzy Global and Factor Domination ,Fuzzy Multiple Domination Fuzzy Global Domination Number A fuzzy graph H=( σ,μ ) on H*( V,E) is said to have a t-factoring into factors F(H)= {G 1 G 2 ,G 3 ,...... G t }if each fuzzy graph G i =( σ i ,μ i )such that σ i =σ and the set{μ 1 ,μ 2 ,μ 3 …….. μ t }form a partition of μ . Given a t-factoring F of H, a subset D f ⊆ V is a fuzzy factor dominating set if D f is a fuzzy dominating set of G i , for1≤i≤t.

17. The fuzzy factor domination number is the minimum cardinality of a fuzzy factor dominating sets of F(H ).and is denoted by γ ft (F(H)) . a(0.3) b(0.2) c(0.1) d(0.2) e(0.2) H 0.1 0.1 0.1 0.2 0.2 0.2 0.2 0.2

18. a(0.3) b(0.2) c(0.1) 0.1 d(0.2) e (0.2) 0.2 0.2 a(0.3) b(0.2) c(0.1) d(0.2) e(0.2) 0.2 0.2 0.1 a(0.3) b(0.2) c(0.1) d(0.2) d(0.2

19. Fuzzy factor domimating set={ a,c,e } Fuzzy factor domination number=0.6 letG =(σ, μ) be a fuzzy graph on G*(V,E) .A subset D g of V is said to be fuzzy global Dominating set of G and if for every vєV - D g there exists u in D g such that µ( u,v ) =σ (u)˄ σ (v)both G and .  

20. A fuzzy global dominating set D g of a fuzzy graph G is called minimal global dominating set of G, if for every vertex v є D g , D g -{v} is not a dominating set. The global domination number is the minimum cardinality taken over all minimal dominating sets of vertices of G. and is denoted by γ g (G) a(0.4) c(0.4) b(0.2) d(0.2) 0.2 0.2 0.2 0.2 a(0.4) b(0.2) d(0.2) c(0.4) 0.2 0.4)

21. Fuzzy global dominating sets { a,d } and{ b,c } Fuzzy global domination number=0.6 For any real number ,0 , a vertex cover of a fuzzy graph G=( ) on G * =(V,E) is a set of vertices σ ( ) , 0 that covers all the edges such that ) , 0 , here n  

22. An edge cover of a fuzzy graph is a set of edges ) , 0 , that covers all the vertices such that σ ( ) , 0 . The minimum cardinality of vertex cover is α (G) and the minimum cardinality of edge cover isα 1 (G).   a(0.2) d(0.2) b(0.3) c(0.4) 0.2 0.2 0.2 0.3 Vertex cover={ a,c } and { b,d } α (G)=0.5 α 1 (G)=0.4

23. Let G= (σ,µ) be a fuzzy graph . And let D be a subset of V is said to be fuzzy k-dominating set if for every vertex v є V-D , there exists atleast ‘ k’ u in D such that µ( u,v )=σ(u)˄σ(v). In a fuzzy graph G every vertex in V-D is fuzzy k- dominated, then D is called a fuzzy k-dominating set. The minimum cardinality of a fuzzy k-dominating set is called the fuzzy k-domination number k (G).  

24. a(0.2) d(0.2 ) g(0.2 ) b(0.1) c (0.1 ) e(0.1 ) f(0.1 ) h(0.1 ) 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 D={ b,c,e,f,h } and V-D= { a,d,g } D is a fuzzy two dominating set The fuzzy two domination number= 0.5

25. Domination in Fuzzy Digraphs A fuzzy digraph G D = ( σ D ,μ D ) is a pair of function σ D :V→[0,1] and μ D : V×V→[0,1] where μ D ( u,v )≤ σ D (u) Λ σ D (v) for u,v є V, σ D a fuzzy set of V,(V , μ D ) a fuzzy relation on V and μ D is a set of fuzzy directed edges are called fuzzy arcs.   Let G D = ( σ D ,μ D ) be a fuzzy digraph of V.If σ D (u) 0, for u in V, then u is called a vertex of G D .If σ D (u) 0 for u in V,then u is called an empty vetex of G D .If μ D ( u,v )=0, then ( u,v ) is called an empty arc of G D .  

26. Let = ( and = ( ) be two fuzzy digraphs of V . Then = ( ) called a fuzzy sub-digraph of = ( ) if (u) (u) for all u in V and ( u,v ) ( u,v ) for all u,v in V, then we write .  

27. For any real number ,0 ,a fuzzy directed walk from a vertex ( ) to ( ) is an alternating sequence of vertices and edges, beginning with ( ) and ending with ( ) , such that ( ) , 0 , and ) , 0 , here n each edge is oriented from the vertex preceding it to the vertex following it. No edge in a fuzzy directed walk appears more than once, but a vertex may appears more than once, as in the case of fuzzy undirected graphs .  

28. For any real number ,0 a directed -path in a fuzzy digraph ) is a sequence of distinct nodes such that ( ) , 0 , and ) , 0 , here n is called the length of .In this case ,we write =( ) and is called a ( ) – path.  

29. Two vertices in a fuzzy digraphs G D are said to be fuzzy independent if there is no effective edges between them . A subset S of Vis said to be fuzzy independent set of G D if every two vertices of S are fuzzy independent . The fuzzy independence number β (G D ) is the maximum cardinality of an independent set in G D .

30. A subset S of V in a fuzzy digraph is said to be a fuzzy dominating set of G D if every vertex v Є V -S ,there exists u in S such that μ D ( u,v )= σ D (u) Λ σ D (v ). The fuzzy domination number γ(G D ) of a fuzzy digraph G D is the minimum cardinality of a fuzzy dominating set in G D

31. a(0.1) d(0.1) g(0.1 h(0.2) b (0.2 ) c(0.2 ) e(0.2 ) f (0.2 ) 0.1 0.1 0.1 0.1 0.1 0.1 0.1 γ(G D ) =0.3

32. THANK YOU