Coloring Edge Connectivity of Fuzzy Graph

DOI : 10.17577/IJERTCONV4IS24023

Download Full-Text PDF Cite this Publication

Text Only Version

Coloring Edge Connectivity of Fuzzy Graph

S. Sarulatha

Department of Mathematics,

TRP Engineering College (SRM Group), Trichy-621105, Tamil Nadu, India.

Abstract Fuzzy graphs were introduced by Rosenfeld in 1975. Fuzzy graph theory has numerous applications in modern science and technology, especially in the fields of information theory, neural networks, expert systems, cluster analysis, medical diagnosis, control theory etc. In this paper, we deal with coloring of the edge connectivity of a fuzzy graph to obtain the better result in diagnosis of cancer cells.

Keywords Fuzzy graphs; fuzzy bonds; Fuzzy k-coloring; Fuzzy edge connectivity.


    The fuzzy graph approach is more powerful in cluster analysis than the usual graph-theoretic approach due to its ability to handle the strengths of edges effectively. As in graphs, connectivity concepts play a key role in applications related with fuzzy graphs [1]. Fuzzy graphs were introduced by Rosenfeld [2] and Yeh and Bang [3] independently in 1975. Rosenfeld in his paper Fuzzy Graphs presented the basic structural and connectivity concepts while Yeh and Bang introduced different connectivity parameters of a fuzzy graph and discussed their applications in the paper titled Fuzzy relations, Fuzzy graphs and their applications to clustering analysis [3]. In [4] the authors have defined the concepts of strong arcs and strong paths. Also, in modern fuzzy graph theory, we have the notions of strong as well as strongest path [4] between any pair of vertices and a fuzzy

    G : ( , ) if

    (u) (u)u * andV (u, v) (u, v)(u, v) *.

    Definition 2.3. A fuzzy graph G : ( , ) is strong if

    (u) (v) (u, v)u, v * and is complete if

    (u) (v) (u, v)u, v *.

    Note that every complete fuzzy graph is strong but not conversely.

    Also if G : ( , ) is a complete fuzzy graph than

    G* : ( *, *) is a complete graph.

    Definition 2.4. A path P in a fuzzy graph G : ( , ) is a sequence of distinct vertices u0 ,u1,u2 ,…,un such that

    (ui1,ui ) 0, 1 i n.

    Here n 1is called the length of the path P. A single vertex u may also be considered as a path. In this case the path is of length 0. The consecutive pairs (ui1, ui ) are called edges of the path. We call P a cycle if u0 un and n 3.

    Definition 2.5. The strength of a path P is defined as


    edge cut can be viewed as a set of strong edges whose removal from G reduces the strength of connectedness

    (ui1, ui ).


    In other words, the strength of a path is

    between some pair of vertices of G, at least one of them differing from the end vertices of edges in the cut. The edges which are not strong need not be considered because the flow through such edges can be redirected through a different path having more strength. In the same manner we have to coloring the edge connectivity to diagnosis the cancer cells for better result.


    Definition 2.1. Let V be a non-empty set, A fuzzy graph is a

    defined to be the degree of membership of a weakest edge of

    the path. If the path has length 0, it is convenient to define its strength to be (u0 ).

    Definition 2.6. Let G : ( , ) be a fuzzy graph. The

    strong degree of a vertex * is defined as the sum of membership values of all strong edges incident at . It is

    denoted by Ds ( ). Also if ns ( ) denote the set of all strong

    neighbours of , then Ds ( ) (u, v) .

    pair of functions G : ( , ) where is a fuzzy subset of V and is a symmetric fuzzy relation on . i.e.,


    :V [0,1] and :V V [0,1] such that


    (u) (v) (u, v) for all u, v in V.

    Definition 2.2. The fuzzy graph H : ( , ) is called a partial

    (u1 ) 0.7, (u2 ) 1, (u3 ) 0.6,

    (u4 ) 0.8, (u5 ) 0.9 and

    (u1, u2 ) 0.3, (u1, u3 ) 0.4, (u2 , u3 ) 0.2,

    fuzzy sub graph of G : ( , ) if and . In

    (u2 , u4 ) 0.7, (u2 , u5 ) 0.8,

    particular, we call H : ( , ) a fuzzy sub graph of

    (u3 , u5 ) 0.5, (u4 , u5 ) 0.6.

    Since the values satisfy (u, v) (u) (v)

    which is a fuzzy graph a strongest path joining

    u2 and u5 is the path

    X 1,…, v , v(x) sup I / x A x X and

    A 1,…, I.

    2 5

    2 5

    P : u2 ,u4 ,u5 with (u ,u ) 0.6

    1 2 1 4 1 5 1 3

    1 2 1 4 1 5 1 3

    (u , u ) (u , u ) (u , u ) (u , u ) 0.3

    Definition 4.1. A family 1, 2 ,…, k of fuzzy sets on X is called a k-fuzzy coloring of G ( X , , ) if

    (u , u ) 0.2, (u , u ) 0.7, (u , u ) 0.6



    2 3 2 4 2 5

    (u , u ) 0.5 and (u , u ) 0.6.

    1. i j 0,

      3 5 4 5


    In [3], the notion of edge connectivity of a fuzzy graph if defined as given below. As mentioned in the introduction this definition is more close to a graph rather than a fuzzy graph since, in a fuzzy graph the concept of strength of connectedness plays a crucial role.

    Definition 3.1. Let G be a fuzzy graph and V1,V2 be a

    1. for every strong edge xy of G,

    min i (x), i ( y) 0 (1 i k).

    The least value of k for which G has a k-fuzzy coloring, denoted by F (G), is called the fuzzy chromatic number of G.

    Definition 4.2. A family 1, 2 ,…, k of fuzzy sets on

    X E is called a k-fuzzy total coloring of G (V , , ) if

    partition of its vertex set. The set of edges joining vertices of

    (i) maxi i (x) (x) for all x X and

    V1 and vertices of V2 is called a cut-set of G, denoted by

    max (xy) (xy) for all edges xy E.

    V ,V relative to the partition V ,V . The weight of the i i

    1 2

    cut-set V ,V is defined as

    1 2

    (u, v).


    i j


    1 2 uV1 ,vV2 (iii) For every adjacent vertices x, y of

    Definition 3.2. Let G be a fuzzy graph. The edge connectivity of G denoted by (G) is defined to be the minimum weight

    of cut-sets of G.

    min i ( yj yk ) / yj yk 0, (are set of incident edges from the vertex xj) j 1, 2,…, x .

    Definition 4.3. Let G be a fuzzy graph. The coloring edge

    Definition 3.3. A one fuzzy edge connectivity is called a fuzzy


    connectivity of G denoted by F (G) is defined to be the

    minimum weight of cut-sets of G. Given a fuzzy graph

    Remark 3.4. Note that fuzzy bonds are special type of fuzzy bridges. Note all fuzzy bridges are fuzzy bonds.

    Example 3.5.

    G (V , F , F ) its edge chromatic number in fuzzy number F (G) x , where x is the edge

    Let G : ( , ) be with * a,b, c, d, ewith

    (a, b) 0.4, (a, c) 0.2, (b, c) 0.3,

    (c, d ) 0.5, (d, a) 0.7, (a, e) 0.6, .

    (b, e) 0.5

    There are four fuzzy bonds in this fuzzy graph namely edges (a, d), (a, e), (d, c) and (e, b).


In a crisp graph G = (V, E), a coloring function C assigns an integer value c(i) to each vertex i V in such a way that the extremes of any edge (i, j) E cannot share the same


i.e., c(i) c( j). In a fuzzy graph G (V , ) , its chromatic number is the fuzzy number

(G) x, v(x) / x X where

connectivity chromatic number ofG and values are the different membership value of vertex and edge of graph G.


In our human body, based on the location of the cells in the low magnification image of a tissue sample, surgically removed from a patient, it is possible to construct a graph with G with vertices as cells, called cell graph [5]. By analyzing the physical features of the cells; for example color and size, we can assign a membership value to the vertices of

  1. This value will range over (0, 1] depending of the nature of the cell; that is healthy, inflammatory or cancerous. Also, edges of G can assign a membership value based on the distances between the cells. Thus the cell graph can be converted to a fuzzy graph in this manner.

    Applying the above clustering procedure to such a fuzzy graph, the cancerous cell clusters can be detected at the

    cellular level in principle. This process, classifies cell After applying the coloring edge connectivity of fuzzy graph


    G is F (G) =0.6. Using the Yeh and Bang procedure in

    in a tissue into different phases of cancer, depending of the distribution, density and fuzzy connectivity of the cell clusters within the tissue using coloring the edge connectivity.

    coloring we obtain the level as given below

    From the above clusters corresponding to

    F (G) =0.6, it is

    Assume that the vertices with weights more than 0.6 represent cancerous cells, edges with weights between 0.3 and 0.5 inflammatory cells and between 0 and 0.4 healthy cells. Let the vertex set of G be v1, v2 , v3 , v4 , v5

    Let G : ( , ) be an fuzzy graph with

    * v , v , v , v , v with

    observed that {4, 5} is a cell cluster which is affected seriously by cancer whereas its neighbouring area containing the cells {2} and {3} can be found inflammatory. Note that the cell {1} is healthy.


    1 2 3 4 5

    (v1 ) (v2 ) (v3 ) (v4 ) (v5 ) 0.8

    (a, b) (a, c) 0.4,


    1. J.N.Moderson, P.S.Nair, Fuzzy Graphs and FuzzyHypergraphs, Physica-Verlog, 2000.

    2. A.Rosenfeld, Fuzzy Graphs,in: L.A. Zadeh, K.S.Fu, M.Shimura(Eds),

      (b, d ) (d, e) (c, e) 0.6

      (b, c) 0.3, (c, d ) 0.5

      using coloring edge connectivity

      (xi ) 0.8 for i 1,…,5

      0.4 for ij 12,13

      0.6 for ij 24, 45, 35

      (x , y )

      Fuzzy sets and their applications to cognitive and Decision processes, Academic Press, New York, 1975, pp 77-95.

    3. R.T.Yeh, S.Y.Bang, Fuzzy relations, fuzzy graphs and their applications to clustering analysis, in: L.A.Zadeh, K.S.Fu, M.Shimura, Fuzzy sets and their applications, Academic Press, 1975, pp 125-149.

    4. K.R. Bhutani, A.Rosenfeld, Strong arcs in fuzzy graphs, information sciences 152(2003) 319-322.

    5. B.Yenes, C.Gunduz, S.H.Gultekin, The cell graphs of cancer, Bio informatics 20(1) 2004, 145-151.

i j 0.3 for ij 23

0.4 for ij 34


Maximal edge connectivity


(0, 0.6]

{1, 2, 3}

C1={1, 2, 3}

[0.6, 1]

{2}, {4}, {5}

C2={2}, C3={4}, C4={5}

Leave a Reply