Abstract
The concept of interval-valued intuitionistic fuzzy set was introduced by Atanassov (See [6]). Interval-valued intuitionistic fuzzy sets provide a more adequate description of uncertainty than the traditional fuzzy sets. It has many applications in fuzzy control and the most computationally intensive part of fuzzy control is defuzzification. In this paper, firstly different kinds of interval valued intuitionistic (S, T)-fuzzy graphs are defined. We introduced several types of arcs in the interval valued intuitionistic (S, T)-fuzzy graphs and studied their properties. These arcs are used to study the structure of complete interval valued intuitionistic (S, T)-fuzzy graphs and constant interval valued intuitionistic (S, T)-fuzzy graphs.
Introduction
Graph theory is becoming increasingly significant as it is applied to other areas of mathematics, science, and technology. In computer science, graphs are used to represent networks of communication, data organization, computational devices, and the flow of computation. After the introduction of fuzzy sets by Zadeh [27], there have been a number of generalization of this fundamental concept. The notion of intuitionistic fuzzy sets introduced by Atanassov [2–5, 8] is one among them. In 1975, Zadeh [28] introduced the notion of interval valued fuzzy sets as an extension of fuzzy sets [27] in which the values of the membership degree are intervals of numbers instead of the numbers. Rosenfeld [21] introduced the notion of fuzzy graphs in 1975 and proposed another definitions including paths, cycles and ect. Akram et al. [1] introduced strong intuitionistic fuzzy graphs. Rashmanlou and Jun investigated complete interval valued fuzzy graphs [15]. Pal and Rashmanlou [11] studied irregular interval valued fuzzy graphs. Also, they defined antipodal interval valued fuzzy graphs [16], balanced interval valued fuzzy graphs [17], some properties of highly irregular interval valued fuzzy graphs [18] and a study on bipolar fuzzy graphs [19, 20]. Sunitha and Vijayakumar [26] investigated complement of a fuzzy graph. In [10], Karunambigai and Parvathi introduced intuitionistic fuzzy graph as a special case of Atanssov’s intuitionistic fuzzy graph. Samanta and Pal definedm-step fuzzy competition graphs [22], fuzzy tolerance graphs [23], fuzzy threshold graphs [24] and fuzzy planar graph [25]. Parvathi et al. [12–14] studied some operations on intuitionistic fuzzy graphs, intuitionistic fuzzy shortest hyperpath in a network and intuitionistic fuzzy linear regression analysis. In graph theory, arc analysis is not very important as all arcs are strong in the sense of [9]. But in interval valued intuitionistic (S, T)-fuzzy graph, it is very important to identify the nature of arcs and no such analysis on arcs is available in the literature. Also, as far as the applications are concerned, the classification of arcs highlights the importance of each arc, which will be improving the efficiency of the system especially in problems involving networks. In this paper, we extended the study of α-strong,β-strong and δ-weak with suitable illustrations. The paper is organized as follows:
Section 2 contain preliminaries and in section 3, we introduce the concept of α-strong, β-strong and δ-weak arcs and emphasis that the connectivity of arcs can not be determined simply by examining the weights of arcs. Also, we examine the relationship between a strong path and a strongest path in an interval valued intuitionistic (S, T)-fuzzy graph and analyse the connectivity of arcs in constant interval valued intuitionistic (S, T)-fuzzy graphs.
Preliminaries
The class of all intuitionistic fuzzy sets over X is denoted by IFS (X).
δ (x, 1) = x (δ (x, 0) = x), δ (x, y) = δ (y, x), δ (δ (x, y) , z) = δ (x, δ (y, z)), δ (x, u) ≤ (x, w), for all x, y, u, w, z ∈ [0, 1], where u ≤ w.
Let G = (V, E) be a graph, where V is the non-empty finite set of vertices of G and E is the set of edges of G. A fuzzy set on V is a mapping σ : V ⟶ [0, 1]. A fuzzy graph G is a pair of functions G = (σ, μ), where σ is a fuzzy subset of a non-empty set V and μ is a symmetric fuzzy relation on σ, i.e. μ (uv) ≤ σ (u) ∧ σ (v), for any u, v ∈ V. The underlying crisp graph of G = (σ, μ) is denoted by G* = (V, E), where E ⊆ V × V. An interval valued intuitionistic (S, T)-fuzzy graph with underlying set V is defined as ordered pair (A, B), where A = (M
A
, N
A
) is an interval valued intuitionistic fuzzy set in V and B = (P
B
, Q
B
) is an interval valued intuitionistic fuzzy set in E such that, for all u, v ∈ V
the M-degree of a vertex v is d
M
(v) = ∑u∈N(v)P
B
(uv) . the N-degree of a vertex v is d
N
(v) = ∑u∈N(v)Q
B
(uv) . the degree of a vertex v is d (v) = [∑u∈N(v)P
B
(uv) , ∑u∈N(v)Q
B
(uv)] . the order of G is defined to be O (G) = (O
M
(G) , O
N
(G) ) where O
M
(G) = ∑v∈VM
A
(v) and O
N
(G) = ∑v∈VN
A
(v) . the size of G is defined to be S (G) = (S
M
(G) , S
N
(G) ) where S
M
(G) = ∑u≠vP
B
(uv) and S
N
(G) = ∑u≠vQ
B
(uv) .
If each vertex of G has the same total degree (r1, r2), then G is said to be an interval valued intuitionistic (S, T)-fuzzy graph of total degree (r1, r2)or a (r1, r2)-totally constant interval valued intuitionistic (S, T)-fuzzy graph.
Types of arcs in interval valuedintuitionistic (S, T)-fuzzy graphsand its properties
In this section, we introduce several types of arcs in interval valued intuitionistic (S-T)-fuzzy graphs and study their properties. These arcs are very important in fuzzy graphs theory and use in study of complete interval valued intuitionistic (S-T)-fuzzy graphs and constant interval valued intuitionistic (S-T)-fuzzy graphs.
A semi P-strong if P
B
(v
i
v
j
) = T (M
A
(v
i
) , M
A
(v
j
) ), for every i and j. A semi Q-strong if Q
B
(v
i
v
j
) = S (N
A
(v
i
) , N
A
(v
j
) ), for every i and j. Strong if it is both semi P-strong and semiQ-strong. Complete P-strong if P
B
(v
i
v
j
) = T (M
A
(v
i
) , M
A
(v
j
) ) and Q
B
(v
i
v
j
) > S (N
A
(v
i
) , N
A
(v
j
) ) , for all v
i
, v
j
∈ V. Complete Q-strong if Q
B
(v
i
v
j
) = S (N
A
(v
i
) , N
A
(v
j
) ) and P
B
(v
i
v
j
) < T
(M
A
(v
i
) , M
A
(v
j
) ) , for all v
i
, v
j
∈ V. Complete if P
B
(v
i
v
j
) = T
(M
A
(v
i
) , M
A
(v
j
) ) and Q
B
(v
i
v
j
) = S
(N
A
(v
i
) , N
A
(v
j
) ), for all v
i
, v
j
∈ V.
P
B
(v
i
v
j
) >0 and Q
B
(v
i
v
j
) =0 for some i and j. P
B
(v
i
v
j
) =0 and Q
B
(v
i
v
j
) >0 for some i and j. P
B
(v
i
v
j
) >0 and Q
B
(v
i
v
j
) >0 for some i and j.
the M-strength of P is defined as min {P
B
(v
i
v
j
)} , for all (i, j = 1, 2, ⋯ , n) and it is denoted by S
M
. the N-strength of P is defined as max {Q
B
(v
i
v
j
)} , for all (i, j = 1, 2, ⋯ , n) and it is denoted by S
N
.
CONNM(G) (v i , v j ) = max {S M } and N-strength of connectedness between two nodes v i and v j is
CONNN(G) (v i , v j ) = min {S N } of all possible path between v i and v j .
In other words, deleting an edge (v i , v j ) reduces the strength of connectedness between some pair of vertices(or) (v i , v j ) is a bridge if there exist vertices v i , v j such that (v i , v j ) is an edge of every strongest path from v i to v j .
Q B (v i v j ) ≤ CONNN(G) (v i , v j ) for every v i , v j ∈ V.
(ii) An arc (v i , v j ) is said to be the weakest arc in G if P B (v i v j ) < CONNM(G) (v i , v j ) and
Q B (v i v j ) > CONNN(G) (v i , v j ) for every v i , v j ∈ V.
(iii) A path P between any two nodes is called the strongest path in G if its strength equals the strength of connectedness CONNM(G) (v i , v j ) and CONNN(G) (v i , v j ) and both the values lie in the same edge.
(iv) A v i - v j path P is called a strong path in G if P contains only strong arcs.
α-strong if P
B
(v
i
v
j
) > CONNM(G)-(v
i
,v
j
) (v
i
, v
j
) and Q
B
(v
i
v
j
) < CONNN(G)-(v
i
,v
j
) (v
i
, v
j
). β-strong if P
B
(v
i
v
j
) = CONNM(G)-(v
i
,v
j
) (v
i
, v
j
) and Q
B
(v
i
v
j
) = CONNN(G)-(v
i
,v
j
) (v
i
, v
j
). δ-weak if P
B
(v
i
v
j
) < CONNM(G)-(v
i
,v
j
) (v
i
, v
j
) and Q
B
(v
i
v
j
) > CONNN(G)-(v
i
,v
j
) (v
i
, v
j
).
Now we discuss the connectivity of arcs of the strongest path in G.
In Fig. 4, the strength of the path uvwzx is ([0.1, 0.2], [0.7, 0.8]), which is the strongest path between the nodes u and x and it contains all types of arcs, namely α-strong, β-strong, and δ-weak.
In Fig. 4, the strong path between the nodes u and x is uwzx. It contains only α-strong and β-strong arcs.
if P contains only α-strong arcs, if P is the unique, strong v
i
v
j
path, if all v
i
v
j
paths in G are of equal strength.
P B (uv) < strength of C′ ≤ CONNM(G)-(v i ,v j ) (v i , v j ) ,
Q B (uv) > strength of C′ ≥ CONNN(G)-(v i ,v j ) (v i , v j ),
which implies that (u, v) is note α-strong, a contradiction. Thus P is the strongest v i v j path.
(ii) Let G = (A, B) be an interval valued intuitionistic (S, T)-fuzzy graph. Let P be the unique strong v i v j path in G. If possible suppose that P is not the strongest v i v j path. Let Q be the strongest v i v j path in G. Then, strength of Q > strength of P for every arc (u, v) in Q, and where is a weakest arc of P.
Then there exists a path from u to v in G whose strength is greater than P B (uv) and less than Q B (uv). Let it be P′. Let w be the last node after u, common to Q and P′ in the uw sub path of P′ and w′ be the first node before v, common to Q and P′ in the w′v sub path of P′. (If P′ and Q are disjoint uv paths then w = u and w′ = v). Then the path P′ consisting of the xw path of Q, ww′ path of P′, and w′v j path of Q is an v i v j path in G such that strength of P′ > strength of Q, contradiction to the assumption that Q is the strongest v i v j path in G. Thus (u, v) can not be a δ-arc, and hence Q is a strong v i v j path in G. Thus we have another strong path from v i to v j , other than P, which is a contradiction to the assumption that P is the unique strong v i v j path in G. Hence P should be the strongest v i v j path in G.
(iii) If every path from v i to v j have the same strength, then each such path is the strongest v i v j path. In particular, a strong v i v j path is the strongest v i v j path. □
In the following theorem, we present a necessary and sufficient condition for interval valued intuitionistic fuzzy bridges.
CONNM(G)-(v i ,v j ) (v i , v j ) ≤ CONNM(G) (v i , v j ), then CONNM(G) (v i , v j ) = P B (v i v j ),
Q B (v i v j ) > CONNM(G)-(v i ,v j ) (v i , v j ) and
CONNN(G)-(v
i
,v
j
) (v
i
, v
j
) > CONNN(G) (v
i
, v
j
), then
Conversely suppose that (v
i
, v
j
) is α-strong. Then by definition, it follows that v
i
v
j
is the unique strongest path from v
i
to v
j
and the removal of (v
i
, v
j
) will reduce the strength of connectedness between v
i
and v
j
. Thus (v
i
, v
j
) is interval valued intuitionistic fuzzy bridge. Note that if an arc (v
i
, v
j
) in G is an interval valued intuitionistic fuzzy bridge, then
That is, there exists a stronger path P other than the arc (v i , v j ) from v i to v j in G.
Let P B (v1v2) = p1, Q B (v1v2) = p2. The strength of the path P be (q1, q2). Then p1 < q1, p2 > q2.
Let v3 be the first node in P after v1. Then P B (v1v3) > p1 and Q B (v1v3) < p2. Similarly, let v4 be the last in P before v2, Then P B (v2v4) > p1 and Q B (v2v4) < p2. Since, P B (v1v2) = p1, Q B (v1v2) = p2, at least one of M A (v1) or M A (v2) and N A (v1) or N A (v2) should be p1 and p2. Now G is a complete interval valued intuitionistic (S, T)-fuzzy graph, it gives the contradiction, which completes the proof. □
Pis a strongv
i
v
j
path Pis the strongestv
i
v
j
path.
Now since G is complete,
From the above
Which implies that P is the strongest path.
(ii) ⇒ (i) Let P be the strongest v i v j path in G. Let the path P contains only β-strong arcs and hence is a strong v i v j path which completes the proof. □
Hence, for an interval valued intuitionistic (S, T)-fuzzy graph G = (A, B), S M = CONNM(G) (v i , v j ) and S N = CONNN(G) (v i , v j ), for all (v i , v j ) ∈ P . □
So, 2S (G) = ∑v∈Ed G (v) = [∑v∈Vk1, ∑v∈Vk2)]= [pk1, pk2]. Hence . □
So, p k + pk′ = 2 [S M (G) + S N (G)] + O M (G) + O N (G). □
Conclusion
Graph theory is an extremely useful tool in solving combinatorial problems in different areas including geometry, algebra, number theory, topology, operations research, biology and social systems. Fuzzy graph theory is finding an increasing number of application in modeling real time systems where the level of information inherent in the system varies with different levels of precision. In this paper, firstly different kinds of interval valued intuitionistic (S, T)-fuzzy graphs are defined. We introduced several types of arcs in interval valued intuitionistic (S, T)-fuzzy graphs and studied their properties. In our future work, we will focus on regularity in interval valued intuitionistic (S, T)-fuzzy intersection graphs and study (2, k)-regular and totally (2, k)-regular interval valued intuitionistic (S, T)-fuzzy graphs.