Vague graphs and strengths

1 Introduction

After introduction of fuzzy sets by Zadeh, fuzzy set theory is included as large research fields. Since then, the theory of fuzzy sets has become a vigorous area of research in different disciplines including medical and life sciences, management sciences, social sciences engineering, statistic, graph theory, artificial intelligence, signal processing, multiagent systems, decision making and automata theory. In a fuzzy set, each element is associated with a membership value selected from the interval [1]. Instead of using particular membership value as in fuzzy sets, interval-based membership can be used to represent the vagueness of a set more perfectly. In 1993, Gau and Buehrer [6] introduced the notion of vague set theory as a generalization of fuzzy set theory. The interval-based membership in vague sets is more expressive in capturing vagueness of data.

A vague set A on a set X is a pair (t _A  ; f _A ) where t _A and f _A are real valued functions defined on X → [0, 1], such that t _A  (x) + f _A  (x) <1 for all x ∈ X. The interval [t _A  (x) , 1 - f _A  (x)] is called the vague value of x in A. However, vague sets are shown to be equivalent to that of intuitionistic fuzzy sets. These sets are algebraically different. They are different in measurement also. But, vague sets allow more graphical representation of vague data, which facilitates significantly better analysis in data relationships, incompleteness, and similarity measures.

Graph theory besides being a well developed branch of Mathematics, it is an important tool for mathematical modeling. Realizing the importance, Rosenfeld [22] introduced the concept of fuzzy graphs. After that, the fuzzy graph theory is increased with a large number of branches. McAllister [12]characterised the fuzzy intersection graphs. In this paper, fuzzy intersection graphs have been defined from the concept of the intersection of fuzzy sets. Bhutani and Rosenfeld [4] introduced the concept of strong edges in fuzzy graphs. After that, Mathew and Sunitha [10] discussed different types of arcs in fuzzy graphs. Further, many works on fuzzy graphs can be found in [3–5, 7–11, 5, 15–17, 19]. Ramakrishna [21] introduced the concept of vague graphs and studied some of their important properties. After that, Talebi et al. [20] illustrated isomorphism on vague graphs. Akram et al. [1 depicted regularity in vague intersection graphs and vague line graphs. Recently, vague graph is one of the interesting research area among researchers].

In this paper, strength of paths in vague graphs is introduced. Different types of strong edges are discussed. Also, vertex connectivity, edge connectivity in vague graphs are discussed. Some important theorems are proved here.

2 Preliminaries

A graph is defined as 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^*.

A fuzzy setA on an universal set X is characterized by a mapping m : X → [0, 1], which is called the membership function. A fuzzy set is denoted by A = (X, m).

A fuzzy graph [22] ξ = (V, σ, μ) is a non-empty set V together with a pair of functions σ : V → [0, 1] and μ : V × V → [0, 1] such that for all x, y ∈ V, μ (x, y) ≤ min {σ (x) , σ (y)}, where σ (x) and μ (x, y) represent the membership values of the vertex x and of the edge (x, y) in ξ respectively. A loop at a vertex x in a fuzzy graph is represented by μ (x, x) ≠0. An edge is non-trivial if μ (x, y) ≠0.

A path [18] book in fuzzy graph is a sequence of distinct nodes x₀, x₁, …, x _n such that μ (x_i-1, x _i ) >0, 1 ≤ i ≤ n. The fuzzy path is said to be fuzzy cycle if x₀ and x _n coincides. Now, strength of a path is the minimum membership value of an edge in the path. The maximum of all strengths of paths between two vertices is the strength of connectivity between the vertices.

The underlying crisp graph [18] book of the fuzzy graph ξ = (V, σ, μ) is denoted as ξ^* = (V, σ^*, μ^*) where σ^* = {u ∈ V|σ (u) >0} and μ^* = {(u, v) ∈ V × V|μ (u, v) >0}. Thus for underlying fuzzy graph, σ^* = V.

A fuzzy graph ξ = (V, σ, μ) is complete [18] book if μ (u, v) = min {σ (u) , σ (v)} for all u, v ∈ V, where (u, v) denotes the edge between the vertices u and v.

A fuzzy graph ξ = (V, σ, μ) is said to be bipartite [18] book if the vertex set V can be partitioned into two nonempty sets V₁ and V₂ such that μ (v₁, v₂) =0 if v₁, v₂ ∈ V₁ or v₁, v₂ ∈ V₂. Further, if μ (v₁, v₂) = min {σ (v₁) , σ (v₂)} for all v₁ ∈ V₁ and v₂ ∈ V₂, then ξ is called a fuzzy complete bipartite graph.

An edge (a, b) is said to be fuzzy bridge [18] book in a fuzzy graph ξ if deletion of the edge (a, b) reduces the strength of connectedness between the vertices a, b.

A vague set [6] A on a set X is a pair (t _A  ; f _A ) where t _A and f _A are real valued functions defined on X → [0, 1], such that t _A  (x) + f _A  (x) <1 for all x ∈ X. The interval [t _A  (x) , 1 - f _A  (x)] is called the vague value of x in A.

A vague set A of X with t _A  = 0 and f _A  = 1 is called zero vague set of X.

A vague set A of X with t _A  = 1 and f _A  = 0 is called unit vague set of X.

A vague set A of X with t _A  = α and f _A  = 1 - α is called α-vague set of X. A vague set A contained in B if t _A  ≤ t _B and f _A  ≥ f _B .

Let A and B be ordinary finite nonempty sets.A vague relation is a vague subset of A × B, that is,an expression R defined by R = {(a, b) , t _R  (a, b) , f _R  (a, b) |a ∈ A, b ∈ B} where t _R  : A × B → [0, 1] and t _R  : A × B → [0, 1] such that 0 ≤ t _R  (a, b)+f _R  (a, b) ≤1 and t _R  (a, b) ≤ t _R  (a) ∧ t _R  (b), f _R  (a, b)≥f _R  (a) ∨ f _R  (b) for all (a, b) ∈ A × B.

Let V be a nonempty set, members of V are called nodes. A vague graph G = (X, Y) with X as the set of nodes is a pair of functions X and Y, where X is a vague set of V and B is a vague relation on V.

The complement of a vague graph [21] G = (X, Y) is a vague graph G ¯ = ( X ¯ , Y ¯ ) where X ¯ = X and the true values and false values of edges are given as t ¯ ( x , y ) = min { t x , t y } - t ( x , y ) and f ¯ ( x , y ) = f ( x , y ) - max { f x , f y } .

The complete vague graph G = (X, Y) is a vague graph such that t_(x,y) = min {t _x , t _y } and 1 - f_(x,y) = max {1 - f _x , 1 - f _y }.

3 Strength of paths

Let P, a path in a vague graph G, contains the sequence of vertices x₀, x₁, …, x _n . Also let the vague values of the edges in the path are given as [t _P  (x₀, x₁) , 1 - f _P  (x₀, x₁)] , [t _P  (x₁, x₂) , 1 - f _P  (x₁, x₂)] , …, [t _P  (x_n-1, x _n ) , 1 - f _P  (x_n-1, x _n )]. The maximum false membership value of an edge in the path corresponds the strength of the path. Let F _p  = max {f _P  (x₀, x₁) , f _P  (x₁, x₂) , …, f _P  (x_n-1, x _n )}. Thus, 1 - F _P  = min {1 - f _P  (x₀, x₁) , 1 - f _P  (x₁, x₂) , …, 1 - f _P  (x_n-1, x _n )}. There may exists more than one edges with right end of vague value as 1 - F _P . Let such edges be (x _{m 1} , x _{m 2} ), (x _{m 3} , x _{m 4} ), …, (x _{m k-1} , x _{m k} ) where m₁, m₂, …, m _k are arbitrary numbers among 1, 2, …, n. Now, let T _P  = max {t _P  (x _{m 1} , x _{m 2} ) , t _P  (x _{m 3} , x _{n 4} ) , …, t _P  (x _{m k-1} , x _{m k} )}. We denote the strength of the path P by [T _P , 1 - F _P ].

Let P₁, P₂, …, P _n be the n paths between the vertices x and y. Let 1 - F G { x , y } = max { 1 - F P 1 , 1 - F P 2 , … , 1 - F P n }. Also let 1 - F G { x , y } be the right end value of the interval which represents the strength of some paths. Let such paths be P _{m 1} , P _{m 2} , …, P _{m k} . Then, we take T G { x , y } = min { T P m 1 , T P m 2 , … , T P m k }. The strength of connectivity between x and y is denoted by C G { x , y } and is defined by C G { x , y } = [ T G { x , y } , 1 - F G { x , y } ].

Example 1. Let P be a path with sequence of vertices x₁, x₂, x₃, x₄ such that the vague values of edges (x₁, x₂) , (x₂, x₃) , (x₃, x₄) of the path be [0.4, 0.7] , [0.5, 0.7] , [0.45, 0.8] respectively. Now the strength of the path is calculated as follows. Here, 1 - F _P  = min {0.7, 0.7, 0.8} = 0.7. But, we see that the edges (x₁, x₂) , (x₂, x₃) have same right end value. This implies T _P  = max {0.4, 0.5} =0.5. So the strength of the path is [0.5, 0.7].

The definition of strong edge is given below.

Definition 1. Let G be a vague graph. An edge (a, b) is said to be strong if 1 - f G ( a , b ) ≥ 1 - F G - ( a , b ) { a , b }. Other edges are said to be weak edges.

Here, we classify two types of strong edges, viz. α-strong and β-strong edges. An edge (a, b) is said to α-strong if 1 - f G ( a , b ) > 1 - F G - ( a , b ) { a , b }. An edge (a, b) is said to be β-strong if 1 - f G ( a , b ) = 1 - F G - ( a , b ) { a , b }.

A path is said to be strong path if it contains at least one α-strong edge or β-strong edge. A path is said to be purely strong path if all edges of the path are either α-strong or β-strong. A path is said to be weak if all edges of the path are weak.

Theorem 1. An edge (a, b) is strong iff f G ( a , b ) = F G { a , b }.

Proof. Let G be a vague graph and (a, b) be a strong edge in G. Then, 1 - f G ( a , b ) ≥ 1 - F G - ( a , b ) { a , b }, i.e. f G ( a , b ) ≤ F G - ( a , b ) { a , b }. Again, F G - ( a , b ) { a , b }≤ F G { a , b }. But, in general f _G  (a, b) ≥ F G { a , b }. Hence, for strong edge f _G  (a, b) = F G { a , b }. Conversely, we take f G ( a , b ) = F G { a , b }. Hence, f _G  (a, b) ≤ F G - ( a , b ) { a , b } i.e. 1 - f _G  (a, b) ≥ 1 - F G - ( a , b ) { a , b }. Thus, (a, b) is strong. □

Theorem 2. Let G be a connected vague graph, then there exists a purely strong path between every pair of vertices.

Proof. Let G be a vague graph. Also, let x, y be any two vertices of G. As G is connected, there exists at least one path between x and y. Suppose the edge (x _k , x _m ) of the path is not strong of any kinds. Then, 1 - f G ( x k , x m ) < 1 - F G - ( x k , x m ) { x k , x m }. Hence, we can find a path between x _k , x _m , whose strength is greater than that of the edge (x _k , x _m ). Similarly, we find an alternate path for every weak edge. If these alternate paths are not purely strong, then we can proceed similarly to find a path of all strong edges. Thus, between any two vertices, there exists a purely strong path. □

Now, we define another kind of strong edge in a vague graph, namely independent strong edge. In earlier definition of strong edge it is seen that, an edge is strong or not, depends on the entire path. We propose a new kind of strong edge by considering only the true and false values of the edge. For this reason, we call it as independently strong edge.

Definition 2. Let G be a vague graph. An edge (a, b) is said to be independently strong if f G ( a , b ) t G ( a , b ) ≤ 0.5. Other edges are said to be independently weak edges.

Example 2. Let us consider a vague graph G shown in Fig. 1. In this graph, t _G  (a, b) =0.25, 1 - f _G  (a, b) =0.9, t _G  (b, c) =0.3, 1 - f _G  (b, c) =0.8, t _G  (a, c) =0.2, 1 - f _G  (a, c) =0.8. Now, we have to check that the edges are strong or not. First, 1 - F G - ( a , b ) { a , b } = 0.8. Here, 1 - f G ( a , b ) > 1 - F G - ( a , b ) { a , b }. Thus, (a, b) is α-strong. Also, f G ( a , b ) t G ( a , b ) = 0.1 0.25 = 0.4 < 0.5. Thus, the edge is also independently strong. Now, 1 - F G - ( b , c ) { b , c } = 0.8. Hence 1 - f G ( b , c ) = 1 - F G - ( b , c ) { b , c } and the edge (b, c) is β-strong. Also, f G ( b , c ) t G ( b , c ) = 0.2 0.3 = 0.67 > 0.5. Thus, the edge is not independently strong. Similarly, we can check that the edge (a, c) is β-strong, but not independently strong.

Theorem 3. If an edge (a, b) is independently strong, f G ( a , b ) ≤ 1 3.

Proof. Let G be a vague graph. If the edge (a, b) is independently strong, f G ( a , b ) t G ( a , b ) ≤ 0.5 i.e. t _G  (a, b) ≥2f _G  (a, b). Again, we know that for an edge t _G  (a, b) + f _G  (a, b) ≤1. Hence, f G ( a , b ) ≤ 1 3. □

But the converse of the theorem is not true. If f G ( a , b ) ≤ 1 3 and f _G  (a, b) + t _G  (a, b) ≤1 do not necessarily imply that f G ( a , b ) t G ( a , b ) ≤ 0.5.

For a complete vague graph, the following theorem holds.

Theorem 4. Let G be a complete vague graph. If t _G  (u) ≥2f _G  (u) ∀ u ∈ V, then all the edges are independently strong edges.

This theorem is obvious as we know that for a complete graph, t_(x,y) = min {t _x , t _y } and 1 - f_(x,y) = max {1 - f _x , 1 - f _y }. Thus f G ( x , y ) t G ( x , y ) ≤ 0.5 as the true membership values of all vertices are twice greater than the false values.

4 Vague bridges

Vague bridge is an important term regarding the connectivity of vertices. The definition is given below.

Definition 3. An edge (a, b) in a vague graph G is said to be vague bridge if its removal reduces the value F G { x , y } for some edge (x, y) in G or G - (a, b) is disconnected vague graph.

Example 3. Consider the vague graph of Fig.2. The removal of the edge (b, c) cause that G - (b, c) is disconnected. Thus the edge (b, c) is a bridge of the graph. Also, the edges (a, b) , (c, d) are bridges.

Theorem 5. Every bridge in a vague graph isα-strong edge.

Proof. Let G be a vague graph and (a, b) be a bridge in G. Now let if possible the edge (a, b) is not α-strong edge. Therefore, 1 - f G ( a , b ) ≤ 1 - F G - ( a , b ) { a , b }. Let P be the strongest path between a, b in G - (a, b). Hence, the strength of the path P is 1 - F G - ( a , b ) { a , b }. As, (a, b) is a bridge 1 - f G ( a , b ) > 1 - F G - ( a , b ) { a , b }. A contradiction. Hence, (a, b) must be an α-strong edge. □

Theorem 6. Every α-strong edge is a bridge, but a β-strong edge need not be a bridge in a vague graph.

Proof. Let (x, y) be an α-strong edge. By definition of α-strong edge, it follows that the removal of this type of edge reduces the strength of the path between x, y. Thus (x, y) is a bridge.

But, if we consider a cycle in vague graph, say G₁ such that all edges are of same false membership value, then all edges are β-strong here. But, if we delete a β-strong edge, say (u, v), then 1 - f G 1 ( u , v ) = 1 - F G 1 - ( u , v ) { u , v }. Hence, the the strong edge does not fulfil the criteria of a bridge in vague graph. □

5 Strong degree of a vertex in vague graph

The degree of a vertex v ∈ V in a vague graph G is d (v) = [∑_v∈Vt _G  (x, v) , ∑_v∈V (1 - t _G  (x, v))]. Let ((x, a₁) , (x, a₂) , …, (x, a _n ) be the strong edges adjacent to x. Now strong degree of a vertex x is d s ( x ) = [ ∑ i = 1 n t G ( x , a i ) , ∑ i = 1 n ( 1 - t G ( x , a i ) ) ].

Now, we define the minimum strong degree in a vague graph. Let 1 - F min = min { ∑ i = 1 n ( 1 - t G ( x , a i ) ) | x ∈ V }. Let this minimum value corresponds to the vertex x _m . Thus, the minimum strong degree of a vague graph is defined as δ s ( v ) = ( ∑ i = 1 n t G ( x m , a i ) , 1 - F min ).

Similarly, we define the maximum strong degree in a vague graph. Let 1 - F max = max { ∑ i = 1 n ( 1 - t G ( x , a i ) ) | x ∈ V }. Let this maximum value corresponds to the vertex x _k . Thus maximum strong degree of vague graph is defined as Δ _s  (v) = ( ∑ i = 1 n t G ( x m , a i ) , 1 - F _max ).

Lemma 1. For any vague graph G, d _s  (v) ≤ d (v) for all vertices in V. [Note that [a, b] ≤ [c, d] if a ≤ c and b ≤ d].

Lemma 2. For any vague graph G, the minimum strong degree δ _s  (v) = min {d _s  (v) |v ∈ V}, δ _s  (v) ≤ d _s  (v) ≤ d (v) for all vertices in V.

This can be illustrated by the following example.

Example 4. Let x be a vertex adjacent to a, b, c, d, e in a vague graph G. Let (x, a) , (x, c) , (x, d)are strong edges and (x, b) , (x, e) are not strongedges. Then strong degree of vertex x is d _s  (x) =[t _G  (x, a) + t _G  (x, c) + t _G  (x, d) , 1 - t _G  (x, a) +1 - t _G  (x, c) +1 - t _G  (x, d)]. But d (x) = [t _G  (x, a)+t _G  (x, b) + t _G  (x, c) + t _G  (x, d) + t _G  (x, e) , 1 - t _G (x, a) +1 - t _G  (x, b) +1 - t _G  (x, c) +1 - t _G  (x, d)+1 - t _G  (x, e)]. Thus d _s  (x) ≤ d (x). Similarly, it can be stated that δ _s  (v) ≤ d _s  (v) ≤ d (v).

Vertex connectivity in vague graph is defined below. Let A be a set of vertices whose removal give the result 1 - F G { x , y } > 1 - F G - A { x , y } where x, y ∉ A. Let ω (G) ⊂ A be a set of vertices having the minimum cardinality such that the stated result holds, i.e. 1 - F G { x , y } > 1 - F G - ω ( G ) { x , y } where x, y ∉ ω (G). Then, ω (G) is said to be cut vertex set in vague graph G.

Edge connectivity in vague graph is defined below. Let B be a set of edges whose removal give the result 1 - F G { x , y } > 1 - F G - B { x , y } for any pair of existing vertices in G - B. Let λ (G) ⊂ B have the minimum cardinality such that 1 - F G { x , y } > 1 - F G - λ ( G ) { x , y } for any pair of existing vertices in G - λ (G). Then λ (G) is said to be cut edge set in vague graph G.

Theorem 7. |ω (G) | ≤ |λ (G) | for any vague graph (|X| denotes the cardinality of the set X).

Proof. Let G be a vague graph. Also let |ω (G) | = m and |λ (G) | = n such that m > n in G. Now removal of one vertex in a connected vague graph, implies that removal of at least one edge connected with it. Thus, removal of m vertices indicates that removal of at least m number of edges. Thus m ≤ n. So the assumption m > n is wrong. Hence, |ω (G) | ≤ |λ (G) |. □

Theorem 8. Any end vertex of any edge of cut edge set, is a member of cut vertex set.

Proof. Let G be a vague graph and let (x, y) ∈ λ (G) such that x, y ∉ ω (G). If x, y ∉ ω (G), λ (G), 1 - F G { x , y }≤ 1 - F G - λ ( G ) { x , y }. Again, (x, y) is a member of λ (G), 1 - F G { x , y }> 1 - F G - λ ( G ) { x , y }. A contradiction arises. Thus, any end vertex of any edge of a cut edge set, is a member of cut vertex set. □

Theorem 9. The members of a cut edge set areα-strong edges.

Proof. Let G be a vague graph and let (x, y) ∈ λ (G). Thus, 1 - F G { x , y }> 1 - F G - λ ( G ) { x , y }. This condition satisfies the condition of α-strong edge. Hence, the member of cut edge set are α-strong edges. This concludes the proof. □

6 Conclusion

This study describes about the strengths of paths in vague graphs. Different types of strong edges are introduced. Independent strong edges are significantly different from other types of strong edges as it does not depend on the strengths of other edges. Some important results regarding the definitions are proved. Strong degree of the vertices are described. Then, the important terms like edge connectivity and vertex connectivity in vague graphs are introduced. Also, the relation between the edge connectivity and α-strong edges are established. Two related terms, viz. cut vertex set and cut edge set are also discussed.

In this study, the priority to the complement of false value, i.e. 1 - f is given. All the strengths are measured by taking the complement of false value. But, all the results can be re-established by taking true value also. But, in our opinion, 1 - f, that is the complement of false statement is more appropriate as it measures the whole range of possible true statement. In future cycles, trees and fundamentals of graph theory will be analyzed with the help of the concept of this paper.