Covering and paired domination in intuitionistic fuzzy graphs

1 Introduction

Concept of graph theory have applications in many areas of computer science, including data mining, image segmentation, clustering, image capturing, networking, etc. An intuitionistic fuzzy set is a generalization of the notion of a fuzzy set. Intuitionistic fuzzy models gives more precision, flexibility and compatibility to the system as compared to the fuzzy models.

In 1983, Atanassov [4] introduced the concept of intuitionistic fuzzy set as a generalization of fuzzy sets. Atanassov added a new components which determines the degree of non-membership in the definition of fuzzy set. The fuzzy sets give the degree of membership, while intuitionistic fuzzy sets give both the degree of membership and the degree of non-membership, which are more or less independent from each other, the only requirement is that the sum of these two degrees is not greater than one. Intuitionistic fuzzy sets have been applied in a wide variety of fields including computer science, engineering, mathematics, medicine, chemistry, economics, etc.

2 Preliminaries

A graph is an ordered pair G = (V, E), where V is the set of all vertices of G, which is non empty and E is the set of all edges of G. Two vertices x, y in a graph G are said to be adjacent in G if (x, y) is an edge of G. A simple graph is a graph without loops and multiple edges. A complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on n vertices has n ( n - 1 ) 2 edges.

A node cover in a graph G = (V, E) is the set of nodes such that each edge of the graph is incident to at least one vertex of the set. The minimum number of nodes in a node cover of G is the node covering number α₀ (G) of G. A set of nodes in a graph G is independent if no two nodes in the set are adjacent. The node independent number β₀ (G) of a graph G is the maximum cardinality of an independent set of nodes in G [5].

An arc cover of a graph G without isolated nodes is the set of arcs of G that covers all nodes of G. The arc covering number α₁ (G) of a graph G is the minimum cardinality of an arc cover of G. A set of arcs in a graph G is independent if no two arcs in the set are adjacent. A matching M in a graph means an independent set of arcs in G. If e = (u, v) ∈ M, then we can say that M matches u to v. A matching of maximum cardinality is called a maximum matching. The arc independent number β₁ (G) of G is the cardinality of a maximum matching. A matching M is called a perfect matching if M matches every node of G to some node of G [5].

2.1 Intuitionistic fuzzy graphs

An intuitionistic fuzzy set A on the set X is characterized by a mapping m : X → [0, 1], which is called as a membership function and n : X → [0, 1], which is called as a non-membership function. An intuitionistic fuzzy set is denoted by A = (X, m _A , n _A ). The membership function of the intersection of two intuitionistic fuzzy sets A = (X, m _A , n _A ) and B = (X, m _B , n _B ) is defined as m_A∩B = min {m _A , m _B } and the non-membership function n_A∩B = max {n _A , n _B }. We write A = (X, m _A , n _A ) ⊆ B = (X, m _B , n _B ) (intuitionistic fuzzy subset) if m _A  (x) ≤ m _B  (x) and n _A  (x) ≥ n _B  (x) for all x ∈ X. Now, the intuitionistic fuzzy graph is defined below. Throughout the paper, we denote min {x, y} = x ∧ y and max {x, y} = x ∨ y. Now the intuitionistic fuzzy graph is definedbelow:

Definition 1. [12] An intuitionistic fuzzy graph is of the form G = (V, σ, μ) where σ = (σ₁, σ₂), μ = (μ₁, μ₂) and

V = {v₀, v₁, …, v _n } such that σ₁ : V → [0, 1] and σ₂ : V → [0, 1], denote the degree of membership and non-membership of the vertex v _i  ∈ V respectively and 0 ≤ σ₁ (v _i ) + σ₂ (v _i ) ≤1 for every v _i  ∈ V (i = 1, 2, …, n).

μ₁ : V × V → [0, 1] and μ₂ : V × V → [0, 1], where μ₁ (v _i , v _j ) and μ₂ (v _i , v _j ) denote the the degree of membership and non-membership value of the edge (v _i , v _j ) respectively such that μ 1 ( v i , v j ) ≤ min { σ 1 ( v i ) , σ 1 ( v j ) } and μ 2 ( v i , v j ) ≤ max { σ 2 ( v i ) , σ 2 ( v j ) } , 0 ≤ μ 1 ( v i , v j ) + μ 2 ( v i , v j ) ≤ 1 for every ( v i , v j ) .

Two types of intuitionistic fuzzy graphs are defined in literature. The difference is on the condition on non-membership value of an edge with end vertices. These conditions are μ 2 ( v i , v j ) ≤ max { σ 2 ( v i ) , σ 2 ( v j ) } [ 12 ](1)μ 2 ( v i , v j ) ≥ max { σ 2 ( v i ) , σ 2 ( v j ) } [ 1 ](2)

The condition on membership value remain same. With both these assumptions, lot of theorems are established on intuitionistic fuzzy graphs. But, we notice that there is a difference on complement. The complement of an intuitionistic fuzzy graph G, defined in [1] with condition (2) is structurally similar to the crisp graph, but it does not hold the property G ¯ ¯ = G , G ¯ represents the complement of G. While the complement defined in [12] along with the condition (1) is similar to the complement of fuzzy graph and it satisfies the property G ¯ ¯ = G .

For this reason, we assumed condition (1) in this paper. Let us consider an example of intuitionistic fuzzy graph.

Example 1. Let G = (V, σ, μ) be an intuitionistic fuzzy graph, where σ (v) = (σ₁ (v) , σ₂ (v)), μ (u, v) = (μ₁ (u, v) , μ₂ (u, v)). Let the vertex set be V = {v₁, v₂, v₃, v₄} and σ (v₁) = (0.3, 0.6), σ (v₂) = (0.8, 0.2), σ (v₃) = (0.2, 0.8), σ (v₄) = (0.5, 0.4); μ (v₁, v₂) = (0.25, 0.45), μ (v₂, v₃) = (0.18, 0.75), μ (v₃, v₄) = (0.15, 0.52), μ (v₄, v₁) = (0.3, 0.25), μ (v₁, v₃) = (0.2, 0.8), μ (v₂, v₄) = (0.4, 0.35). The corresponding intuitionistic fuzzy graph is shown in Fig. 1.

OPEN IN VIEWER

Fig. 1

An intuitionistic fuzzy graph.

Definition 2. An intuitionistic fuzzy graph G = (V, σ, μ) is said to be complete if μ₁ (v _i , v _j ) = σ₁ (v _i ) ∧ σ₁ (v _j ) and μ₂ (v _i , v _j ) = σ₂ (v _i ) ∨ σ₂ (v _j ) for all (v _i , v _j ) ∈ E .

An intuitionistic fuzzy graph G = (V, σ, μ) is said to be bipartite if the vertex set V can be partitioned into two non empty sets V₁ and V₂ such that μ₁ (v _i , v _j ) =0 and μ₂ (v _i , v _j ) =0 if v _i , v _j  ∈ V₁ or v _i , v _j  ∈ V₂. Further, if μ₁ (v _i , v _j ) = σ₁ (v _i ) ∧ σ₁ (v _j ) and μ₂ (v _i , v _j ) = σ₂ (v _i ) ∨ σ₂ (v _j ) for all v _i  ∈ V₁ and v _j  ∈ V₂, then G is called a complete bipartite graph and is denoted by K_{σ′,σ^′′}.

Definition 3. An arc (u, v) in an intuitionistic fuzzy graph G = (V, σ, μ) is said to be strong arc if μ₁ (u, v) ≥ CONN_1G (u, v) and μ₂ (u, v) ≤ CONN_2G (u, v) for all (u, v) ∈ E .

In this section, the concept of covering and matching in intuitionistic fuzzy graphs using strong arcs are discussed and established many interesting results. First, we defined strong node cover in intuitionistic fuzzy graphs.

Definition 4. Let G = (V, σ, μ) be an intuitionistic fuzzy graph. A node and an incident strong arc are said to strong cover to each other. A strong node cover in an intuitionistic fuzzy graph G is the set D of nodes that cover all strong arcs of G. The membership value of the strong cover node D is defined as W₁ (D) = ∑_u∈Dμ₁ (u, v) and non-membership value of the strong cover node D is defined as W₂ (D) = ∑_u∈Dμ₂ (u, v), where μ₁ (u, v) is the minimum of the membership values and μ₂ (u, v) is the maximum of the non-membership values of the strong arc incident on u. The strong node covering number of an intuitionistic fuzzy graph G is defined by α _{s 0}  (G) = α _{s 0}  = (α _{s 10} , α _{s 20} ) and defined as α _{s 10} is the minimum membership value of the strong node cover of G and α _{s 20} is the maximum non-membership value of the strong node cover of G. A minimum strong node cover in an intuitionistic fuzzy graph G is a strong node cover of minimum membership value and maximum non-membership value.

Theorem 1. If G = (V, σ, μ) is a complete intuitionistic fuzzy graph, then α _{s 10}  = (n - 1) μ₁ (u, v) and α _{s 20}  = (n - 1) μ₂ (u, v), where n is the number of nodes and μ₁ (u, v) , μ₂ (u, v) are the membership and non-membership value of the weakest arc in G.

Proof. Since G = (V, σ, μ) is a complete intuitionistic fuzzy graph, then all arcs are strong and each node is adjacent to all other nodes. Hence, any set containing (n - 1) nodes forms a strong cover node of G. Let u be a node in G having minimum membership value and maximum non-membership value. Let v₁, v₂, …, v_n-1 be the node adjacent to u. Then the arcs (u, v₁) , (u, v₂) , …, (u, v_n-1) are all weakest arcs of G with membership strength of each arc is equal to μ₁ (u, v) and non-membership strength of each arc equal to μ₂ (u, v), where v ∈ {v₁, v₂, …, v_n-1}. Hence, the set D = {v₁, v₂, …, v_n-1} of n - 1 nodes form a strong node cover of G with W 1 ( D ) = ∑ v i ∈ D μ 1 ( u , v i ) , where μ₁ (u, v _i ), i = 1, 2, …, (n - 1) is the minimum of the membership value of the strong arc incident on v _i . Then α s 10 = μ 1 ( u , v ) + μ 1 ( u , v ) + … + μ 1 ( u , v ) [ ( n - 1 ) times ] where μ₁ (u, v) is the membership value of the weakest arc in G.

Hence, α _{s 10}  = (n - 1) μ₁ (u, v).

Similarly, W 2 ( D ) = ∑ v i ∈ D μ 2 ( u , v i ) , where μ₂ (u, v _i ), i = 1, 2, …, (n - 1) is the maximum of the non-membership value of the strong arc incident on v _i . Then α s 20 = μ 2 ( u , v ) + μ 2 ( u , v ) + … + μ 2 ( u , v ) [ ( n - 1 ) times ] where μ₂ (u, v) is the non-membership value of the weakest arc in G.

Hence, α _{s 20}  = (n - 1) μ₂ (u, v).

Theorem 2. For a complete bipartite intuitionistic fuzzy graph K_{σ′,σ^′′} with partite set V′ and V^′′, then α _{s 10}  (K_{σ′,σ^′′}) = ∧ {W₁ (V′) , W₁ (V^′′)} and α _{s 20}  (K_{σ′,σ^′′}) = ∨ {W₂ (V′) , W₂ (V^′′)}.

Proof. In K_{σ′,σ^′′} all arcs are strong. Also, each node in V′ is adjacent with all nodes in V^′′ and vice-versa. Note that the set of all arcs of K_{σ′,σ^′′} is the set of all arcs incident on each node of V′ or the set of all arcs incident on each node of V^′′. Hence, strong node cover in K_{σ′,σ^′′} are V′, V^′′ and V′ ∪ V^′′. Clearly W₁ (V′ ∪ V^′′) is greater than W₁ (V′) and W₁ (V^′′). Hence, α _{s 10}  (K_{σ′,σ^′′}) = ∧ {W₁ (V′) , W₁ (V^′′)}. Also, W₂ (V′ ∪ V^′′) is less than W₂ (V′) and W₂ (V^′′). Hence, α _{s 20}  (K_{σ′,σ^′′}) = ∨ {W₂ (V′) , W₂ (V^′′)}.

Theorem 3. If G = (V, σ, μ) is an intuitionistic fuzzy cycle such that G^★ is a crisp cycle. Then α s 10 ( G ) = ∧ { W 1 ( D ) : D is a strong node cover in Gwith | D | ≥ ⌈ n 2 ⌉ } and α s 20 ( G ) = ∨ { W 2 ( D ) : D is astrong node cover in G with | D | ≥ ⌈ n 2 ⌉ } .

Proof. In an intuitionistic fuzzy cycle every arc is strong. Also, the number of nodes in the strong node cover of both G and G^★ are same, as each arc in both graphs is strong. Now strong node covering number of G^★ is ⌈ n 2 ⌉ [5]. Hence, the minimum number of nodes in the strong node cover in G is ⌈ n 2 ⌉ . Therefore, α _{s 10}  (G) = ∧ { W 1 ( D ) : D is a strong node coverin G with | D | ≥ ⌈ n 2 ⌉ } and α s 20 ( G ) = ∨ { W 2 ( D ) : Dis a strong node cover in G with | D | ≥ ⌈ n 2 ⌉ } . Hence, the result follows.

Definition 5. Two nodes in an intuitionistic fuzzy graph G = (V, σ, μ) are said to be strongly independent if there is no strong arc between them. A set of nodes in G is strongly independent if any two nodes in the set are strongly independent.

Definition 6. The membership value of a strong independent set D in an intuitionistic fuzzy graph G = (V, σ, μ) is defined as W₁ (D) = ∑_u∈Dμ₁ (u, v), where μ₁ (u, v) is the minimum of the membership values of the strong arcs incident on u and non-membership value of a strong independent set D in an intuitionistic fuzzy graph G = (V, σ, μ) is defined as W₂ (D) = ∑_u∈Dμ₂ (u, v), where μ₂ (u, v) is the maximum of the non-membership values of the strong arcs incident on u.

The strong independent number of an intuitionistic fuzzy graph G is denoted by β _{s 0}  (G) = β _{s 0}  = (β _{s 10} , β _{s 20} ), where β _{s 10} is the maximum membership value of the strong independent set of nodes in G and β _{s 20} is the minimum non-membership value of the strong independent set of nodes in G. A maximum strong independent set in an intuitionistic fuzzy graph G is the strong independent set of maximum membership value and minimum non-membership value.

Now, we determine βs₀ of complete intuitionistic fuzzy graph, complete bipartite intuitionistic fuzzy graph and intuitionistic fuzzy cycle.

Theorem 4. If G = (V, σ, μ) is a complete intuitionistic fuzzy graph, then β _{s 10}  = μ₁ (u, v) and β _{s 20}  = μ₂ (u, v), where μ₁ (u, v) , μ₂ (u, v) are the membership and non-membership values of the weakest arc in G.

Proof. Since G is a complete intuitionistic fuzzy graph, all arcs are strong and each node is adjacent to all other nodes. Hence, D = {u} is the only strong independent set. Hence, the result follows.

Theorem 5. For a complete bipartite intuitionistic fuzzy graph K_{σ′,σ^′′} with partite set V′ and V^′′, then β _{s 10}  (K_{σ′,σ^′′}) = ∨ {W₁ (V′) , W₁ (V^′′)} and β _{s 20}  (K_{σ′,σ^′′}) = ∧ {W₂ (V′) , W₂ (V^′′)}.

Proof. In K_{σ′,σ^′′} all arcs are strong. Also, each node in V₁ is adjacent with all nodes in V₂ and vice-versa. Therefore, the strong independent sets in K_{σ′,σ^′′} are V₁ and V₂. Hence, β _{s 10}  (K_{σ′,σ^′′}) = ∨ {W₁ (V′) , W₁ (V^′′)} and β _{s 20}  (K_{σ′,σ^′′}) = ∧ {W₂ (V′) , W₂ (V^′′)}.

Theorem 6. If G = (V, σ, μ) is an intuitionistic fuzzy cycle such that G^★ is a crisp cycle. Then β s 10 ( G ) = ∨ { W 1 ( D ) : D is a strong node cover in Gwith | D | ≤ ⌊ n 2 ⌋ } and β s 20 ( G ) = ∧ { W 2 ( D ) : D isa strong node cover in G with | D | ≤ ⌊ n 2 ⌋ } .

Proof. In an intuitionistic fuzzy cycle every arc is strong. Also, the number of nodes in the strong independent set of both G and G^★ are same, as each arc in both graphs is strong. Now strong independent number of G^★ is ⌊ n 2 ⌋ [5]. Hence, the maximum number of nodes in a strong independent set in G is ⌊ n 2 ⌋ . Therefore, β s 10 ( G ) = ∨ { W 1 ( D ) : D is a strong node coverin G with | D | ≤ ⌊ n 2 ⌋ } and β s 20 ( G ) = ∧ { W 2 ( D ) : Dis a strong node cover in G with | D | ≤ ⌊ n 2 ⌋ } . Hence, the result follows.

Now, we defined strong cover and strong covering number in intuitionistic fuzzy graphs.

Definition 7. Let G = (V, σ, μ) be an intuitionistic fuzzy graph without isolated nodes. A strong arc cover of G is the set X of strong arcs of G that cover all the nodes of G. The membership value of the strong arc cover X is defined as W₁ (X) = ∑_(u,v)∈Xμ₁ (u, v) and non-membership value of the strong arc cover X is defined as W₂ (X) = ∑_(u,v)∈Xμ₂ (u, v). The strong arc covering number of an intuitionistic fuzzy graph G is defined by α _{s 1}  (G) = α _{s 1}  = (α _{s 11} , α _{s 21} ) and defined as α _{s 11} is the minimum membership value of the strong arc cover of G and α _{s 21} is the maximum non-membership value of the strong arc cover of G. A minimum strong arc cover in an intuitionistic fuzzy graph G is a strong arc cover of minimum membership value and maximum non-membership value.

Theorem 7. If G = (V, σ, μ) is a complete intuitionistic fuzzy graph, then α s 11 ( G ) = ∧ { W 1 ( X ) : X is a strong arc cover in G with | X | ≥ ⌈ n 2 ⌉ } and α s 21 ( G ) = ∨ { W 2 ( X ) : X is a strong arc cover in Gwith | X | ≥ ⌈ n 2 ⌉ } .

Proof. Since G is a complete intuitionistic fuzzy graph, all arcs are strong and each node is adjacent to all others nodes. Also, the number of arcs in strong arc cover of both G and G^★ are same because each arc in both graphs is strong. Now, the strong arc covering number of G^★ is ⌈ n 2 ⌉ [5]. Therefore, the minimum number of arcs in a strong arc cover of G is n 2 . Hence, the result follows.

Theorem 8. For a complete bipartite intuitionistic fuzzy graph K_{σ′,σ^′′} with partite set V′ and V^′′, then α _{s 11}  (K_{σ′,σ^′′}) = ∧ {W₁ (X) : X is a strongarc cover in K_{σ′,σ^′′} with |X| ≥ ∨ {|V₁|, |V₂|}} andα _{s 21}  (K_{σ′,σ^′′}) = ∨ {W₁ (X) : X is a strong arc cover inK_{σ′,σ^′′} with |X| ≥ ∨ {|V₁|, |V₂|}}.

Proof. In K_{σ′,σ^′′} all arcs are strong. Also each node in V′ is adjacent with all nodes in V^′′ and vice-versa. Also, the number of arcs in a strong arc cover of both G and G^★ are same because each arc in both graph is strong. Now, the arc covering number of K σ ′ , σ ′ ′ ★ is {|V₁|, |V₂|} [5]. Therefore, the minimum number of arcs in a strong arc cover of K_{σ′,σ^′′} is {|V₁|, |V₂|}. Hence, α _{s 11}  (K_{σ′,σ^′′}) = ∧ {W₁ (X) : X is astrong arc cover in K_{σ′,σ^′′} with |X| ≥ ∨ {|V₁|, |V₂|}}and α _{s 21}  (K_{σ′,σ^′′}) = ∨ {W₁ (X) : X is a strong arccover in K_{σ′,σ^′′} with |X| ≥ ∨ {|V₁|, |V₂|}}.

Theorem 9. If G = (V, σ, μ) is an intuitionistic fuzzy cycle such that G^★ is a crisp cycle. Then α s 11 ( G ) = ∧ { W 1 ( X ) : X is a strong arc cover in G with | X | ≥ ⌈ n 2 ⌉ } and α s 21 ( G ) = ∨ { W 2 ( X ) : X is a strong arccover in G with | X | ≥ ⌈ n 2 ⌉ } .

Proof. In an intuitionistic fuzzy cycle every arc is strong. Also, the number of arcs in the strong arc cover of both G and G^★ are same, as each arc in both graphs is strong. Now strong arc covering number of G^★ is ⌈ n 2 ⌉ [5]. Hence, the minimum number of arcs in the strong arc cover in G is ⌈ n 2 ⌉ . Therefore, α s 11 ( G ) = ∧ { W 1 ( X ) : X is a strong arc cover in G with | X | ≥ ⌈ n 2 ⌉ } and α s 21 ( G ) = ∨ { W 2 ( X ) : X is astrong arc cover in G with | X | ≥ ⌈ n 2 ⌉ } . Hence, the result follows.

Definition 8. Let G = (V, σ, μ) be an intuitionistic fuzzy graph. A set M of strong arcs in G such that no two arcs in M have a common node is called a strong independent set of arcs or a strong matching in G.

Definition 9. Let M be a strong matching in an intuitionistic fuzzy graph G = (V, σ, μ). If e = (u, v) ∈ M, then M strongly matches u to v. The membership value of strong matching is defined asW₁ (M) = ∑_(u,v)∈Mμ₁ (u, v) and non-membership value of strong matching is defined as W₂ (M) = ∑_(u,v)∈Mμ₂ (u, v).

The strong arc independent number or strong matching number of an intuitionistic fuzzy graph G is denoted by β _{s 1}  (G) = β _{s 1}  = (β _{s 11} , β _{s 21} ), where β _{s 11} is the maximum membership value of the strong matchings of G and β _{s 21} is the minimum non-membership value of the strong matchings of G. A maximum strong matching in an intuitionistic fuzzy graph G is the strong matching of maximum membership value and minimum non-membership value.

Now, we determine βs₁ of complete intuitionistic fuzzy graph, complete bipartite intuitionistic fuzzy graph and intuitionistic fuzzy cycle.

Theorem 10. If G = (V, σ, μ) is a complete intuitionistic fuzzy graph, then β s 11 ( G ) = ∨ { W 1 ( M ) : M is a strong matching with | M | ≤ ⌊ n 2 ⌋ } and β s 21 ( G ) = ∧ { W 2 ( X ) : X is a strong matching with | M | ≤ ⌊ n 2 ⌋ } , where n is the number of nodes in G.

Proof. Since G is a complete intuitionistic fuzzy graph, all arcs are strong and each node is adjacent to all others nodes. Also, the number of arcs in a strong matching of both G and G^★ are same because each arc in both graph is strong. Now, the strong matching number of G^★ is ⌊ n 2 ⌋ [5]. Therefore, the maximum number of arcs in a strong matching of G is n 2 . Hence, the result follows.

Theorem 11. For a complete bipartite intuitionistic fuzzy graph K_{σ′,σ^′′} with partite set V′ and V^′′, then β _{s 11}  (K_{σ′,σ^′′}) = ∨ {W₁ (M) : M is astrong matching in K_{σ′ , σ^′′} with |M|  ≤   ∧ {|V₁|, |V₂|}}   and β _{s 21}  (K_{σ′,σ^′′}) = ∧ {W₁ (M) : M is a strong mat - ching in K_{σ′,σ^′′} with |M| ≤ ∧ {|V₁|, |V₂|}}.

Proof. In K_{σ′,σ^′′} all arcs are strong. Also each node in V′ is adjacent with all nodes in V^′′ and vice-versa. Also, the number of arcs in a strong matching of both K_{σ′,σ^′′} and K σ ′ , σ ′ ′ ★ are same because each arc in both graphs is strong. Now, the strong matching number of K σ ′ , σ ′ ′ ★ is {|V₁|, |V₂|} [5]. Therefore, the maximum number of arcs in a strong matching of K_{σ′,σ^′′} is {|V₁|, |V₂|}. Hence, the resultfollows.

Theorem 12. If G = (V, σ, μ) is an intuitionistic fuzzy cycle such that G^★ is a crisp cycle.Then β s 11 ( G ) = ∨ { W 1 ( M ) : M is a strong matchingwith | M | ≤ ⌊ n 2 ⌋ } and β s 21 ( G ) = ∧ { W 2 ( M ) : M isa strong matching with | M | ≤ ⌊ n 2 ⌋ } .

Proof. In an intuitionistic fuzzy cycle every arc is strong. Also, the number of arcs in a strong matching of both G and G^★ are same, as each arc in both graphs is strong. Now strong matching number of G^★ is ⌊ n 2 ⌋ [5]. Hence, the maximum number of arcs in a strong matching in G is ⌊ n 2 ⌋ . Therefore, β s 11 ( G ) = ∨ { W 1 ( M ) : M is a strong matching with | M | ≤ ⌊ n 2 ⌋ } and β s 21 ( G ) = ∧ { W 2 ( M ) : M is a strongmatching with | M | ≤ ⌊ n 2 ⌋ } . Hence, the result follows.

Example 2. In the intuitionistic fuzzy graph of Fig. 2, strong arc are (u, w) , (w, x) and (x, v). The strong node covers in this intuitionistic fuzzy graph are as follows: D₁ = {w, x}, D₂ = {v, w}, D₃ = {u, x}, D₄ = {u, v, w}, D₅ = {u, v, x}, D₆ = {v, w, x}, D₇ = {u, w, x} and D₈ = {u, v, w, x}.

OPEN IN VIEWER

Fig. 2

Illustration of strong covering in intuitionistic fuzzy graph.

Now, W (D₁) = (0.7 + 0.5, 0.2 + 0.4) = (1.2, 0.6), W (D₂) = (0.5 + 0.7, 0.4 + 0.2) = (1.2, 0.6), W (D₃) = (0.8 + 0.5, 0.2 + 0.4)   =   (1.3, 0.6) , W (D₄)   =   (0.8 + 0.5 + 0.7,  0.2 + 0.4 + 0.2)   = (2.0, 0.8) ,  W (D₅) = (0.8 + 0.5 + 0.5, 0.2 + 0.4 + 0.4)   =   (1.8, 1.0), W (D₆) = (0.5 + 0.7 + 0.5, 0.4 + 0.2 + 0.4) = (1.7, 1.0), W (D₇) = (0.8 + 0.7 + 0.5, 0.2 + 0.2 + 0.4) = (2.0, 0.8) and W (D₈) = (0.8 + 0.5 + 0.7 + 0.5, 0.2 + 0.4 + 0.2 + 0.4) = (2.5, 1.2). Among these the minimum value is (1.2, 0.6). Hence, α _{s 0}  = (1.2, 0.6). Here, u and v are adjacent, so they are not independent, but they are strong independent, since they are not connected with any strong edge.

The strong independent sets are D₁ = {u, v},D₂ = {u, x} and D₃ = {v, w}. Now, W (D₁) = (0.8 + 0.5, 0.2 + 0.4) = (1.3, 0.6), W (D₂) = (0.8 + 0.5, 0.2 + 0.4) = (1.3, 0.6) and W (D₃) = (0.5 + 0.7, 0.4 + 0.2) = (1.2, 0.6). The maximum value among these is (1.3, 0.6) and hence β _{s 0}  = (1.3, 0.6).

The set X = {(u, w) , (v, x)} is the only strong arc cover and strong matching in G and W (X) = (0.8 + 0.5, 0.2 + 0.4) = (1.3, 0.6). Hence α _{s 1}  = β _{s 1}  = (1.3, 0.6).

Theorem 13. For every intuitionistic fuzzy graph G = (V, σ, μ) of order (m, n) containing no isolated vertex,

α _{s 0}  + β _{s 0}  = W (V) ≤ m

Proof. Let α _{s 0}  = W (N _{s 0} ), where N _{s 0} is the minimum strong node cover of G. Then V - N _{s 0} is a strong independent set of nodes. That is nodes in V - N _{s 0} are incident on strong arcs of G. Therefore, β _{s 0}  ≥ W (V - N _{s 0} ) = W (V) - α _{s 0} . i . e α s 0 + β s 0 ≥ W ( V )(3)

Let β _{s 0}  = W (M _{s 0} ), where M _{s 0} is a maximum strong independent set of nodes in G. That is no two nodes in M _{s 0} are adjacent to each other by a strong arc and thus the node in V - M _{s 0} strong cover all the strong arcs of G. Hence, V - M _{s 0} is a strong node cover of G and α _{s 0} is the minimum value of such strong node covers. Hence, α _{s 0}  ≤ W (V - M _{s 0} ) = W (V) - β _{s 0} . i . e α s 0 + β s 0 ≤ W ( V )(4)

From (1) and (2), we have α _{s 0}  + β _{s 0}  = W (V).

Since W (V) ≤ m always by definition of W (V). Hence, α _{s 0}  + β _{s 0}  = W (V) ≤ m.

The second inequality follows directly, since the value of the strong arcs are considered for determining α _{s 1} , β _{s 1} and m is the sum of the node values.

Definition 10. Let G = (V, σ, μ) be an intuitionistic fuzzy graph and M be a strong matching in G. Then M is called perfect strong matching if M strongly matches every node of G to some nodes of G.

Example 3. In the intuitionistic fuzzy graph of Fig. 3, all arcs are strong. The sets M₁ = {(u, w) , (v, x)} and M₂ = {(u, x) , (v, w)} are perfect strong matchings with values W (M₁) = (0.4 + 0.6, 0.6 + 0.4) = (1.0, 1.0) and W (M₂) = (0.4 + 0.5, 0.6 + 0.5) = (0.9, 1.1).

OPEN IN VIEWER

Fig. 3

Perfect strong matching.

In this section, we have introduced paired domination in intuitionistic fuzzy graphs using strong arcs based on perfect strong matching and established some results.

Definition 11. A node v in an intuitionistic fuzzy graph G = (V, σ, μ) is said to be strongly dominate itself and each of its strong neighbours, i.e., v strongly dominates the nodes in N _s  [v]. A set D of nodes of G is a strong dominating set of G if every node of V (G) - D is a strong neighbour of some nodes in D.

Definition 12. The membership value of the strong dominating set D is defined as W₁ (D) = ∑_u∈Dμ₁ (u, v), where μ₁ (u, v) is the minimum of the membership values of the strong arcs incident on u and non-membership value of the strong dominating set D is defined as W₂ (D) = ∑_u∈Dμ₂ (u, v), where μ₂ (u, v) is the maximum of the non-membership values of the strong arcs incident on u.

The strong domination number of an intuitionistic fuzzy graph G is denoted by γ _s  (G) = γ _s  = (γ _{s 1} , γ _{s 2} ), where γ _{s 1} is the minimum membership value of strong dominating sets of G and γ _{s 2} is the maximum non-membership value of strong dominating sets of G.

Definition 13. Let G = (V, σ, μ) be an intuitionistic fuzzy graph. A set D ⊆ V of nodes is said to be a strong paired dominating set if D is a strong dominating set and the induced intuitionistic fuzzy subgraph D has a perfect strong matching. The membership value of the strong paired dominating set D is defined as W₁ (D) = ∑_u∈Dμ₁ (u, v), where μ₁ (u, v) is the minimum of the membership values of the strong arcs incident on u and non-membership value of the strong dominating set D is defined as W₂ (D) = ∑_u∈Dμ₂ (u, v), where μ₂ (u, v) is the maximum of the non-membership values of the strong arcs incident on u

The strong paired domination number of an intuitionistic fuzzy graph G is denoted byγ _spr  (G) = γ _spr  = (γ _{spr 1} , γ _{spr 2} ), where γ _{spr 1} is the minimum membership value of strong paired dominating sets of G and γ _{spr 2} is the maximum non-membership value of strong paired dominating sets of G.

Example 4. In Fig. 4, strong arc are (u, w) , (w, x) and (x, v). In this intuitionistic fuzzy graph, D₁ = {u, v}, D₂ = {w, x} and D₃ = {u, v, w, x} are paired dominating set.

OPEN IN VIEWER

Fig. 4

Illustration of paired domination in intuitionistic fuzzy graph.

Now, value of these sets are: W (D₁) = (0.8 + 0.5, 0.2 + 0.4) = (1.3, 0.6), W (D₂) = (0.7 + 0.5, 0.2 + 0.4) = (1.2, 0.6) and W (D₃) = (0.8 + 0.5 + 0.7 + 0.5, 0.2 + 0.4 + 0.2 + 0.4)   =   (2.5, 1.2). Here,D₂ is a strong paired dominating set with minimum membership value and maximum non-minimum membership value. Hence, strong paired domination number is γ _spr  (G) = (2.5, 1.2).

Theorem 14. If G = (V, σ, μ) is a complete intuitionistic fuzzy graph, then γ _{spr 1}  (G) =2μ₁ (u, v) and γ _{spr 2}  (G) =2μ₂ (u, v), where μ₁ (u, v) is the membership value and μ₂ (u, v) is the non-membership value of any weakest arc in G.

Proof. Since G = (V, σ, μ) is a complete intuitionistic fuzzy graph, all arcs are strong and each node is adjacent to all other nodes. Then any set having two nodes say {u, v} in G forms a strong paired dominating set. Hence, γ _{spr 1}  (G) = μ₁ (u, v) + μ₁ (u, v) =2μ₁ (u, v) and γ _{spr 2}  (G) = μ₂ (u, v) + μ₂ (u, v) =2μ₂ (u, v). Hence, the proof.

Theorem 15. For a complete bipartite intuitionistic fuzzy graph K_{σ′,σ^′′}, γ _{spr 1}  (K_{σ′,σ^′′}) =2μ₁ (u, v) and γ _{spr 2}  (K_{σ′,σ^′′}) =2μ₂ (u, v), where μ₁ (u, v) is the membership value and μ₂ (u, v) is the non-membership value of any weakest arc in K_{σ′,σ^′′}.

Proof. In K_{σ′,σ^′′} all arcs are strong. Also, each node in V₁ is adjacent with all nodes in V₂. Hence, in K_{σ′,σ^′′}, a strong paired dominating set is any set containing two nodes, one in V₁ and other in V₂. Then end nodes say {u, v} of any weakest arc (u, v) in K_{σ′,σ^′′}, u ∈ V₁, v ∈ V₂ form a strong paired dominating set.

Hence, γ _{spr 1}  (K_{σ′,σ^′′}) = μ₁ (u, v) + μ₁ (u, v) =2μ₁ (u, v) and γ _{spr 2}  (K_{σ′,σ^′′}) = μ₂ (u, v) + μ₂ (u, v) =2μ₂ (u, v).

In this paper, covering and matching in intuitionistic fuzzy graphs using strong arcs are defined. The concept of strong cover node, strong independent number, strong arc cover and strong matching in intuitionistic fuzzy graphs using strong arcs are determined and obtained the relations among them. Also, paired domination in intuitionistic fuzzy graphs using strong arcs is introduced. The strong paired domination number γ _spr of complete intuitionistic fuzzy graph and complete bipartite intuitionistic fuzzy graph is determined and investigated many interesting properties on it. We are extending our research work to (1) Chromatic number in intuitionistic fuzzy graphs, and (2) Colouring of intuitionistic fuzzy graphs.