Abstract
In this paper we discuss about the concepts of vague graphs which gives the precise idea about coloring. We know about the coloring on fuzzy graphs with both fuzzy membership values on vertices and edges. In this work we implement the concept of (α, β) cuts used to define the properties of coloring in vague graphs. Also we relate the idea of coloring on vertices of vague graphs using different methods. In this regard we focus on fuzzifying the vertex membership values of the vague graph into fuzzy membership values and hence implement the concept of coloring in this fuzzified vague graph.
Introduction
Fuzzy logic involves the major part of its contributions with wide range of real time applications. When used with the graphs it has created a unique way of representation on real time data set. Introduced by Lofti A. Zadeh [1] in the year 1965, achieving its high way of success in different fields. The concept of fuzzy graphs has been developed by Rosenfeld [2] in the year 1975 with various definitions pertaining to the cycles, connectivity and coloring of fuzzy graphs. Eslahchi et al. [3] in his paper identified the vertex strength of fuzzy graph. Mordeson et al. [4] in his article identified the types of fuzzy graphs and its operations. Rakesh et al. [5] in his paper analysed the concept of traffic light problem using fuzzy graphs. Lavanya et al. [6] has analysed the concept of fuzzy total coloring and its applications in fuzzy graph. The concept of vagueness is a generalization of fuzzy graph. For example, if suppose in a set of 20 people voting in an election, 10 people stands in a favourable side of polling, 7 people stands against the favourable conditions of polling and 3 people stands neutral without taking any decisions. There arises the situation of vague sets and hence it removes the abstained condition and provides the exact details of the belongingness. Gau et al., in 1994 presented the concept of vague sets. They used the truth membership function and false membership function to classify the data set namely t A and f A respectively. They characterized the lower bound of the fuzzy membership function μ A . Hence in a subinterval of [0,1], the lowerbounds are used to create the vague data set as [t A (u i ) , 1 - f A (u i )] which generalizes the membership function μ A (u i ) as t A (u i ) ≤ μ A (u i ) ≤1 - f A (u i ). Vague graphs has been studied by Akram et al. [7] in his paper Certain types of fuzzy graphs. In this paper we analyse the concept of coloring in fuzzy graphs using different methods of coloring. Given a vague data set, the objective is to color the vertices in a vague graph using vague fuzzifiication method. We fuzzify the vague vertex membership values defined by Solairaju [8], in their paper to fuzzify the vague data set. We use MatLAB 2016(A) to fuzzify the vague data set into fuzzy membership values with the parameter of λ, a positive number. We propose a new method of coloring based on the range set of fuzzified data from the vertex membership values of the vague graph. Hence we try to color the vertices in the vague graph based on its fuzzified membership values obtained. Some of the concepts are also dealt with the vague graphs. Boorzoei and Hossein Rashmanlou [9] analysed the concepts on Laplacian matrix and spectrum on Vague graphs. Hossein et al. [10] in his paper contributed some of the isomorphic properties of vague graphs.
Ghorai et al. [11] has analysed the concept of density of m-polar fuzzy graphs and its operations. Also they analysed the properties of fuzzy graphs [12] in their paper on “some properties of fuzzy graphs”. Ghorai and Pal also discussed the concepts of [13] m-polar fuzzy planar graphs and faces and dual [14] of m-polar fuzzy planar graphs. Isomorphic properties of fuzzy graphs were discussed by many authors. Ghorai and Pal [15] in their paper investigated the properties of m-polar fuzzy graphs. Also they discussed some applications of isomorphic properties of m-polar fuzzy graphs.
The vague sets are considered to be intervalued fuzzy sets in this regard it is worth mentioning that the interval valued fuzzy sets are not vague sets. In interval valued fuzzy sets the interval valued membership values are assigned to each element of the evidence for x in a set a and evidence against x in a set A. In vague sets both are independent and hence determined based on the decision. A vague relation on a set is a generalisation of a fuzzy relation in universe of discourse. Samata et al. [16] in their work analysed the concepts of vague graphs and its strength. Hossein et al. [17] investigated the properties of intuituonistic fuzzy graphs and its importance in fuzzy analysis. Hossein et al. [17] also identified the properties of vague graphs and its applications in their article “A study on vague graphs”. Hence the behaviour of vague graphs and its applications are used in real time applications. One of the important analysis which is credential in this work is about the study of vague graph coloring in different scenarios. We also discussed and sorted out the vagueness into fuzziness and discussed the coloring concepts in it.
Main definition and results
A fuzzy graph G = (V, σ, μ) with the vertex set σ : V → [0, 1] and the edge set μ : V × V → [0, 1] such that for all x, y ∈ V, μ (x, y) ≤ σ (x) ∧ σ (y) . σ (x) is the membership value of vertex and μ (x, y) is the membership value of the edges.
Here μ is a symmetric fuzzy relation on σ .
A family Γ = {γ1, …, γ
k
} of fuzzy sets on V is called a k-fuzzy coloring of G = (σ, μ) if ∨Γ = σ, γ
i
∧ γ
j
= 0, For every strongly adjacent vertices u, v of G, min {γ
i
(u) , γ
i
(v) =0 (1 ≤ i ≤ k)}.
Fuzzy chromatic number is the least value of k for which the fuzzy graph G has k-fuzzy coloring and is denoted by χ F (G).
Vague set is a generalization of fuzzy set. A vague set is characterized by two membership functions namely a truth membership function t v (i) and false membership function f v (i). t v (i) is the lower bound of the grade of membership function of i determined by the evidence of i and f v (i) is the negation of the grade of membership of i determined against the evidence of i. The difference 1 - f v (i) - t v (i) is the uncertainty in the vague set. The uncertainty is determined based on the value of difference. If the difference value is small the knowledge is precisely relative and if it is large the knowledge is little. The boundedness of this vague set is represented by t v (i) ≤ μ v (i) ≤1 - f v (i) where t v (i) + f v (i) ≤1.
The example shows the vague set X [t B (x) , 1 - f B (x)] = [0.7, 0.2]. This indicates the degree of x belonging to the set B is 0.7 and the degree of x not belonging to the set B is 0.2. 0.1 is the degree representing the neutral position. This is a interval valued set on a vague relation.
Let G* = (V, E) be a crisp graph. A pair G = (A, B) is called a vague graph on a crisp graph G* = (V, E) where A = (t A , f A ) is a vague set on V and B = (t B , f B ) is a vague set on E ⊆ V × V such that t B (xy) ≤ min(t A (x) , t A (y)) , f B (xy) ≥ max(f A (x) , f B (y)) for each edge xy ∈ E .
Otherwise A is the vague set on V and B is a vague relation on V.
Let G* = (V, E) be a crisp graph. A pair G = (A, B) is called a vague graph on a crisp graph G* = (V, E) where A = (t A , f A ) is a vague set on V and B = (t B , f B ) is a vague set on E ⊆ V × V such that for each edge xy ∈ E .
A graph G* = (V, E) is said to be complete vague graph if it is strong. i.e., t B (xy) = min(t A (x) , t A (y)) , f B (xy) = max(f A (x) , f B (y)) for each edge xy ∈ E .
A Vague graph is said to be Eulerian if all the edges in the graph are strongly connected and has a cycle from any vertex as origin and terminal.
Vague graph.
Let G* = (V, E) be a vague graph with A = (t A , f A ) is a vague set on V and B = (t B , f B ) is a vague set on E ⊆ V × V. The level set of the truth and false membership values of A and B are defined as α and β such that α = {α1 < α2 < … < α k ) and β = {β1 < β2 < … < β k ) for I = α ∪ β ∪ {0} ∪ {1}.
A k-coloring on strong vague graphs is defined as minimum number of colors say k required to color the vertices of the strong vague graph using the (α, β) cuts on the level set of A and B.
Strong vague Graph.
We consider the α cut values as α = {0.1, 0.2, 0.3, 0.4, 0, 5.0, 6} and β = {0.1, 0.2, 0.3, 0.4, 0, 5.0, 6}
Vague graph for (α, β) = (0.1, 0.3).
For (α, β) = (0.1, 0.3) we have the k-coloring as χ V (G) =2 as shown in the graph below
In the previous section we discuss about the concept of level sets for identifying the vertex coloring on vague graphs. In this section we are considering the color classes to analyse the coloring on vertices in vague graphs.
The concept of coloring on vague graphs using the definition of color class depends only on the truth membership functions which is the lower bound of the vague set A and we do not consider the lower bound of the vague set B which carries the negation of false membership values. The following discussion are dealt only with the case of truth membership values of the vague graphs.
A family Γ = {γ1, …, γ
k
} of fuzzy sets on V is called a k-fuzzy coloring of G = (V, A, B) if ∨Γ = A, γ
i
∧ γ
j
= 0, For every strongly adjacent vertices u, v of G, min {γ
i
(u) , γ
i
(v)} =0 (1 ≤ i ≤ k).
Fuzzy chromatic number is the least value of k for which the fuzzy graph G has k-fuzzy coloring and is denoted by χ V (G) .
In Example 2.2 we consider the strong vague graph having 4 vertices and 5 edges. Considering the truth values of the vague graph we analyse the definition of k-coloring using color class Γ. We have γ = (0.2, 0.4) , (0.3, 0.6) fori = 1 and (0.1, 0.3) fori = 2and (0.3, 0.5) fori = 3. We define the family of color class Γ = {γ1, γ2, γ3} which satisfies the condition of the above definition. Hence we see that χ V (G) =3 .
Fuzzification of vague set into fuzzy set
The fuzzy set A defined in the universe of discourse U is a set of ordered pairs {(u1, μ A (u1)) , (u2, μ A (u2)) , …, (u n , μ A (u n ))} , where μ A is the membership function of the fuzzy set A, μ A : U → [0, 1] and μ A (u i ) indicates the grade of the membership of u i in A. The concept of vague set is a interval based classification of membership functions on the basis of truth and false membership function. This is used to generate a vague interval namely [t A (u i ) , 1 - f A (u i )] to generalize the membership function in fuzzy set μ A (u i ) such that t A (u i ) ≤ μ A (u i ) ≤1 - f A (u i ) .
For example, let B be a vague set with truth membership and false membership function namely t A and f A respectively. If we consider the interval [t A (u i ) , 1 - f A (u i )] = [0.2, 0.7], then the assigned values are t A (u i ) =0.2 and 1 - f A (u i ) =0.7 ⇒ f A (u i ) =0.3 . So if we want to consider the vague set with truth membership and negation of false membership then the case of evaluating the coloring of its vertices may be critical even we considered the truth membership function values alone. Hence we try to fuzzify the vertices of vague graph to a fuzzy membership value.
In this section we implement the technique of vague fuzzification [8] to convert the vague data into fuzzy membership values. We use mat lab 2016(B) to convert these data into fuzzy membership values. By finding the corresponding membership values of the vertices and edges of the graph the respective graph could be transformed into fuzzy graph. By doing so, we avoid the constraints of vague data set defined as true and negation of false membership values and coordinate those values into fuzzy membership values. The method []used to fuzzify the vague data is defined as follows. Let λ be a distance of the line segment and λ > 0, a positive integer. Then the fuzzified membership values of the corresponding vague set is given by
Coloring on fuzzified vertices on vague graphs
In this section we see about the concepts on coloring of the vertices of vague graph by transforming it into fuzzified membership values and color the corresponding vertices based on the membership values.
Vague graph.
Fuzzified vertices on Vague Graph.
Consider the vague graph with vertex membership values as follows.
In this vague graph we consider the vertex membership values as vague data and the edges having a crisp data. Hence we could transform the vertex membership values of true membership function and negation of false membership function as the fuzzified membership values using matlab. Using the above rule considering the parameter of λ = 100 we get the fuzzified membership values for vertices {a, b, c, d} = {0.15, 0.45, 0.37, 0.45} respectively.
The below graph refers to the fuzzified vertices in the vague graph defined above.
Hence we see that the coloring of this graph is based on the k-fuzzy coloring definition mentioned above as Γ = {γ1, γ2}, the color classes having the membership values of a, d and b, c. This satisfies the criteria of the definition and hence we could assign minimum of 2 colors to color this fuzzified vague graph vertices. Therefore we see that the chromatic number of this graph is χ V (G) =2 .
Also the edges in this fuzzified vague graph does not have an impact over the vertex coloring as we consider the edges to be crisp in knowledge.
In this concept we propose the method of classifying the color class using the range of fuzzified vague set assigned to the vertices of vague graphs as fuzzy membership values.
Also we see define the range of color classes as follows.
In this approach we fix the range of the membership values obtained after fuzzifying the vague data set into fuzzified membership values. Hence we apply the cluster of colors to the range defined above.
Vague graph with 5 vertices.
According to the proposed method the vertex membership values of the vague graph are assigned the colors C = {c2, c3}. Hence the required number of colors assigned to the vague graph defines the chromatic number of this graph as χ V (G) =2 .
By defining the usual definition of k-coloring in fuzzy graphs we see that χ V (G) =3 .
The advantage of this proposed method of coloring is to identify the cluster of same groups based on the fuzzified membership values on vertices and define a strategy in any real time application.
The following results are analysed by using various methods of coloring for the graph taken in Example 6.1.
Fuzzified vague graph with vertex membershipvalues.
Table showing the methods of coloring in this graph as follows.
We could analyse some more concepts of coloring with different graphs based on these methods.
In this paper we analyse the concept of vague data set and its applications on fuzzy graph pertaining to the well defined vague graphs. We relate the vertex membership values of the vague graphs and propose different methods of coloring based on the membership values and understand some of the concepts on critical conditions on complete vague graphs. We also study some methods on fuzzification of vague data set into fuzzy membership values. Analyse our new method of coloring to the strategy of fuzzified graph with fuzzy vertices and crisp edges in vague graphs. We try to extend this result to many families of graphs and compare the chromatic number of these graphs and also study some of its applications in real time and engineering fields.