Magic labeling on interval-valued intuitionistic fuzzy graphs

1 Introduction

Graph theory has found its importance in many real time problems. Recent applications in graph theory is quite interesting analysing any complex situations and moreover in engineering applications. It has got numerous applications on operations research, system analysis, network routing, transportation and many more. To analyse any complete information we make intensive use of graphs and its properties. For working on partial informations or incomplete informations or to handle the systems containing the elements of uncertainty we understand that fuzzy logic and its involvement in graph theory is applied. In 1975, Rosenfeld [17] discussed the concept of fuzzy graphs whose ideas are implemented by Kauffman [12] in 1973. The fuzzy relation between fuzzy sets were also considered by Rosenfeld who developed the structure of fuzzy graphs, obtaining various analagous results of several graph theoretical concepts. Bhattacharya [4] gave some remarks of fuzzy graphs. The complement of fuzzy graphs was introduced by Mordeson [13]. Atanassov introduced the concept of intuitionistic fuzzy relation and intuitionistic fuzzy graphs [2, 31]. Talebi and Rashmanlou [34] studied the properties of isomorphism and complement of interval - valued fuzzy graphs. They defined isomorphism and some new operations on vague graphs [35, 36]. Borzooei and Rashmalou analysed new concepts of vague graphs  [5], degree of vertices in vague graphs [6], more results on vague graphs  [7], Semi global domination sets in vague graphs with application [8] and degree and total degree of edges in bipolar fuzzy graphs with application [9]. Rashmanlou et al., defined the complete interval-valued fuzzy graphs [18]. Rashmanlou and Pal defined intuitionistic fuzzy graphs with categorical properties [23], some properties of highly irregular interval - valued fuzzy graphs [22], more results on highly irregular bipolar fuzzy graphs [24], balanced interval valued fuzzy graphs [20] and antipodal interval valued fuzzy graphs [19]. Samanta and Pal defined fuzzyk-competition and p-competition graphs in  [25]. Also they introduced fuzzy tolerance graph [32], bipolar fuzzy hypergraphs [33] and investigated several properties on it. Pal and Rashmanlou [14] studied lot of properties of irregular interval valued fuzzy graphs. S. Sahoo and M. Pal [28, 29] introduced the concepts of Intuitionistic fuzzy tolerance graphs with applications and analysed about product of intuitionistic fuzzy graphs and degree. Also they analysed [26, 27] different products on intutionistic fuzzy graphs and studied about Intuitionistic fuzzy competition graphs. S.N. Mishra and A. Pal [15] studied about the concepts of magic labeling on Interval-valued fuzzy graphs. In this article we define the intuitionistic interval-valued fuzzy graph(IVIFS) and analyse its labeling properties. We implement the ideas of magic labeling to IVIFS and define some structures of IVIFS. We also discuss some properties of star IVIFS and find the lower and upper bounds based on ε neighborhood. For other notations and terminologies in this paper, the readers are referred to [1–6, 11].

2 Preliminaries

In this section we define some definitions which are prerequisites applied throughout this paper.

Definition 2.1. By an interval-valued fuzzy graph of a graph G we mean a pair G^* = (A, B) where A = [ μ A - , μ A + ] and μ _e  : V × V → [0, 1] are bijective such that membership value of nodes and edges are distinct and μ _e  (x, y) ≤ μ _v  (x) ∧ μ _v  (y) ∀ x, y ∈ V.

Definition 2.2. A fuzzy labeling graph is said to be a fuzzy magic graph if μ _v  (u) + μ _e  (u, v) + μ _v  (v) has a same magic value for all u, v ∈ V.

Definition 2.3. A graph G^* = (A, B) is said to be an interval-valued fuzzy labeling graph, if μ A - , μ A + , μ B - , μ B + ∈ [ 0 , 1 ] all are distinct for each nodes and edges, where μ A - is lower limit and μ A + is the upper limit of the interval membership of nodes, similarly, μ B - , μ B + are lower and upper limit respectively of the interval membership of edges.

Definition 2.4. An interval [μ - ε, μ + ε] is said to be an ε-neighborhood of any membership value (ie., corresponding to any nodes or edges) μ for any ε satisfying the following conditions.

εnotgreaterthanmin {μ _v  (v _i ) , μ _e  (e _ij )}

Definition 2.5. By an interval-valued intuitionistic fuzzy graph of a graph G we mean a pair G^* = (A, B) where A = [ ( μ A - , μ A + ) , ( ν A - , ν A + ) ] and μ _e  : V × V → [0, 1] and ν _e  : V × V → [0, 1] are bijective such that true and false membership value of nodes and edges are distinct and μ _e  (x, y) ≤ μ _v  (x) ∧ μ _v  (y) ∀ x, y ∈ V, ν _e  (x, y) ≥ ν _v  (x) ∨ ν _v  (y) ∀ x, y ∈ V.

Definition 2.6. A intuitionistic fuzzy labeling graph is said to be a intuitionistic fuzzy magic graph if μ _v  (u) + μ _e  (u, v) + μ _v  (v) and ν _v  (u) + ν _e  (u, v) + ν _v  (v) has a same magic value for all u, v ∈ V.

Definition 2.7. A graph G^* = (A, B) is said to be an interval-valued intuitionistic fuzzy labeling graph, if μ A - , μ A + , μ B - , μ B + ∈ [ 0 , 1 ] and ν A - , ν A + , ν B - , ν B + ∈ [ 0 , 1 ] all are distinct for each nodes and edges, where μ A - and ν A - is lower limit and μ A + and ν A + is the upper limit of the interval membership of nodes, similarly, μ B - , ν B - , μ B + , ν B + are lower and upper limits respectively of the true and false interval membership of edges.

Proposition 2.8. Any intuitionistic fuzzy graph can be converted into interval-valued intuitionistic fuzzy labeling graph.

Proof. We know that intuitionistic fuzzy graph is not an intuitionistic fuzzy labeling graph. Thus for labeling any intuitionistic fuzzy graph we consider the interval-valued intuitionistic membership of all nodes and edges in such a way that the graph obtained is labeled.

For this we take the ε-neighborhood corresponding to each node and edge, here we claim that it gives an intuitionistic interval-valued labeling graph. For any intuitionistic fuzzy graph only three cases are there, either all nodes and edges have same membership value, or only few nodes and edges have same membership value or all nodes and edges have distinct membership values.

case(i): If all the nodes and edges have same true and false membership values, then if the sum of the number of nodes and edges is n then we take n distinct ε as defined above and on assigning ε-neighborhood, we get an interval-valued intutionistic fuzzy labeling graph.

case(ii): If only few nodes and edges have same true and false membership value, then firstly we make a list of all membership values and corresponding nodes or edges, from it we take a set of true and false membership values and assign one ε = ε₁ for them and strike off those membership values and corresponding nodes or edges from the list. Again we take another set of membership values from the remaining element of the list and assign another ε = ε₂ to them and again we strike off the assigned true or false membership values and corresponding nodes or edges from the list. Continue this process till the last element in the list. Thus corresponding to each ε _i , i = 1, 2, . . . we get distinct ε-neighborhood interval, assigning it to the corresponding nodes and edges, we obtain an interval-valued intuitionistic fuzzy graph satisfies the condition of interval-valued intuitionistic fuzzy labeling.

case(iii): If all nodes and edges have distinct true and false membership value, then we can take only one ε and we get distinct ε-neighborhood corresponding to each nodes and edges.

Hence in each case we can convert a intuitionistic fuzzy graph into interval-valued intuitionistic fuzzy labeling graph. □

Example 2.9. Let G ˜ be a intuitionistic fuzzy graph with 3 vertices and 2 edges having its true and false membership values. We obtain a interal-valued intuitionistic fuzzy labeling graph G^*. We take the list of membership values of the graph G ˜ = { 0.3 , 0.45 , 0.4 , 0.5 , 0.3 , 0.55 , 0.25 , 0.55 , 0.2 , 0.6 } corresponding to v₁, v₂, v₃, v₁v₂, v₂v₃. A set W is formed from all distinct true and false membership values in the list G ˜ is W = {0.3, 0.45, 0.4, 0.5, 0.55, 0.25, 0.2, 0.6} corresponding to the vertices and edges membership values. Set ε = 0.02 and strike off those element from the list G ˜ which are in W. Again we consider another set W₁ formed from G ˜ - W and so we see W₁ = {0.55, 0.3} corresponding to remaining vertices and edges membership values. Striking off those elements from G ˜ - W the list G ˜ becomes empty and hence the interval-valued intuitionistic fuzzy labeling graph is obtained which is shown in Fig. 1 above.

OPEN IN VIEWER

Fig.1

IFG and IF labeling graph G.

Definition 3.1. An Interval-valued intuitionistic fuzzy labeling graph is said to be an interval-valued intuitionistic fuzzy magic graph if the sum of lower magic membership values for both true and false relations remain equal for all x, y ∈ V and the upper magic membership values for both true and false relations remain equal for all x, y ∈ V. The lower magic membership values are denoted by m 0 - ( G * ) and n 0 - ( G * ) and upper magic membership values are denoted by m 0 + ( G * ) and n 0 + ( G * ) . We denote an interval-valued intuitionistic fuzzy magic graph by MN₀ (G^*).

Example 3.2. In this example we see an interval-valued intuitionistic fuzzy magic labeling cycle graph with three vertices and three edges given in Fig. 2. In this graph μ A - ( v i ) + μ B - ( v i , v j ) + μ A - ( v j ) for all vertices v _i and v _j gives 0.21, μ A + ( v i ) + μ B + ( v i , v j ) + μ A - ( v j for all vertices v _i and v _j gives 0.2. Similarly ν A - ( v i ) + ν B - ( v i , v j ) + ν A - ( v j for all vertices v _i and v _j gives 0.23, ν A + ( v i ) + ν B + ( v i , v j ) + ν A - ( v j ) for all vertices v _i and v _j gives 1.35. Here m 0 - ( G * ) = 0.21 , m 0 + ( G * ) = 0.2 and n 0 - ( G * ) = 0.23 , n 0 + ( G * ) = 1.35 . Hence the graph is magic labeled.

OPEN IN VIEWER

Fig.2

Interval-valued Intuionistic fuzzy magic graph.

Proposition 3.3. Every intuitionistic fuzzy magic graph can be converted into interval-valued intuitionistic fuzzy magic graph.

Proof. We see that in intuitionistic fuzzy magic graph all the vertices and edges assigns distinct membership values. Let the true and false membership values of vertices be μ _v  (v _i ) and ν _v  (v _i ) and the edges be μ _e  (e _ij ) and ν _e  (e _ij ) for the vertices v _i and v _j . Let the sum of true and false membership values for each pair of vertices and edges is S₁ and S₂ respectively.

ie., S₁ = μ _v  (v _i ) + μ _e e _s quo (ij) + μ _v  (v _j ) and S₂ = μ _v  (v _i ) + μ _e  (e _ij ) + μ _v  (v _j ).

Now we can find M = max {μ _v  (v _i ) , μ _e  (e _ij )} and N = max {ν _v  (v _i ) , ν _e  (e _ij )}, m = min {μ _v  (v _i ) , μ _e  (e _ij )} and n = min {ν _v  (v _i ) , ν _e  (e _ij )}, then we choose any ε which satisfy additional conditions M + ε ≤ 1,N + ε ≤ 1 and m + ε ≥ 0, n + ε ≥ 0.

Now, replace the true and false membership value of each vertices with [μ _v  (v _i ) - ε, μ _v  (v _i ) + ε], [ν _v  (v _i ) - ε, ν _v  (v _i ) + ε] and each edges by [μ _e  (e _ij ) - ε, μ _e  (e _ij ) + ε], [ν _e  (e _ij ) - ε, ν _e  (e _ij ) + ε].

Since intuitionistic fuzzy magic graph admits all distinct true and false membership values for each vertices and edges, we choose ε satisfying the conditions of definition and the conditions mentioned above. Hence we always get the disjoint interval because intervals are symmetric about ε. In this way the constructed graph becomes an intuitionistic interval-valued fuzzy magicgraph. □

Example 3.4. In this example we obtain an interval-valued intuitionistic fuzzy magic labeled graph G^* from a intuitionistic fuzzy magic graph G ˜ . In Fig. 3 we see that G ˜ is a intuitionistic fuzzy magic labeled graph whose magic values are 0.18 and 0.21 respectively. Now, on taking ε = 0.02 we getε-neighborhood intervals for G^*. We observe that this interval-valued intuitionistic fuzzy graph satisfies all the conditions of magic labeling of interval-valued intuitionistic fuzzy graph.

OPEN IN VIEWER

Fig.3

IF magic labeled graph and IVIF magic graph.

OPEN IN VIEWER

Fig.4

Path IF labeled graphs and IVIF magic path G.

Proposition 3.5. Any intuitionistic fuzzy labeled graph can be converted into interval-valued intuitionistic fuzzy magic graph but the interval true and false memberships never be mutually disjoint.

Proof. The intuitionistic fuzzy labeled graph assigns some true and false membership values for its vertice and edges which are bijective. Thus we can find some ε which can be added to the each corresponding vertices and edges. Hence we obtain the magic sum for each pair of vertices and related edges. We assume that as the upper limit for the intervals. Now for the lower limit of the interval we just multiply all the obtained upper limits by 0.1 as 1 is the identity for multiplication and place of decimal provides the length for the interval shown in Figure. Continuing this process we see that the interval-valued intuitionistic fuzzy graph satisfies the condition of magic labeling. But the resultant interval need not be mutually disjoint as we choose the length of the interval as arbitrary selection. □

Example 3.6. A path intuitionistic fuzzy labeled graph with 3 vertices which is converted into interval-valued fuzzy magic graph. In this example, for vertices v₁ and edge v₁v₂ we assign ε = 0.02. For the vertices v₂ and the edge v₂v₃ we assign ε = 0.03 and for the vertex v₃ we assign ε = 0.01.

After adding ε to concern vertices and edges of true and false membership values we consider the upper limits alone. ie., we get μ A + ( v i ) + μ A + ( v i v j ) + μ A + ( v j ) value as 0.77 and ν A + ( v i ) + ν A + ( v i v j ) + ν A + ( v j ) value as 1.87. Now we multiply these values by 0.1 to obtain the lower limit sum as μ A + ( v i ) + μ A + ( v i v j ) + μ A + ( v j ) value as 0.077 and ν A + ( v i ) + ν A + ( v i v j ) + ν A + ( v j ) value as 0.187 respectively satisfying the the conditions of magic labeling of an interval-valued intuitionistic fuzzy graph.

Definition 3.7. A star in a intuitionistic fuzzy graph consist of two vertex sets V and U with |V|=1 and |U|>1, such that μ _e  (v, u _i ) >0, ν _e  (v, u _i ) >0 and μ _e  (u _i , u_i+1) =0,ν _e  (u _i , u_i+1) =0, i ≤ i ≤ n. It is denoted by S_1,n.

Proposition 3.8. A intutionistic fuzzy labeled graph need not be an interval-valed intuitionistic fuzzy magic graph.

Proof. It is possible that in a intuitionistic fuzzy labeled star graph there may be infinite number of pendant vertices and for those vertices we need mutually disjoint true and false membership for each edges incident to it. In this case, it is impossible to find an ε-neighborhood interval for each pendant vertices and edges, so that the lower limit of membership interval for each pair of vertices and edges remains equal which is a similar condition for upper limits of the true and false memberships. Hence we conclude that a intuitionistic fuzzy star graph need not be an interval-valed fuzzy magic graph. □

Example 3.9. An intuitionistic fuzzy labeled star graph with three pendant verices which is not an interval-valued intuitionistic fuzzy magic graph. Here some of the vertices and edges have different true and false membership values, but we see that μ A - ( v ) + μ B - ( v , u j ) + μ A - ( u j ) , ν A - ( v ) + ν B - ( v , u j ) + ν A - ( u j ) for each pair of vertices and edges are 0.077, 0.087, 0.076, 0.215, 0.104, 0.194. Similarly μ A + ( v ) + μ B + ( v , u j ) + μ A + ( u j ) , ν A + ( v ) + ν B + ( v , u j ) + ν A + ( u j ) for each pair of vertices and edges are 0.77, 0.87, 0.76, 2.15, 1.04, 1.94 which does not satisfy the conditions of magic labeling.

OPEN IN VIEWER

Fig.5

IVIF labeled star S₁₃ which is not magic labeled.

Proposition 3.10. Every cycle with odd number of vertices are always an interval-valued intuitionistic fuzzy magic graph.

Proof. Let G be a cycle with odd number of vertices say v₁, v₂, v₃, . . . v _n and v₁v₂, v₂v₃, . . . , v _n v₁ be the edges corresponding to it. Let ε ∈ [0, 1] such that we choose ε₁ = 0.01 for lower limit and ε₂ = 0.1 for upper limit for n ≤ 3 and for n ≤ 4 we can choose ε₁ = 0.001 for lower limit and set the membership interval as follows μ A - ( v 2 i ) = ( 2 n + i ) ε 1 , 1 ≤ i ≤ ( n - 1 ) 2 μ A + ( v 2 i ) = ( 2 n + i ) ε 2 , 1 ≤ i ≤ ( n - 1 ) 2 ν A - ( v 2 i ) = ( 2 n + i ) ε 1 , 1 ≤ i ≤ ( n - 1 ) 2 ν A + ( v 2 i ) = ( 2 n + i ) ε 2 , 1 ≤ i ≤ ( n - 1 ) 2 and μ A - ( v 2 i - 1 ) = min { μ A - ( v 2 i ) / 1 ≤ i ≤ ( n - 1 ) 2 - i ε 1 } μ A + ( v 2 i - 1 ) = min { μ A + ( v 2 i ) / 1 ≤ i ≤ ( n - 1 ) 2 - i ε 2 } ν A - ( v 2 i - 1 ) = min { ν A - ( v 2 i ) / 1 ≤ i ≤ ( n - 1 ) 2 - i ε 1 } ν A + ( v 2 i - 1 ) = min { ν A + ( v 2 i ) / 1 ≤ i ≤ ( n - 1 ) 2 - i ε 2 } .

Similarly, μ B - ( v 1 , v n ) = 1 2 max { μ A - ( v i ) / 1 ≤ i ≤ n } μ B + ( v 1 , v n ) = 1 2 max { μ A + ( v i ) / 1 ≤ i ≤ n } ν B - ( v 1 , v n ) = 1 2 max { ν A - ( v i ) / 1 ≤ i ≤ n } ν B + ( v 1 , v n ) = 1 2 max { ν A + ( v i ) / 1 ≤ i ≤ n } and μ B - ( v n - i + 1 , v n - i ) = μ B - ( v 1 , v n ) - i ε 1 , 1 ≤ i ≤ n - 1 μ B + ( v n - i + 1 , v n - i ) = μ B - ( v 1 , v n ) - i ε 2 , 1 ≤ i ≤ n - 1 ν B - ( v n - i + 1 , v n - i ) = ν B - ( v 1 , v n ) - i ε 1 , 1 ≤ i ≤ n - 1 ν B + ( v n - i + 1 , v n - i ) = ν B - ( v 1 , v n ) - i ε 2 , 1 ≤ i ≤ n - 1

Case(i): When i is even, let i = 2k for any positive integer k. For each edge v _i , v_i+1 m 0 - ( C n ) = μ A - ( v i ) + μ B - ( v i , v i + l ) + μ A - ( v i + 1 ) = μ A - ( v 2 k ) + μ B - ( v 2 k , v 2 k + 1 ) + μ A - ( v 2 k + 1 ) = ( 2 n + 1 - k ) ε 1 + 1 2 max { μ A - ( v i ) / 1 ≤ i ≤ n } - n - 2 k ε 1 + min { μ A - ( v 2 i ) / 1 ≤ i ≤ ( n - 1 ) 2 } + n ( ε 1 ) = 1 2 max { μ A - ( v i ) / 1 ≤ i ≤ n } + min { μ A - ( v 2 i / 1 ≤ i ≤ ( n - 1 ) 2 + n ( ε 1 ) } and m 0 + ( C n ) = μ A + ( v i ) + μ B + ( v i , v i + l ) + μ A + ( v i + 1 ) = μ A + ( v 2 k ) + μ B + ( v 2 k , v 2 k + 1 ) + μ A + ( v 2 k + 1 ) = ( 2 n + 1 - k ) ε 2 + 1 2 max { μ A - ( v i ) / 1 ≤ i ≤ n } - n - 2 k ε 2 + min { μ A + ( v 2 i ) / 1 ≤ i ≤ ( n - 1 ) 2 } + n ( ε 2 ) = 1 2 max { μ A + ( v i ) / 1 ≤ i ≤ n } + min { μ A + ( v 2 i / 1 ≤ i ≤ ( n - 1 ) 2 + n ( ε 2 ) } .

Similarly we can prove the result for false magic membership values n 0 - ( C n ) and n 0 + ( C n ) .

Case(ii): When i is odd, let i = 2k + 1 for any positive integer k. For each edge v _i , v_i+1 m 0 - ( C n ) = μ A - ( v i ) + μ B - ( v i , v i + l ) + μ A - ( v i + 1 ) = μ A - ( v 2 k + 1 ) + μ B - ( v 2 k + 1 , v 2 k + 2 ) + μ A - ( v 2 k + 2 ) = min { μ A - ( v 2 i ) / 1 ≤ i ≤ ( n - 1 ) 2 } - ( k + 1 ) ( ε 1 ) + 1 2 max { μ A - ( v i ) / 1 ≤ i ≤ n } - ( n - 2 k - 1 ) ε 1 + ( 2 n - k ) ε 1 = 1 2 max { μ A - ( v i ) / 1 ≤ i ≤ n } + min { μ A - ( v 2 i / 1 ≤ i ≤ ( n - 1 ) 2 + n ( ε 1 ) } and m 0 + ( C n ) = μ A + ( v i ) + μ B + ( v i , v i + l ) + μ A + ( v i + 1 ) = μ A + ( v 2 k + 1 ) + μ B + ( v 2 k + 1 , v 2 k + 2 ) + μ A + ( v 2 k + 2 ) = 1 2 max { μ A + ( v i ) / 1 ≤ i ≤ n } + min { μ A + ( v 2 i / 1 ≤ i ≤ ( n - 1 ) 2 + n ( ε 2 ) } .

Similarly we can prove the result for the false magic membership values n 0 - ( C n ) and n 0 + ( C n ) .

Hence from the above cases we can say that the odd cycle is always an interval-valued intuitionistic fuzzy magic graph. It is not always true for even cycle because when we apply this process for even cycle then some vertices receive such interval membership (true and false) which violates the condition of magic labeling on it. □

Proposition 3.11. Every interval-valued intuitionistic fuzzy magic graph whose interval memberships are ε-neighborhood of a fuzzy graph, always contains atleast one fuzzy bridge.

Proof. Any intuitionistic fuzzy graph G ¯ can be labeled by many ways as discussed above. When we label it by taking ε-neighborhood interval membership then it contains atleat one fuzzy bridge. Because, if an ε-neighborhood interval-valued intuitionstic fuzzy graph is magic labeled then it is necessarily be obtained from such an intuitionistic fuzzy graph where every vertices and edges admits different true and false membership values. Otherwise we could not say that interval-valued intuitionistic fuzzy magic graph is magic labeled. Hence it is clear that ε-neighborhood interval-valued intuitionistic fuzzy magic graph have all different interval memberships for vertices and edges (both true and false). On taking interval membership of every vertices and edges there must exist atleast one interval membership for every vertices and edges whose lower limit is the infimum and upper limit of the interval is also the infimum among all interval memberships of edges because, intervals are symmetric about ε. Thus we can find an edge for which the conditions μ_∞ (u, v) < μ (u, v) and ν_∞ (u, v) > ν (u, v) would satisfy. Hence the edge must be the only fuzzy bridge. Hence the result. □