Coloring Edge Connectivity of Fuzzy Graph

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.

1. INTRODUCTION

   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

   n

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

   (ui1, ui ).

   i1

   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.

2. FUZZY GRAPH

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

   uns(v)

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

   Example-2.7.

   (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

   (i)

   ,

   2 3 2 4 2 5

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

   1. i j 0,

      3 5 4 5

3. FUZZY EDGE CONNECTIVITY

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

   (ii)

   i j

   0,

   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

   bond.

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

4. COLORING FUZZY EDGE CONNECTIVITY

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

color,

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.

IV. ILLUSTRATION: CANCER DETECTION PROBLEM

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

   clusters

   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.

   REFERENCES

   1 2 3 4 5

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

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

   and

   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