Intuitionistic Fuzzy Planar Graphs

Abstract

Graph theory has numerous applications in modern sciences and technology. Atanassov introduced the concept of intuitionistic fuzzy sets as a generalization of fuzzy sets. Intuitionistic fuzzy set has shown advantages in handling vagueness and uncertainty compared to fuzzy set. In this paper, we apply the concept of intuitionistic fuzzy sets to multigraphs, planar graphs, and dual graphs. We introduce the notions of intuitionistic fuzzy multigraphs, intuitionistic fuzzy planar graphs, and intuitionistic fuzzy dual graphs and investigate some of their interesting properties. We also study isomorphism between intuitionistic fuzzy planar graphs.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Noura Alshehri 1 and Muhammad Akram 2

Academic Editor:Zuo-nong Zhu

1, Department of Mathematics, Faculty of Sciences (Girls), King Abdulaziz University, Jeddah, Saudi Arabia
2, Department of Mathematics, University of the Punjab, New Campus, Lahore, Pakistan

Received 21 April 2014; Accepted 7 August 2014; 24 August 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Graph theory is now a very important research area due to its wide applications. There are many practical applications with a graph structure in which crossing between edges is nuisance including design problems for circuits, subways, and utility lines. Crossing of two connections normally means that the communication lines must be run at different heights. This is not a big issue for electrical wires, but it creates extra expenses for some types of lines. Circuits, in particular, are easier to manufacture if their connections can be constructed in fewer layers. These applications are designed by the concept of planar graphs. Circuits, where crossing of lines is necessary, can not be represented by planar graphs. Numerous computational challenges can be solved by means of cuts of planar graph. In the city planning, subway tunnels, pipelines, and metro lines are essential in twenty first century. Due to crossing, there is a chance for an accident. Also, the cost of crossing of routes in underground is high. But underground routes reduce the traffic jam. In a city planning, routes without crossing are perfect for safety. But due to lack of space, crossing of such lines is allowed. It is easy to observe that the crossing between one congested and one noncongested route is better than the crossing between two congested routes. The term "congested" has no definite meaning. We generally use "congested," "very congested," "highly congested" routes, and so forth. These terms are called linguistic terms and they have some membership values. A congested route may be referred to as strong route and low congested route may be called weak route. Thus crossing between strong route and weak route is more safe than the crossing between two strong routes. That is, crossing between strong route and weak route may be allowed in city planning with certain amount of safety. The terms strong route and weak route lead to strong edge and weak edge of a fuzzy graph, respectively. And the permission of crossing between strong and weak edges leads to the concept of fuzzy planar graph [1-3].

Presently, science and technology is featured with complex processes and phenomena for which complete information are not always available. For such cases, mathematical models are developed to handle various types of systems containing elements of uncertainty. A large number of these models are based on an extension of the ordinary set theory, namely, fuzzy sets. The notion of fuzzy sets was introduced by Zadeh [4] as a method of representing uncertainty and vagueness. Since then, the theory of fuzzy sets has become a vigorous area of research in different disciplines. In 1983, Atanassov [5] introduced the concept of intuitionistic fuzzy sets as a generalization of fuzzy sets. Atanassov added in the definition of fuzzy set a new component which determines the degree of nonmembership. Fuzzy sets give the degree of membership of an element in a given set (the nonmembership of degree equals one minus the degree of membership), while intuitionistic fuzzy sets give both a degree of membership and a degree of nonmembership, which are more or less independent from each other; the only requirement is that the sum of these two degrees is not greater than 1 . Intuitionistic fuzzy sets are higher order fuzzy sets. Application of higher order fuzzy sets makes the solution-procedure more complex, but if the complexity on computation-time, computation-volume or memory-space are not the matter of concern then a better result could be achieved.

Fuzzy graph theory is finding an increasing number of applications in modeling real time systems where the level of information inherent in the system varies with different levels of precision. Fuzzy models are becoming useful because of their aim in reducing the differences between the traditional numerical models used in engineering and sciences and the symbolic models used in expert systems. Kauffman's initial definition of a fuzzy graph [6] was based on Zadeh's fuzzy relations [7]. Rosenfeld [8] introduced the fuzzy analogue of several basic graph-theoretic concepts and Bhattacharya [9] gave some remarks on fuzzy graphs. Mordeson and Nair [10] defined the concept of complement of fuzzy graph and studied some operations on fuzzy graphs. In [11], the definition of complement of a fuzzy graph was modified so that the complement of the complement is the original fuzzy graph, which agrees with the crisp graph case. Shannon and Atanassov [12] introduced the concept of intuitionistic fuzzy relations and intuitionistic fuzzy graphs and investigated some of their properties in [13]. Parvathi et al. defined operations on intuitionistic fuzzy graphs in [14]. Akram et al. [15-18] introduced many new concepts including intuitionistic fuzzy hypergraphs, strong intuitionistic fuzzy graphs, intuitionistic fuzzy cycles, and intuitionistic fuzzy trees. Abdul-Jabbar et al. [1] introduced the concept of a fuzzy dual graph and discussed some of its interesting properties. Recently, Pal et al. [2] and Samanta et al. [3] introduced and investigated the concept of fuzzy planar graphs and studied several properties. In this paper, we apply the concept of intuitionistic fuzzy sets to multigraphs, planar graphs, and dual graphs. We introduce the notions of intuitionistic fuzzy multigraphs, intuitionistic fuzzy planar graphs, and intuitionistic fuzzy dual graphs and investigate some of their interesting properties. We also study isomorphism between intuitionistic fuzzy planar graphs. We have used standard definitions and terminologies in this paper. For other notations, terminologies, and applications not mentioned in the paper, the readers are referred to [8, 10, 14, 19-27].

2. Preliminaries

In this section, we review some elementary concepts whose understanding is necessary for full benefit from this paper.

By a graph we mean a pair ^G* =(V,E) , where V is the set and E is a relation on V . The elements of V are vertices of ^G* and the elements of E are edges of ^G* . We write xy ∈E to mean (x,y)∈E , and if e=xy∈E , we say x and y are adjacent . Formally, given a graph ^G* =(V,E) , two vertices x,y∈V are said to be neighbors, or adjacent nodes , if xy∈E . The number of vertices, the cardinality of V , is called the order of graph and denoted by |V| . The number of edges, the cardinality of E , is called the size of graph and denoted by |E| . A multigraph is a graph that may contain multiple edges between any two vertices, but it does not contain any self-loops. A graph can be drawn in many different ways. A graph may or may not be drawn on a plane without crossing of edges. A drawing of a geometric representation of a graph on any surface such that no edges intersect is called embedding . A graph ^G* is planar if it can be drawn in the plane with its edges only intersecting at vertices of ^G* . A crisp graph is called nonplanar graph if there is at least one crossing between the edges for all possible geometrical representations of the graph. A planar graph with cycles divides the plane into a set of regions are called faces . The length of a face in a plane graph ^G* is the total length of the closed walk(s) in ^G* bounding the face. The portion of the plane lying outside a graph embedded in a plane is infinite region. The dual graph of a plane graph ^G* is a graph that has a vertex corresponding to each face of ^G* and an edge joining two neighboring faces for each edge in ^G* . The term "dual" is used because this property is symmetric, meaning that if ^H* is a dual of ^G* , then ^G* is a dual of ^H* (if ^G* is connected).

Let X be a nonempty set. A fuzzy set [4] A drawn from X is defined as A={Y9;x:_μA (x)YA;:x∈X} , where μ:X[arrow right][0,1] is the membership function of the fuzzy set A . A fuzzy binary relation [7] on X is a fuzzy subset μ on X×X . By a fuzzy relation, we mean a fuzzy binary relation given by μ:X×X[arrow right][0,1] . A fuzzy graph [6] G=(V,σ,μ) is a nonempty set V together with a pair of functions σ:V[arrow right][0,1] and μ:V×V[arrow right][0,1] such that, for all x,y∈V , μ(x,y)...4;min...(σ(x),σ(y)) , where σ(x) and μ(x,y) represent the membership values of the vertex x and of the edge (x,y) in G , respectively. A loop at a vertex x in a fuzzy graph is represented by μ(x,x)...0;0 . An edge is nontrivial if μ(x,y)...0;0 . Let G be a fuzzy graph and, for a certain geometric representation, the graph has only one crossing between two fuzzy edges ((w,x),μ(w,x)) and ((y,z),μ(y,z)) . If μ(w,x)=1 and μ(y,z)=0 , then we say that the fuzzy graph has no crossing. Similarly, if μ(w,x) has value near to 1 and μ(y,z) has value near to 0 , the crossing will not be important for the planarity. If μ(y,z) has value near to 1 and μ(w,x) has value near to 1 , then the crossing becomes very important for the planarity.

Let X be a nonempty set. A fuzzy multiset [28] A drawn from X is characterized by a function, "count membership" of A denoted by _CMA such that _CMA :X[arrow right]Q , where Q is the set of all crisp multisets drawn from the unit interval [0,1] . Then for any x∈X , the value _CMA (x) is a crisp multiset drawn from [0,1] . For each x∈X , the membership sequence is defined as the decreasingly ordered sequence of elements in _CMA (x) . It is denoted by (^μA1 (x),^μA2 (x),^μA3 (x),...,^μAp (x)) where ^μA1 (x)...5;^μA2 (x)...5;^μA3 (x)...5;......5;^μAp (x) .

Let V be a nonempty set and σ:V[arrow right][0,1] a mapping and let μ={(x,y),μ(x,y_)j ,j=1,2,...,_pxy |"(x,y)∈V×V} be a fuzzy multiset of V×V such that μ(x,y_)j ...4;min...{σ(x),σ(y)} for all j=1,2,...,_pxy , where _pxy =max...{j|"μ(x,y_)j ...0;0} . Then G=(V,σ,μ) is denoted as fuzzy multigraph [2] where σ(x) and μ(x,y_)j represent the membership value of the vertex x and the membership value of the edge (x,y) in G , respectively. In 1983, Atanassov [5] introduced the concept of intuitionistic fuzzy sets as a generalization of fuzzy sets [4]. An intuitionistic fuzzy set (IFS, for short) on a universe X is an object of the form [figure omitted; refer to PDF] where _μA (x)(∈[0,1]) is called degree of membership of x in A and _νA (x)(∈[0,1]) is called degree of nonmembership of x in A , and _μA , _νA satisfies the following condition for all x∈X , _μA (x)+_νA (x)...4;1 . An intuitionistic fuzzy relation R=(_μR (x,y),_νR (x,y)) in a universe X×Y(R(X[arrow right]Y) , for short) is an intuitionistic fuzzy set of the form [figure omitted; refer to PDF] where _μR :X×Y[arrow right][0,1] and _νR :X×Y[arrow right][0,1] . The intuitionistic fuzzy relation R satisfies _μR (x,y)+_νR (x,y)...4;1 for all x,y∈X . An intuitionistic fuzzy graph is a pair G=(A,B) where A=Y9;V,_μA ,_νA YA; is an intuitionistic fuzzy set in V and B=Y9;V×V,_μB ,_νB YA; is an intuitionistic fuzzy relation on V such that [figure omitted; refer to PDF] such that 0...4;_μB (xy)+_νB (xy)...4;1 for all x,y∈V .

Let X be a nonempty set. An intuitionistic fuzzy multiset (IFMS) [29] A drawn from X is characterized by two functions: "count membership" of A (_CMA ) and "count nonmembership" of A (_CNA ) given by _CMA :X[arrow right]Q and _CNA :X[arrow right]Q where Q is the set of all crisp multisets drawn from the unit interval [0,1] such that, for each x∈X , the membership sequence is defined as a decreasingly ordered sequence of elements in _CMA (x) which is denoted by (^μA1 (x),^μA2 (x),^μA3 (x),...,^μAp (x)) where ^μA1 (x)...5;^μA2 (x)...5;^μA3 (x)...5;......5;^μAp (x) and the corresponding nonmembership sequence will be denoted by (^νA1 (x),^νA2 (x),^νA3 (x),...,^νAp (x)) such that ^μAi (x)+^νAi (x)...4;1 for all x∈X and i=1,2,...,p . An IFMS A is denoted by [figure omitted; refer to PDF]

We arrange the membership sequence in decreasing order but the corresponding nonmembership sequence may not be in decreasing or increasing order.

3. Intuitionistic Fuzzy Planar Graphs

We first introduce the notion of an intuitionistic fuzzy multigraph using the concept of an intuitionistic fuzzy multiset.

Definition 1.

Let A=(_μA ,_νA ) be an intuitionistic fuzzy set on V and let [figure omitted; refer to PDF] be an intuitionistic fuzzy multiset of V×V such that [figure omitted; refer to PDF] for all i=1,2,...,m . Then G is called an intuitionistic fuzzy multigraph .

Note that there may be more than one edge between the vertices x and y . _μB (xy_)i , _νB (xy_)i represent the membership value and nonmembership value of the edge xy in G , respectively. m denotes the number of edges between the vertices. In intuitionistic fuzzy multigraph G , B is said to be intuitionistic fuzzy multiedge set.

Example 2.

Consider a multigraph ^G* =(V,E) such that V={a,b,c,d} , E={ab,ab,ab,bc,bd} . Let A=(_μA ,_νA ) be an intuitionistic fuzzy set of V and let B=(_μB ,_νB ) be an intuitionistic fuzzy multiedge set of V×V defined by Table 1 and Figure 1.

Table 1

(a)

	a	b	c	d
μ A	0.5	0.4	0.5	0.4
ν A	0.3	0.4	0.3	0.4

(b)

	a b	a b	a b	b c	b d
μ B	0.2	0.1	0.2	0.3	0.1
ν B	0.2	0	0.2	0.3	0.2

Figure 1: Intuitionistic fuzzy multigraph.

[figure omitted; refer to PDF]

By routine computations, it is easy to see from Figure 1 that it is an intuitionistic fuzzy multigraph.

Definition 3.

Let B={(xy,_μB (xy_)i ,_νB (xy_)i ),i=1,2,...,m|"xy∈V×V} be an intuitionistic fuzzy multiedge set in intuitionistic fuzzy multigraph G . The degree of a vertex x∈V is denoted by deg... (x) and is defined by deg... (x)=(^∑i=1m_μB (xy_)i ,^∑i=1m_νB (xy_)i ) for all y∈V .

Example 4.

In Example 2, degrees of the vertices a,b,c,d are deg... (a)=(0.5,0.4) , deg... (b)=(0.9,0.9) , deg... (c)=(0.3,0.3) , and deg... (d)=(0.1,0.2) .

Definition 5.

Let B={(xy,_μB (xy_)i ,_νB (xy_)i ),i=1,2,...,m|"xy∈V×V} be an intuitionistic fuzzy multiedge set in intuitionistic fuzzy multigraph G . A multiedge xy of G is strong if (1/2)min...{_μA (x),_μA (y)}...4;_μB (xy_)i , (1/2)max...{_νA (x),_νA (y)}...4;_νB (xy_)i , for all i=1,2,...,m .

Definition 6.

Let B={(xy,_μB (xy_)i ,_νB (xy_)i ),i=1,2,...,m|"xy∈V×V} be an intuitionistic fuzzy multiedge set in intuitionistic fuzzy multigraph G . An intuitionistic fuzzy multigraph G is complete if min...{_μA (x),_μA (y)}=_μB (xy_)i , max...{_νA (x),_νA (y)}=_νB (xy_)i , for all i=1,2,...,m and for all x,y∈V .

Example 7.

Consider an intuitionistic fuzzy multigraph G as shown in Figure 2.

Figure 2: Intuitionistic fuzzy complete multigraph.

[figure omitted; refer to PDF]

By routine computations, it is easy to see from Figure 2 that it is an intuitionistic fuzzy complete multigraph.

Definition 8.

Strength of the intuitionistic fuzzy edge ab can be measured by the value [figure omitted; refer to PDF]

Definition 9.

Let G be an intuitionistic fuzzy multigraph. An edge ab is said to be intuitionistic fuzzy strong if _Mab ...5;0.5 or _Nab ...4;0.5 , otherwise weak.

Definition 10.

Let G be an intuitionistic fuzzy multigraph and let B contain two edges (ab,_μB (ab_)i ,_νB (ab_)i ) and (cd,_μB (cd_)j ,_νB (cd_)j ) which are intersected at a point P , where i and j are fixed integers. We define the intersecting value at the point P by [figure omitted; refer to PDF]

If the number of points of intersections in an intuitionistic fuzzy multigraph increases, planarity decreases. Thus for intuitionistic fuzzy multigraph, _IP is inversely proportional to the planarity. We now introduce the concept of an intuitionistic fuzzy planar graph.

Definition 11.

Let G be an intuitionistic fuzzy multigraph and let _P1 ,_P2 ,...,_Pz be the points of intersections between the edges for a certain geometrical representation; G is said to be an intuitionistic fuzzy planar graph with intuitionistic fuzzy planarity value f=(_fM ,_fN ) , where [figure omitted; refer to PDF]

Clearly, f=(_fM ,_fN ) is bounded and 0<_Mf ...4;1 ; _Nf is 0<_Nf ...4;1 . If there is no point of intersection for a certain geometrical representation of an intuitionistic fuzzy planar graph, then its intuitionistic fuzzy planarity value is (1,1) . In this case, the underlying crisp graph of this intuitionistic fuzzy graph is the crisp planar graph. If _fM decreases and _fN increases, then the number of points of intersection between the edges increases and decreases, respectively, and the nature of planarity decreases and decreases, respectively. We conclude that every intuitionistic fuzzy graph is an intuitionistic fuzzy planar graph with certain intuitionistic fuzzy planarity value.

Example 12.

Consider a multigraph ^G* =(V,E) such that V={a,b,c,d,e} , [figure omitted; refer to PDF] Let A=(_μA ,_νA ) be an intuitionistic fuzzy of V and let B=(_μB ,_νB ) be an intuitionistic fuzzy multiedge set of V×V defined by Table 2.

The intuitionistic fuzzy multigraph as shown in Figure 3 has two points of intersections _P1 and _P2 . _P1 is a point between the edges (ad,0.2,0.1) and (bc,0.2,0.1) and _P2 is between (ad,0.3,0.1) and (bc,0.2,0.1) . For the edge (ad,0.2,0.1) , _Iad =(0.4,0.5) , For the edge (ad,0.3,0.1) , _Iad =(0.6,0.5) , and for the edge (bc,0.2,0.1) , _Ibc =(0.6667,1) . For the first point of intersection _P1 , intersecting value _IP1 is (0.5335,0.75) and that for the second point of intersection _P2 , _IP2 =(0.63335,0.75) . Therefore, the intuitionistic fuzzy planarity value for the intuitionistic fuzzy multigraph shown in Figure 3 is (0.461,0.4) .

Table 2

(a)

	a	b	c	d	e
μ A	0.5	0.4	0.3	0.6	0.6
ν A	0.2	0.1	0.1	0.2	0.1

(b)

	a b	a c	a d	a d	b c	b d	c d	a e	c e	d e	b e
μ B	0.2	0.2	0.2	0.3	0.2	0.2	0.2	0.2	0.2	0.2	0.2
ν B	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1

Figure 3: Intuitionistic fuzzy planar graph.

[figure omitted; refer to PDF]

Intuitionistic fuzzy planarity value for the intuitionistic fuzzy complete multigraph is calculated from Theorem 13.

Theorem 13.

Let G be an intuitionistic fuzzy complete multigraph. The intuitionistic fuzzy planarity value f=(_Mf ,_Nf ) of G is given by _Mf =1/(1+_np ) and _Nf =1/(1+_np ) such that _Mf +_Nf ...4;1 , where _np is the number of points of intersections between the edges in G .

Definition 14.

An intuitionistic fuzzy planar graph G is called strong intuitionistic fuzzy planar graph if the intuitionistic fuzzy planarity value f=(_Mf ,_Nf ) of the graph is _Mf ...5;0.5 , _Nf ...4;0.5 .

Theorem 15.

Let G be a strong intuitionistic fuzzy planar graph. The number of points of intersections between strong edges in G is at most one.

Proof.

Let G be a strong intuitionistic fuzzy planar graph. Assume that G has at least two points of intersections _P1 and _P2 between two strong edges in G . For any strong edge (ab,_μB (ab_)i ,_νB (ab_)i ) , [figure omitted; refer to PDF] This shows that _Mab ...5;0.5 or _Nab ...4;0.5 . Thus for two intersecting strong edges (ab,_μB (ab_)i ,_νB (ab_)i ) and (cd,_μB (cd_)j ,_νB (cd_)j ) , [figure omitted; refer to PDF] that is, _MP1 ...5;0.5 , _NP1 ...4;0.5 . Similarly, _MP2 ...5;0.5 , _NP2 ...4;0.5 . This implies that 1+_MP1 +_MP2 ...5;2 , 1+_NP1 +_NP2 ...4;2 . Therefore, _fM =1/(1+_MP1 +_MP2 )...4;0.5 , _fN =1/(1+_NP1 +_NP2 )...5;0.5 . It contradicts the fact that the intuitionistic fuzzy graph is a strong intuitionistic fuzzy planar graph. Thus number of points of intersections between strong edges can not be two. Obviously, if the number of points of intersections of strong intuitionistic fuzzy edges increases, the intuitionistic fuzzy planarity value decreases. Similarly, if the number of points of intersection of strong edges is one, then the intuitionistic fuzzy planarity value _Mf >0.5 , _Nf <0.5 . Any intuitionistic fuzzy planar graph without any crossing between edges is a strong intuitionistic fuzzy planar graph. Thus, we conclude that the maximum number of points of intersections between the strong edges in G is one.

Theorem 16.

Let G be an intuitionistic fuzzy planar graph with intuitionistic fuzzy planarity value f=(_Mf ,_Nf ) . If _Mf ...5;0.67 , _Nf ...4;0.33 , G do not contain any point of intersection between two strong edges.

Definition 17.

Let G be an intuitionistic fuzzy graph. Let 0<c<0.5 be a rational number. An edge xy is said to considerable edge if [figure omitted; refer to PDF] If an edge is not considerable, it is called nonconsiderable edge. For intuitionistic fuzzy multigraph G , a multiedge xy is said to be considerable edge if _Mxy ...5;c , _Nxy ...4;c , for each edge xy in G .

Remark 18.

Let 0<c<0.5 be a rational number. If (_μB (xy)/min...{_μA (x),_μA (y)})...5;c , (_νB (xy)/max...{_μA (x),_μA (y)})...4;c for all edges xy of an intuitionistic fuzzy graph G , then the number c is said to be considerable number of the intuitionistic fuzzy graph. Considerable number of an intuitionistic fuzzy graph may not be unique, but it is countable. Clearly, for a specific value of c , a set of considerable edges is obtained and for different values of c one can obtain different sets of considerable edges. Actually, c is a preassigned number for a specific application.

Theorem 19.

Let G be a strong intuitionistic fuzzy planar graph with considerable number c . The number of points of intersections between considerable edges in G is at most [1/c] ( or 1/c-1) .

Proof.

Let G be a strong intuitionistic fuzzy planar graph, where E={(xy,_μB (xy_)i ,_νB (xy_)i ),i=1,2,...,m|" xy∈V×V} . Let 0<c<0.5 be the considerable number and let f=(_Mf ,_Nf ) be the intuitionistic fuzzy planarity value. For any considerable edge (ab,_μB (ab_)i ,_νB (ab_)i ) , [figure omitted; refer to PDF] This shows that _Mab ...5;c , _Nab ...4;c . Let _P1 ,_P2 ,...,_Pn be the n points of intersections between considerable edges. Then for the point _P1 between two intersecting considerable edges (ab,_μB (ab_)i ,_νB (ab_)i ) and (cd,_μB (cd_)j ,_νB (cd_)j ) , _MP1 =(_Mab +_Mcd )/2...5;c , _NP1 =(_Nab +_Ncd )/2...4;c . So ^∑i=1n_MPi ...5;n×c , ^∑i=1n_NPi ...4;n×c . Hence _Mf ...4;1/(1+nc) , _Nf ...5;1/(1+nc) . As G is strong intuitionistic fuzzy planar graph, 0.5<_Mf ...4;1/(1+nc) , 0.5>_Nf ...5;1/(1+nc) . Hence 0.5<1/(1+nc) . This implies n<1/c . This inequality will be satisfied for some integral values of n which are obtained from the following expression: [figure omitted; refer to PDF]

Face of an intuitionistic fuzzy planar graph is an important parameter. Face of an intuitionistic fuzzy graph is a region bounded by intuitionistic fuzzy edges. Every intuitionistic fuzzy face is characterized by intuitionistic fuzzy edges in its boundary. If all the edges in the boundary of an intuitionistic fuzzy face have membership and nonmembership values 1 and 0, respectively, it becomes crisp face. If one of such edges is removed or has membership and nonmembership values 0 and 1, respectively, the intuitionistic fuzzy face does not exist. So the existence of an intuitionistic fuzzy face depends on the minimum value of strength of intuitionistic fuzzy edges in its boundary. A intuitionistic fuzzy face and its membership values and nonmembership values of an intuitionistic fuzzy graph are defined below.

Definition 20.

Let G be an intuitionistic fuzzy planar graph and B={(xy,_μB (xy_)i ,_νB (xy_)i ),i=1,2,...,m|"xy∈V×V} . An intuitionistic fuzzy face of G is a region, bounded by the set of intuitionistic fuzzy edges ^{E[variant prime]} ⊂E , of a geometric representation of G . The membership and nonmembership values of the intuitionistic fuzzy face are [figure omitted; refer to PDF]

Definition 21.

An intuitionistic fuzzy face is called strong intuitionistic fuzzy face if its membership value is greater than 0.5 or nonmembership value is less than 0.5, and weak face otherwise. Every intuitionistic fuzzy planar graph has an infinite region which is called outer intuitionistic fuzzy face . Other faces are called inner intuitionistic fuzzy faces .

Example 22.

Consider an intuitionistic fuzzy planar graph as shown in Figure 4. The intuitionistic fuzzy planar graph has the following faces:

(i) intuitionistic fuzzy face _F1 is bounded by the edges (_v1v2 ,0.5,0.1) , (_v2v3 ,0.6,0.1) , and (_v1v3 ,0.5,0.1) ;

(ii) outer intuitionistic fuzzy face _F2 is surrounded by edges (_v1v3 ,0.5,0.1) , (_v1v4 ,0.5,0.1) , (_v2v4 ,0.6,0.1) , and (_v2v3 ,0.6,0.1) ;

(iii): intuitionistic fuzzy face _F3 is bounded by the edges (_v1v2 ,0.5,0.1) , (_v2v4 ,0.6,0.1) , and (_v1v4 ,0.5,0.1) .

Clearly, the membership value and nonmembership value of an intuitionistic fuzzy face _F1 are 0.833 and 0.333, respectively. The membership value and nonmembership value of an intuitionistic fuzzy face _F3 are also 0.833 and 0.333, respectively. Thus _F1 and _F3 are strong intuitionistic fuzzy faces.

Figure 4: Faces in intuitionistic fuzzy planar graph.

[figure omitted; refer to PDF]

We now introduce dual of intuitionistic fuzzy planar graph. In intuitionistic fuzzy dual graph, vertices are corresponding to the strong intuitionistic fuzzy faces of the intuitionistic fuzzy planar graph and each intuitionistic fuzzy edge between two vertices is corresponding to each edge in the boundary between two faces of intuitionistic fuzzy planar graph. The formal definition is given below.

Definition 23.

Let G be an intuitionistic fuzzy planar graph and let [figure omitted; refer to PDF] Let _F1 ,_F2 ,...,_Fk be the strong intuitionistic fuzzy faces of G . The intuitionistic fuzzy dual graph of G is an intuitionistic fuzzy planar graph ^{G[variant prime]} =(^{V[variant prime]} ,^{A[variant prime]} ,^{B[variant prime]} ) , where ^{V[variant prime]} ={_xi ,i=1,2,...,k} , and the vertex _xi of ^{G[variant prime]} is considered for the face _Fi of G . The membership and nonmembership values of vertices are given by the mapping ^{A[variant prime]} =(_{μ^{A[variant prime]}} ,_{ν^{A[variant prime]}} ):^{V[variant prime]} [arrow right][0,1] × [0,1] such that _{μ^{A[variant prime]}} (_xi )=max...{_{μ^{B[variant prime]}} (uv_)i , i=1,2,...,p|"uv is an edge of the boundary of the strong intuitionistic fuzzy face _Fi } , and _{ν^{A[variant prime]}} (_xi )=min...{_{ν^{B[variant prime]}} (uv_)i , i=1,2,...,p|"uv is an edge of the boundary of the strong intuitionistic fuzzy face _Fi } .

There may exist more than one common edge between two faces _Fi and _Fj of G . Thus there may be more than one edge between two vertices _xi and _xj in intuitionistic fuzzy dual graph ^{G[variant prime]} . Let ^μBl (_xixj ) denote the membership value of the l th edge between _xi and _xj , and ^νB1 (_xixj ) denote the nonmembership value of the l th edge between _xi and _xj . The membership and nonmembership values of the intuitionistic fuzzy edges of the intuitionistic fuzzy dual graph are given by _{μ^{B[variant prime]}} (_xixj)l =^μBl (uv_)j , _{ν^{B[variant prime]}} (_xixj)l =^νBl (uv_)j where (uv_)l is an edge in the boundary between two strong intuitionistic fuzzy faces _Fi and _Fj and l=1,2,...,s , where s is the number of common edges in the boundary between _Fi and _Fj or the number of edges between _xi and _xj . If there is any strong pendant edge in the intuitionistic fuzzy planar graph, then there will be a self-loop in ^{G[variant prime]} corresponding to this pendant edge. The edge membership and nonmembership value of the self-loop is equal to the membership and nonmembership value of the pendant edge. Intuitionistic fuzzy dual graph of intuitionistic fuzzy planar graph does not contain point of intersection of edges for a certain representation, so it is intuitionistic fuzzy planar graph with planarity value (1,1) . Thus the intuitionistic fuzzy face of intuitionistic fuzzy dual graph can be similarly described as in intuitionistic fuzzy planar graphs.

Example 24.

Consider an intuitionistic fuzzy planar graph G=(V,A,B) as shown in Figure 5 such that V={a,b,c,d} , A=(a,0.6,0.2),(b,0.7,0.2),(c,0.8,0.2),(d,0.9,0.1) , and B={(ab,0.5,0.01),(ac,0.4,0.01),(ad,0.55,0.01),(bc,0.45,0.01),(bc,0.6,0.01),(cd,0.7,0.01)}

Figure 5: Intuitionistic fuzzy dual graph.

[figure omitted; refer to PDF]

The intuitionistic fuzzy planar graph has the following faces:

(i) intuitionistic fuzzy face _F1 is bounded by (ab,0.5,0.01),(ac,0.4,0.01),(bc,0.45,0.01) ,

(ii) intuitionistic fuzzy face _F2 is bounded by (ad,0.55,0.01),(cd,0.7,0.01),(ac,0.4,0.01) ,

(iii): intuitionistic fuzzy face _F3 is bounded by (bc,0.45,0.01),(bc,0.6,0.01) ,

(iv) outer intuitionistic fuzzy face _F4 is surrounded by (ab,0.5,0.01) , (bc,0.6,0.01) , (cd,0.7,0.01) , (ad,0.55,0.01) .

Routine calculations show that all faces are strong intuitionistic fuzzy faces. For each strong intuitionistic fuzzy face, we consider a vertex for the intuitionistic fuzzy dual graph. So the vertex set ^{V[variant prime]} ={_x1 ,_x2 ,_x3 ,_x4 } , where the vertex _xi is taken corresponding to the strong intuitionistic fuzzy face _Fi , i=1,2,3,4 . Thus [figure omitted; refer to PDF] There are two common edges ad and cd between the faces _F2 and _F4 in G . Hence between the vertices _x2 and _x4 , there exist two edges in the intuitionistic fuzzy dual graph of G . Membership and nonmembership values of these edges are given by [figure omitted; refer to PDF] The membership and nonmembership values of other edges of the intuitionistic fuzzy dual graph are calculated as [figure omitted; refer to PDF] Thus the edge set of intuitionistic fuzzy dual graph is [figure omitted; refer to PDF] In Figure 5, the intuitionistic fuzzy dual graph ^{G[variant prime]} =(^{V[variant prime]} ,^{A[variant prime]} ,^{B[variant prime]} ) of G is drawn by dotted line.

Weak edges in planar graphs are not considered for any calculation in intuitionistic fuzzy dual graphs. We state the following theorems without their proofs.

Theorem 25.

Let G be an intuitionistic fuzzy planar graph whose number of vertices, number of intuitionistic fuzzy edges, and number of strong faces are denoted by n , p , m , respectively. Let ^{G[variant prime]} be the intuitionistic fuzzy dual graph of G . Then

(i) the number of vertices of ^{G[variant prime]} is equal to m ,

(ii) number of edges of ^{G[variant prime]} is equal to p ,

(iii): number of intuitionistic fuzzy faces of ^{G[variant prime]} is equal to n .

Theorem 26.

Let G=(V,A,B) be an intuitionistic fuzzy planar graph without weak edges and let the intuitionistic fuzzy dual graph of G be ^{G[variant prime]} =(^{V[variant prime]} ,^{A[variant prime]} ,^{B[variant prime]} ) . The membership and nonmembership values of intuitionistic fuzzy edges of ^{G[variant prime]} are equal to membership and nonmembership values of the intuitionistic fuzzy edges of G .

We now study isomorphism between intuitionistic fuzzy planar graphs.

Definition 27.

Let _G1 and _G2 be intuitionistic fuzzy graphs. An isomorphism f:_G1 [arrow right]_G2 is a bijective mapping f:_V1 [arrow right]_V2 which satisfies the following conditions:

(c) : _μA1 (_x1 )=_μA2 (f(_x1 )) , _νA1 (_x1 )=_νA2 (f(_x1 )) ,

(d) : _μB1 (_x1y1 )=_μB2 (f(_x1 )f(_y1 )) , _νB1 (_x1y1 )=_νB2 (f(_x1 )f(_y1 )) ,

for all _x1 ∈_V1 , _x1y1 ∈_E1 .

Definition 28.

Let _G1 and _G2 be intuitionistic fuzzy graphs. Then, a weak isomorphism f:_G1 [arrow right]_G2 is a bijective mapping f:_V1 [arrow right]_V2 which satisfies the following conditions:

(e) : f is homomorphism,

(f) : _μA1 (_x1 )=_μA2 (f(_x1 )) , _νA1 (_x1 )=_νA2 (f(_x1 )) ,

for all _x1 ∈_V1 .

Definition 29.

Let _G1 and _G2 be the intuitionistic fuzzy graphs. A co-weak isomorphism f:_G1 [arrow right]_G2 is a bijective mapping f:_V1 [arrow right]_V2 which satisfies that

(g) : f is homomorphism,

(h) : _μB1 (_x1y1 )=_μB2 (f(_x1 )f(_y1 )) , _νB1 (_x1y1 )=_νB2 (f(_x1 )f(_y1 )) ,

for all _x1y1 ∈_V1 .

It is known that isomorphism between intuitionistic fuzzy graphs is an equivalence relation. If there is an isomorphism between two intuitionistic fuzzy graphs such that one is an intuitionistic fuzzy planar graph, then the other will be intuitionistic fuzzy graph. We state the following result without its proof.

Theorem 30.

Let G be an intuitionistic fuzzy planar graph and let H be an intuitionistic fuzzy graph. If there exists an isomorphism f:G[arrow right]H , H can be drawn as intuitionistic fuzzy planar graph with same planarity value of G .

Two intuitionistic fuzzy planar graphs with same number of vertices may be isomorphic. But the relations between intuitionistic fuzzy planarity values of two intuitionistic fuzzy planar graphs may have the following relations.

Theorem 31.

Let _G1 and _G2 be two isomorphic intuitionistic fuzzy graphs with intuitionistic fuzzy planarity values _f1 and _f2 , respectively. Then _f1 =_f2 .

Theorem 32.

Let _G1 and _G2 be two weak isomorphic intuitionistic fuzzy graphs with intuitionistic fuzzy planarity values _f1 and _f2 , respectively. _f1 =_f2 if the edge membership and nonmembership values of corresponding intersecting edges are same.

Theorem 33.

Let _G1 and _G2 be two co-weak isomorphic intuitionistic fuzzy graphs with intuitionistic fuzzy planarity values _f1 and _f2 , respectively. _f1 =_f2 if the minimum of membership values and maximum of nonmembership values of the end vertices of corresponding intersecting edges are same.

4. Conclusions

Graph theory has numerous applications to problems in systems analysis, operations research, economics, and transportation. However, in many cases, some aspects of a graph-theoretic problem may be vague or uncertain. It is natural to deal with the vagueness and uncertainty using the methods of fuzzy sets. Since intuitionistic fuzzy set has shown advantages in handling vagueness and uncertainty compared to fuzzy set, we have applied the concept of intuitionistic fuzzy sets to multigraphs and planar graphs in this paper. The natural extension of this research work is application of intuitionistic fuzzy planar graphs in the area of applied soft computing including neural networks, decision making, and geographical information systems. We plan to extend our research of fuzzification to (1) soft fuzzy planar graphs, (2) roughness in planar graphs, (3) vague planar graphs, and (4) bipolar fuzzy planar graphs.

Acknowledgment

This project was funded by the Deanship of Scientific Research (DSR), King Abdulaziz University, Jeddah, under Grant no. (111/363/1434). The authors therefore acknowledge with thanks DSR technical and financial support.

Conflict of Interests

The authors declare that they do not have any conflict of interests regarding the publication of this paper.

References

[1] N. Abdul-Jabbar, J. H. Naoom, E. H. Ouda, "Fuzzy dual graph," Journal of Al-Nahrain University , vol. 12, no. 4, pp. 168-171, 2009.

[2] A. Pal, S. Samanta, M. Pal, "Concept of fuzzy planar graphs," in Proceedings of the Science and Information Conference, pp. 557-563, London, UK, October 2013.

[3] S. Samanta, M. Pal, A. Pal, "New concepts of fuzzy planar graph," International Journal of Advanced Research in Artificial Intelligence , vol. 3, no. 1, pp. 52-59, 2014.

[4] L. A. Zadeh, "Fuzzy sets," Information and Computation , vol. 8, pp. 338-353, 1965.

[5] K. T. Atanassov 1983 (Bulgarian) Intuitionistic Fuzzy Sets , of VII ITKR's Session, Sofia, Central Science and Technical Library, Bulgarian Academy of Sciences 1697/84

[6] A. Kauffman Introduction a la Theorie des Sous-Emsembles Flous , vol. 1, Masson et Cie, 1973.

[7] L. A. Zadeh, "Similarity relations and fuzzy orderings," Information Sciences , vol. 3, no. 2, pp. 177-200, 1971.

[8] A. Rosenfeld, L. A. Zadeh, K. S. Fu, M. Shimura, "Fuzzy graphs," Fuzzy Sets and Their Applications , pp. 77-95, Academic Press, New York, NY, USA, 1975.

[9] P. Bhattacharya, "Some remarks on fuzzy graphs," Pattern Recognition Letters , vol. 6, no. 5, pp. 297-302, 1987.

[10] J. N. Mordeson, P. S. Nair Fuzzy Graphs and Fuzzy Hypergraphs , vol. 46, of Studies in Fuzziness and Soft Computing, Physica, Heidelberg, Germany, 2000.

[11] M. S. Sunitha, A. Vijaya Kumar, "Complement of a fuzzy graph," Indian Journal of Pure and Applied Mathematics , vol. 33, no. 9, pp. 1451-1464, 2002.

[12] A. Shannon, K. T. Atanassov, D. Lakov, "A first step to a theory of the intuitionistic fuzzy graphs," in Proceeding of the FUBEST, pp. 59-61, Sofia, Bulgaria, September 1994.

[13] A. Shannon, K. Atanassov, "Intuitionistic fuzzy graphs from α -, β - and (α ,b)-levels," Notes on Intuitionistic Fuzzy Sets , vol. 1, no. 1, pp. 32-35, 1995.

[14] R. Parvathi, M. G. Karunambigai, K. T. Atanassov, "Operations on intuitionistic fuzzy graphs," in Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE '09), pp. 1396-1401, August 2009.

[15] M. Akram, W. A. Dudek, "Intuitionistic fuzzy hypergraphs with applications," Information Sciences , vol. 218, pp. 182-193, 2013.

[16] M. Akram, B. Davvaz, "Strong intuitionistic fuzzy graphs," Filomat , vol. 26, no. 1, pp. 177-196, 2012.

[17] M. Akram, N. O. Al-Shehri, "Intuitionistic fuzzy cycles and intuitionistic fuzzy trees," The Scientific World Journal , vol. 2014, 2014.

[18] M. Akram, N. O. Alshehri, W. A. Dudek, "Certain types of interval-valued fuzzy graphs," Journal of Applied Mathematics , vol. 2013, 2013.

[19] K. T. Atanassov Intuitionistic Fuzzy Sets: Theory and Applications, Studies in Fuzziness and Soft Computing , Physica, Heidelberg, Germany, 2012.

[20] U. Cerruti, M. M. Gupta, "Graphs and fuzzy graphs," Fuzzy Information and Decision Processes , pp. 123-131, Northholland, 1982.

[21] C. Eslahchi, B. N. Onagh, "Vertex-strength of fuzzy graphs," International Journal of Mathematics and Mathematical Sciences , vol. 2006, 2006.

[22] S. Mathew, M. S. Sunitha, "Types of arcs in a fuzzy graph," Information Sciences , vol. 179, no. 11, pp. 1760-1768, 2009.

[23] J. N. Mordeson, C. Peng, "Operations on fuzzy graphs," Information Sciences , vol. 79, no. 3-4, pp. 159-170, 1994.

[24] R. Parvathi, M. G. Karunambigai, "Intuitionistic fuzzy graphs," Journal of computational Intelligence: Theory and Applications , vol. 38, pp. 139-150, 2006.

[25] G. Pasi, R. Yager, K. Atanassov, "Intuitionistic fuzzy graph interpretations of multi-person multi-criteria decision making: Generalized net approach," in Proceedings of the 2nd International IEEE Conference Intelligent Systems, vol. 2, pp. 434-439, June 2004.

[26] F. Riaz, K. M. Ali, "Applications of graph theory in computer science," in Proceedings of the 3rd International Conference on Computational Intelligence, Communication Systems and Networks (CICSyN '11), pp. 142-145, Bali, Indonesia, July 2011.

[27] S. Samanta, M. Akram, M. Pal, " m -step fuzzy competition graphs," Journal of Applied Mathematics and Computing , 2014.

[28] R. R. Yager, "On the theory of bags," International Journal of General Systems: Methodology, Applications, Education , vol. 13, no. 1, pp. 23-37, 1986.

[29] T. K. Shinoj, S. J. John, "Intuitionistic fuzzy multisets and its application in medical diagnosis," World Academy of Science, Engineering and Technology , vol. 6, no. 1, pp. 1418-1421, 2012.