Definition 1. (see [4]). A VS A is a pair (t_A, f_A) on set V where t_A and f_A are used as real valued functions which can be defined on V⟶[0,1], so that t_A(a) + f_A(a) ≤ 1, ∀a ∈ V. The interval [[t_A(a), 1 − f_A(a)] is considered as the vague value of a in A.

Definition 2. (see [29]). A pair ξ = (A, B) is said to be a VG on a crisp graph G^∗, where A = (t_A, f_A) is a VS on V and B = (t_B, f_B) is a VS on E⊆V × V such that t_B(ab) ≤ min(t_A(a), t_A(b)) and f_B(ab) ≥ max(f_A(a), f_A(b)), for each edge ab ∈ E.

Definition 3. (see [35]). A VG ξ is called complete VG if t_B(ab) = min(t_A(a), t_A(b)) and f_B(ab) = max(f_A(a), f_A(b)), ∀a, b ∈ V.

Definition 4. (see [35]). The complement of a VG ξ = (A, B) is a VG $$, where $$ and $$ are defined by the following:

Definition 5. (see [31]). A vague path in a VG ξ = (A, B) is a sequence of distinct nodes b₁, b₂, …, b_n so that either t_B(b_kb_k+1) > 0 or f_B(b_kb_k+1) > 0, ∀ 1 ≤ k ≤ n − 1. It was shown by P_n.

Definition 6. An edge ab of a VG ξ is called an effective edge if t_B(ab) = t_A(a)∧t_A(b) and f_B(ab) = f_A(a)∨f_A(b). Otherwise, it is called a noneffective edge.

Definition 7. (see [31]). An edge ab in a VG ξ is called a strong edge if $$ and $$.

Definition 8. (see [31]). Let ξ = (A, B) be a VG. Let a, b ∈ V, then a dominates b in ξ, if there exists a strong edge between a and b.

Definition 9. (see [32]). The cartesian product of two VGs ξ₁ = (A₁, B₁) and ξ₂ = (A₂, B₂) of the graphs $$ and $$, denoted by ξ₁ × ξ₂ = (A₁ × A₂, B₁ × B₂), is defined as follows:

Definition 10. (see [35]). A node a in a VG ξ is said to be an isolated node if t_B(ab) = 0 and f_B(ab) = 0, for all b ∈ V and a ≠ b. That is, $$.

Definition 11. (see [31]). S⊆V is called a DS in ξ if, ∀ a ∈ V − S, ∃ b ∈ S, so that a dominates b.

Definition 12. (see [31]). Let ξ = (A, B) be a VG. The vertex cardinality of S⊆V is defined as

Notations are shown in Table 1.

Definition 13. Let ξ = (A, B) be a VG and let k ≥ 1 be an integer. A subset S⊆V is called a K-DS of ξ if, for each node a ∈ V − S, there exists an a − b vague path which includes at least k effective edges for b ∈ S. The K-DN of ξ, denoted by γ_k(ξ), is described as the minimum cardinality among all K-DS in ξ.

Definition 14. Let ξ = (A, B) be a VG and let k ≥ 1 be an integer. A subset S⊆V is called a T-KDS of ξ if, for each node a ∈ V, ∃ an a − b vague path that includes at least k effective edges for b ∈ S. The T-KDN of ξ, demonstrated by γ_tk(ξ), is described as the minimum cardinality between all T-KDS in ξ.

Example 1. Consider an example of a T-2DS of VG ξ shown in Figure 1.

It is clear from Figure 1 that S = {a, f} is a minimal T-2DS of VG ξ. The T-2DN of ξ is γ_k(ξ) = 0.8.

Definition 15. Let ξ be a VG. A set S⊆V is called an RDS of ξ if each node in V − S dominates a node in S and also a node in V − S. The RDN of ξ, demonstrated by γ_r(ξ), is described as the minimum cardinality of an RDS in ξ.

Example 2. Consider a VG ξ = (A, B) as shown in Figure 2. It is obvious that S = {c, d} is an RDS of ξ. The RDN of ξ is γ_r(ξ) = 0.75.

Definition 16. Let ξ be a VG. A set S⊆V is called GRDS of ξ if it is an RDS of both ξ and $$. The GRDN of ξ, denoted by γ_gr(ξ), is described as the minimum cardinality of a GRDS in ξ.

Example 3. Consider ξ and $$ as shown in Figures 3 and 4. It is easy to see that S₁ = {a, b} and S₂ = {c, d} are GRDSs of ξ. The GRDN of ξ is γ_gr(ξ) = 0.9.

Theorem 1. Suppose that ξ = (A, B) is a CVG; then γ_r(ξ) = |V|.

Proof. Assume that ξ = (A, B) is a CVG. Then, t_B(ab) = min(t_A(a), t_A(b)) and f_B(ab) = max(f_A(a), f_A(b)). Let S be the MI-RDS of ξ. Then, each node in V − S dominates a node in S and also a node in V − S. Hence, each node dominates all other nodes. So, γ_r(ξ) = |V|.

Definition 17. Let ξ = (A, B) be a VG. A subset S⊆V is called a PDS of ξ if, for each node b ∈ V − S, there exists exactly one node a ∈ S so that a dominates b.

Definition 18. We say that a PDS S is an MI-PDS if, for every a ∈ S, the set S − {a} is not a PDS in ξ. The minimum cardinality among all MI-PDSs is called the PDN of ξ and it was shown by γ_pif(ξ) or simply γ_pif.

Example 4. Consider a VG ξ = (A, B) as shown in Figure 5. It is obvious that S = {a, d} is an MI-PDS. The PDN of ξ is γ_pif = 0.9.

Theorem 2. Every DS in CVG ξ = (A, B) is a PDS.

Proof. Let S be an MI-DS of a VG ξ. Since ξ is complete, each edge in ξ is one effective edge and each node b ∈ V − S is neighbor to exactly one node a ∈ S. Hence, each DS in ξ is a PDS.

Definition 19. The strong product of two VGs ξ₁ = (A₁, B₁) and ξ₂ = (A₂, B₂) of the graphs $$ and $$, where V₁∩V₂ = ∅, denoted by G₁ × G₂ = (A₁ × A₂, B₁ × B₂), is defined as follows:

Theorem 3. Let ξ₁ = (A₁, B₁) and ξ₂ = (A₂, B₂) be two VGs with V₁∩V₂ = ∅. The strong product ξ = ξ₁ × ξ₂ remains connected even after removal of all noneffective edges in it.

Proof. Assume that ξ = ξ₁ × ξ₂ is a strong product of two VGs ξ₁ and ξ₂. Let e = ((a, a₁)(b, b₁)) be a noneffective edge in ξ; that is, t_B((a, a₁)(b, b₁)) < min{t_A(a, a₁), t_A(b, b₁)}, and f_B((a, a₁)(b, b₁)) > max{f_A(a, a₁), f_A(b, b₁)}. Let ξ^′ = ξ − e, and suppose that ξ^′ is disconnected. The edge e disconnects the graph into more than one component. Hence, there is no path among (a, a₁) and (b, b₁) except the edge e = ((a, a₁), (b, b₁)) in ξ^′. This implies that t_B((a, a₁)(b, b₁)) = {t_A(a, a₁), t_A(b, b₁)} and f_B((a, a₁)(b, b₁)) = {f_A(a, a₁), f_A(b, b₁)}, which is a contradiction. So, ξ^′ is connected.

Remark 1. The strong product ξ₁⊠ξ₂ of two connected vague graphs is a connected vague graph.

Theorem 4. If a node a dominates a node b in ξ₁ and a node a₁ dominates a node b₁ in ξ₂, then the node ab does not dominate the node a₁b₁ in ξ₁ × ξ₂.

Proof. Suppose that a dominates b in ξ₁. Then ∃ an effective edge ab in ξ₁, i.e., t_B(ab) = min{t_A(a), t_A(b)} and f_B(ab) = max{f_A(a), f_A(b)}. Similarly, assume that a node a₁ dominates a node b₁ in ξ₂, so that t_B(a₁b₁) = min{t_A(a₁), t_A(b₁)} and f_B(a₁b₁) = max{f_A(a₁), f_A(b₁)}. Now, by definition of Cartesian product, there does not exist any edge among the nodes (a, a₁) and (b, b₁) in ξ₁ × ξ₂; i.e., t_B((a, a₁)(b, b₁)) = 0 and f_B((a, a₁)(b, b₁)) = 0. Therefore, (a, a₁) does not dominate (b, b₁) in ξ₁ × ξ₂.

Definition 20. The direct product of two VGs ξ₁ = (A₁, B₁) and ξ₂ = (A₂, B₂) of the graphs $$ and $$, where V₁∩V₂ = ∅, denoted by ξ₁ ⊗ ξ₂ = (A₁ ⊗ A₂, B₁ ⊗ B₂), is defined as follows:

Note 1. If a node a dominates a node b in ξ₁ and a node a₁ dominates a node b in ξ₂, then the node (a, a₁) dominates the node (b, b₁) in ξ₁ ⊗ ξ₂. It is shown in Figure 6.

Example 5. Consider a VG as in Figure 6. It is obvious that the node a dominates b in ξ₁ and e dominates f in ξ₂. Likewise, the node (a, e) dominates the node (b, f) in ξ₁ × ξ₂.

Definition 21. Let ξ = (A, B) be a VG. A subset S⊆V is called an EDS of ξ if, for each node b ∈ V − S, ∃ a node a ∈ S so that ab ∈ E, |deg^t(a) − deg^t(b)| ≤ 1, t_B(ab) = min{t_A(a), t_A(b)}, |deg^f(a) − deg^f(b)| ≥ 1, and f_B(ab) = max{f_A(a), f_A(b)}. The EDN of ξ, denoted by γ_e(ξ), is defined as the minimum cardinality of an EDS S.

Example 6. Consider a VG ξ = (A, B), as shown in Figure 7.

It is obvious that the MI-EDS of a VG ξ is S = {a}. The EDN is γ_e(ξ) = 0.45. Note that an EDS S is called an MI-EDS of ξ, if, for each node b ∈ S, the set S − {b} is not an EDS.

Theorem 5. Let ξ₁ and ξ₂ be VGs on nonempty sets V₁ and V₂, respectively. Then,

Proof. Assume that S₁ and S₂ are EDSs of minimum cardinality of ξ₁ and ξ₂, respectively. Then, for each node b ∈ V − S₁, ∃ a node a ∈ S₁ so that |deg^t(b) − deg^t(a)| ≤ 1, t_B(ab) = min{t_A(a), t_A(b)}, |deg^f(b) − deg^f(a)| ≥ 1, and f_B(ab) = max{f_A(a), f_A(b)}. Similarly, for each node c ∈ V − S₂, ∃ a node d ∈ S₂ so that |deg^t(d) − deg^t(c)| ≤ 1, t_B(c  d) = min{t_A(c), t_A(d)}, |deg^f(d) − deg^f(c)| ≥ 1, and f_B(c  d) = max{f_A(c), f_A(d)}. That is, a dominates b in ξ₁ and d dominates c in ξ₂. Therefore, by Note 1, the node (a, d) dominates the node (b, c) in ξ₁ ⊗ ξ₂. Thus, |deg^t(a, d) − deg^t(b, c)| ≤ 1, t_B((a, d)(b, c)) = min{t_A(a, d), t_A(b, c)}, |deg^f(a, d) − deg^f(b, c)| ≥ 1, and f_B((a, d)(b, c)) = max{f_A(a, d), f_A(b, c)}. So, γ_e(ξ₁ ⊗ ξ₂) ≤ min(|S₁ × V₁|, |S₂ × V₂|).

Theorem 6. Let S₁ and S₂ be K-DSs of connected VGs ξ₁ = (A₁, B₁) and ξ₂ = (A₂, B₂), respectively; then (1) ξ₁ × ξ₂ is connected. (2) If S₁ is a connected K-DS of ξ₁, then S₁ × V₂ is a connected K-DS of ξ₁ × ξ₂. (3) If S₂ is a connected K-DS of ξ₂, then V₁ × S₂ is a connected K-DS of ξ₁ × ξ₂.

Proof. To prove that ξ₁ × ξ₂ is connected, consider any two arbitrary distinct nodes (a, d) and (b, c) of V₁ × V₂. Then, by definition of Cartesian product, ∃ a path between these two nodes in the following cases:

• (1)

  If a = b, then, since ξ₂ is a connected VG, ∃ a path P : d, d₁, d₂, …, c so that t_B(ef) > 0 and f_B(ef) > 0 for any two nodes e, f of vague path P. Hence, $$ and $$. So, P′:(a, d)(a, d₁), (a, d₂), …\\, (a, c) is the vague path between (a, d), (b, c) in ξ₁ × ξ₂.

• (2)

  If d = c, then, since ξ₁ is a connected VG, ∃ a vague path Q = a, a₁, a₂, …, b so that $$ and $$ for any two nodes e, f of vague path Q. Hence, $$, and t_B((a, d), …, (b, d)) is the vague path between (a, d), (b, c) in ξ₁ × ξ₂.

• (3)

  If a ≠ b and c ≠ d, then, by case 1, ∃ a vague path between the nodes (a, d) and (a, c) in ξ₁ × ξ₂. Likewise, by case 2, ∃ a vague path between the nodes (a, d) and (b, d) in ξ₁ × ξ₂. Hence, the union of these two disjoint vague paths is a vague path between the nodes (a, d) and (b, c) in ξ₁ × ξ₂. Now, if S₁ and S₂ are K-DSs of ξ₁ and ξ₂, respectively, then γ_k(ξ₁ × ξ₂) = min{|V₁ × S₂|, |S₁ × V₂|}. So, V₁ × S₂ and S₁ × V₂ are K-DSs of ξ₁ × ξ₂ and the connectivity can be proved similarly.

Theorem 7. Let ξ₁ and ξ₂ be VGs on nonempty sets V₁ and V₂, respectively. Let S₁ and S₂ be K-DSs of ξ₁ and ξ₂; then S₁ × V₂ is an independent K-DS of ξ₁ × ξ₂ if and only if S₁ is k-independent and $$ and $$, for a, b ∈ S₁ and d ∈ V₂; $$ and $$, for a ∈ S₁ and c, d ∈ V₂; and $$ and $$, for c, d ∈ V₂.

Proof. To prove that each two distinct nodes (a, d), (b, c) in S₁ × V₁ are not neighbor, we consider three conditions. If a = b, then

If c = d, the result is obtained by independence of a, b of S₁.

If a ≠ b and c ≠ d, then, by definition, we have t_B((a, d)(b, c)) = 0 and f_B((a, d)(b, c)) = 0. So, (a, d), (b, c) are not neighbors in G₁ × G₂. Conversely, assume that (iii) is false. That is, ∃ nodes b, c ∈ V₂, so that $$ and $$. Let a ∈ S₁; then

Hence, S₁ × V₂ is not independent. Therefore, condition (iii) is true, i.e., $$ and $$.