Intuitionistic fuzzy threshold graphs

Abstract

In this study, we provide a generalization of fuzzy threshold graphs, and introduce three notions, which are intuitionistic fuzzy threshold graphs, intuitionistic fuzzy alternating 4-cycle, and threshold dimension of intuitionistic fuzzy graphs. Then we discuss some properties about intuitionistic fuzzy graphs, and obtain two main results. The first one is that under some conditions, an intuitionistic fuzzy graph is equivalent to an intuitionistic fuzzy threshold graph. The second one is that the underlying graph of an intuitionistic fuzzy threshold graph is a split graph, and conversely, a given split graph can be used to construct an intuitionistic fuzzy threshold graph. Finally, we give two applications of intuitionistic fuzzy threshold graphs, which are used to control water resource and power resources, respectively. Through the two applications, we know that intuitionistic fuzzy threshold graphs are more appropriate than fuzzy threshold graphs in controlling water resource and power resource, because intuitionistic fuzzy sets are more suitable and powerful to deal with uncertainty and vagueness compared to fuzzy sets.

Keywords

Intuitionistic fuzzy graphs fuzzy threshold graph intuitionistic fuzzy threshold graphs intuitionistic fuzzy alternating 4-cycle

1. Introduction

Fuzzy graph theory was introduced by Rosenfeld in 1975 [44], ten years after the concept of fuzzy set first proposed [50]. This theory can represent all the systems properly due to the uncertainty or haziness of the parameters of systems. For example, a family group can be represented as a graph, where a vertex represents a family member of the family, and an edge represents the resemblance between two related family members. Obviously, fuzziness should be considered to represent edges because we could not characterize resemblance with classical mathematics theories. Since the reality is full of uncertainty, fuzzy graphs occur in many situations. Now fuzzy graph theories are growing fast from both theories and applications in various fields, and have become a vast branch [4 , 49].

Intuitionistic fuzzy sets (IFSs) proposed by Atanassov [11] is a generalization of fuzzy sets [50 –53], and an IFS is defined by a membership degree, a non-membership degree and a hesitancy degree. So IFSs are more suitable and powerful to handle uncertainty and vagueness compared to fuzzy sets. Further in 1999, Atanassov [10] introduced the concept of intuitionistic fuzzy relations and intuitionistic fuzzy graphs (IFG), where an intuitionistic fuzzy set is used to characterize each vertex or each edge. Afterwards, much more attention have been attracted in this subject [1–3 , 54]. More specifically, in 2006, Karunambigai and Parvathi [36] introduced another type of IFG as a special case of Atanassov’s IFG, and applied these concepts to find a shortest path in networks [22]. Parvathi et al. [37] defined some important operations on IFGs. Karunambigai et al. discussed arcs in IFGs [21], and introduced constant IFG in [23]. Gani et al. [24] defined the concept of degree, order and size of an IFG, and studied point set domination of IFGs [25]. Akram et al. [1–3 , 34] introduced many new concepts including intuitionistic fuzzy hypergraphs, strong IFGs, intuitionistic fuzzy cycles, intuitionistic fuzzy trees, intuitionistic fuzzy planar graph, and double domination on IFGs. Clearly, further research on IFGs is becoming a research pot now.

Threshold graphs as special graphs have beautiful structures and possess many important mathematical properties. This concept was first introduced by Chvatal and Hammer [18] in 1973, and plays an important role in graph theory as well as in many areas, such as computer science, psychology, artificial intelligence and so on. For example, Bipartite threshold graphs were studied in [19]. Andelic and Simic [9] presented properties of threshold graphs. Especially, Samanta and Pal [45] first introduced the fuzzy threshold graph in 2011. Afterwards, Makwana et al. [27] discussed the extraction of illumination invariant features using a fuzzy threshold based approach. Pramanik et al. [41, 42] proposed interval-valued fuzzy threshold graph (IVFTG) and interval-valued fuzzy planar graphs in 2016. However, it should be noted that little work has been done on intuitionistic fuzzy threshold graph, which can be considered as a special IFG. So it is interesting to discuss about intuitionistic fuzzy threshold graphs later to perfect IFG theories.

Based on the above analysis, it is really meaningful for us to study intuitionistic fuzzy threshold graphs(IFTGs) compared to fuzzy threshold graphs, where uncertainty and vagueness will be characterized by intuitionistic fuzzy sets instead of fuzzy sets. Therefore in this paper, we will first give the definition of IFTGs and then introduce other notions, such as intuitionistic fuzzy alternating 4-cycle, threshold dimension of IFGs and so on. Further, we will discuss about properties related to IFTGs, including the relationship between IFTGs and its underlying graphs, the connection between IFGs and IFTGs, and so on. Finally, we will give applications of IFTGs in controlling water resources and power resource, and try to show the importance of researches on IFTGs.

2. Preliminaries

Some definitions necessary are given below.

Let G = (V^*, E^*) be a graph, where V^* and E^* denote the set of vertices and edges of G^*, respectively. ∀x, y ∈ V^*, we say that x and y are adjacent if (x, y) ∈ E^*, i.e., (x, y) is an edge. We call G^* = (V^*, E^*) a simple graph if G^* = (V^*, E^*) does not have loops and multiple edges. Besides, a simple graph is called a complete graph if ∀ x, y ∈ V^*, x and y are adjacent.

Definition 2.1. ([50, 53]) A mapping μ : X → [0, 1] defines a fuzzy subset μ on X. A mapping v : X × X → [0, 1] defines a fuzzy relation on X if v (x, y) ≤ min(μ (x) , μ (y)), ∀x, y ∈ X.

We say a fuzzy relation v symmetric if and only if v (x, y) = v (y, x), ∀x, y ∈ X.

Definition 2.2. ([10]) We define an intuitionistic fuzzy set (IFS) A on X as $\begin{matrix} A = (μ_{A}, v_{A}) : X \to [0, 1] \times [0, 1], \end{matrix}$ where μ_A (x) + v_A (x) ≤1, ∀x, y ∈ X. Note that μ_A (x), v_A (x), and 1 - μ_A (x) - v_A (x) represent the degree of membership, non-membership, and hesitancy of x to A, respectively.

Definition 2.3. ([10]) Let A = (μ_A, v_A) and B = (μ_B, v_B) be two IFS on X. Then (A ∩ B) (x) = (min(μ_A (x) , μ_B (x)) , max(v_A (x) , v_B (x))) , (A ∪ B) (x) = (max(μ_A (x) , μ_B (x)) , min(v_A (x) , v_B (x))) .

Definition 2.4. ([10]) An intuitionistic fuzzy relation (IFR) A on X is characterized by A = (μ_A, v_A): X×X ⟶ [0, 1] × [0, 1], where μ_A (x, y) + v_A (x, y) ≤1, ∀ (x, y) ∈ X × X.

Definition 2.5. ([36, 37]) A pair G = (A, B) is said to be an IFG with its underlying graph G^* = (V^*, E^*) if and only if the following conditions are satisfied:

(μ_A, v_A) is an IFS on V^*.

(μ_B, v_B) is an IFR on V^*(or IFS on E^*),

where

\begin{matrix} μ_{B} (x, y) \leq μ_{A} (x) \land μ_{A} (y) \end{matrix}

and

v_{B} (x, y) \leq v_{A} (x) \lor v_{A} (y), \forall (x, y) \in V^{*} \times V^{*}

(2.1)

Remark 2.1. Note that for Definition 2.5, if v_A (x) =0 for all x ∈V^* and v_B (x, y) =0 for all (x, y) ∈ E^*, we call G = (A, B) a fuzzy graph.

Definition 2.6. ([3]) A pair G = (A, B) is said to be an IFG if and only if the following conditions are satisfied:

(μ_A, v_A) is an IFS on V^*.

(μ_B, v_B) is an IFR on V^*(or IFS on E^*), where

\begin{matrix} μ_{B} (x, y) \leq μ_{A} (x) \land μ_{A} (y) \end{matrix}

and

v_{B} (x, y) \geq v_{A} (x) \lor v_{A} (y), \forall (x, y) \in V^{*} \times V^{*} .

(2.2)

Remark 2.2. Both Definition 2.5 and Definition 2.6 are two types of definition of intuitionistic fuzzy graph. However, Equation (2.1) and Equation (2.2) shows the difference between the two definitions.

Specifically, from Definition 2.5, we know that there is no edge between the vertex x and the vertex y when μ_B (x, y) =0 and v_B (x, y) =0. However from Definition 2.6, we know that there is no edge between the vertex x and the vertex y when μ_B (x, y) =0 and v_B (x, y) =1.

Further, let G₀ = (A, B) be a graph, μ_A (x) =1, v_A (x) =0, ∀x ∈ V. By Definition 2.5, we know G₀ = (A, B) is an intuitionistic fuzzy graph only when v_B (x, y) =0, ∀x, y ∈ V. However, by Definition 2.6, we know G₀ = (A, B) is always an intuitionistic fuzzy graph.

Remark 2.3. (1) In the following sections, we only adopt the intuitionistic fuzzy graph defined in definition 2.5.

(2) Throughout this paper, G^* = (V^*, E^*) denotes the underlying graph of an IFG G = (A, B), where

μ_A (x) ≠0 or v_A (x) ≠1 , ∀ x ∈ V^*

μ_B (x, y) ≠0 or v_B (x, y) ≠1 , ∀ (x, y) ∈ E^*.

Definition 2.7. ([38]) Let G = (A, B) be an IFG. We define the vertex cardinality of V ⊆ V^* as $\begin{matrix} {| V |}_{IF} = \sum_{v_{i} \in V} \frac{1 + μ_{A} (v_{i}) - v_{A} (v_{i})}{2} . \end{matrix}$

3. Intuitionistic fuzzy threshold graphs

Definition 3.1. We call an IFG G = (A, B) an intuitionistic fuzzy threshold graph(IFTG) if there exist t₁ > 0, t₂ > 0, such that $\begin{matrix} \sum_{u \in U} μ_{A} (u) \leq t_{1} and \sum_{u \in U} (1 - v_{A} (u)) \leq t_{2} \end{matrix}$ if and only if U ⊆ V^* is an independent set in G. For simplicity, we denote this type of IFTG as G = (A, B ; t₁, t₂).

Remark 3.1. That U ⊆ V^* is an independent set in G is the same as that U ⊆ V^* is an independent set in G^*. Note that if G = (A, B ; t₁, t₂), and U ⊆ V^* is not an independent set in G^*, we have $\begin{matrix} \sum_{u \in U} μ_{A} (u) > t_{1} or \sum_{u \in U} (1 - v_{A} (u)) > t_{2} . \end{matrix}$

Example 3.1. Consider a graph G^* = (V^*, E^*) with V^* = {a, b, c, d, e} and $E^{*} = {(a, b), (b, e), (e, d), (b, d), (b, c), (c, d)} .$

Let A be an intuitionistic fuzzy subset on V^* and B be an intuitionistic fuzzy subset on E^* (see Table 1). Then based on A and B we can get an IFTG (see Fig. 1) with t₁ = 0.5 and t₂ = 0.6, and here we denote this graph as G = (A, B ; 0.5, 0.6).

Table 1
Membership degrees and non-membership degrees for vertices and edges

Vertices a b c d e

μ _A 0.1 0.5 0.2 0.4 0.2

v _A 0.9 0.4 0.7 0.6 0.8

Edges (a,b) (b,c) (b,d) (b,e) (e,d) (c,d)

μ _B 0.1 0.2 0.4 0.2 0.2 0.2

v _B 0.9 0.7 0.6 0.8 0.7 0.6

Vertices	a	b	c	d	e
μ _A	0.1	0.5	0.2	0.4	0.2
v _A	0.9	0.4	0.7	0.6	0.8
Edges	(a,b)	(b,c)	(b,d)	(b,e)	(e,d)	(c,d)
μ _B	0.1	0.2	0.4	0.2	0.2	0.2
v _B	0.9	0.7	0.6	0.8	0.7	0.6

Fig. 1

An IFTG G = (A, B ; 0.5, 0.6).

Proposition 3.1. Let G = (A, B ; t₁, t₂) and U ⊆ V^* be an independent set in G, then $\begin{matrix} {| U |}_{IF} \leq \frac{1}{2} (t_{1} + t_{2}) . \end{matrix}$

Proof. Since G = (A, B) is an IFTG with two threshold t₁, t₂, then there exist non-negative real numbers t₁, t₂, such that $\begin{matrix} \sum_{u \in U} μ_{A} (u) \leq t_{1} and \sum_{u \in U} (1 - v_{A} (u)) \leq t_{2} . \end{matrix}$

Note that $\begin{matrix} t_{2} \geq \sum_{u \in U} (1 - v_{A} (u)) = m - \sum_{u \in U} v_{A} (u), \end{matrix}$ i.e.,∑_u∈Uv_A (u) ≥ m - t₂, where m is the number of vertices of U. Therefore by Definition 2.7 we obtain that $\begin{matrix} \begin{matrix} {| U |}_{IF} = \sum_{v_{i} \in U} \frac{1 + μ_{A} (v_{i}) - v_{A} (v_{i})}{2} \\ = \sum_{v_{i} \in U} \frac{μ_{A} (v_{i})}{2} + \sum_{v_{i} \in U} \frac{1 - v_{A} (v_{i})}{2} \\ \leq \frac{1}{2} (t_{1} + t_{2}) . □ \end{matrix} \end{matrix}$

Proposition 3.2. A FTG is a special IFTG.

Proof. Let G = (A, B) be an FTG, then by its definition, we get that U ⊆ V is an independent set in G if and only if there exists a threshold t₁ such that $\begin{matrix} \sum_{u \in U} μ_{A} (u) \leq t_{1} . \end{matrix}$

Note that for an IFG, we know v_A (u) =0 for all u ∈ U. Take t₂ = n, then there exist non-negative real numbers t₁, t₂ such that $\begin{matrix} \sum_{u \in U} μ_{A} (u) \leq t_{1} and \sum_{u \in U} (1 - v_{A} (u)) \leq t_{2}, \end{matrix}$ where n is the number of vertices of V. So a FTG is an IFTG.

Definition 3.2. Suppose G = (A, B) is an IFG with V^* = {a, b, c, d}. If the following four conditions hold:

μ_B (a, b) ≠0 and v_B (a, b) ≠0 ((μ_B (a, b) , v_B (a, b)) ≠ (0, 0));

μ_B (c, d) ≠0 and v_B (c, d) ≠0 ((μ_B (c, d) , v_B (c, d)) ≠ (0, 0));

μ_B (a, c) =0 and v_B (a, c) =0 ((μ_B (a, c) , v_B (a, c)) = (0, 0));

μ_B (b, d) =0 and v_B (b, d) =0 ((μ_B (b, d) , v_B (b, d)) = (0, 0)),

we say that the four vertices constitute an intuitionistic fuzzy alternating 4-cycle.

Remark 3.2. The intuitioistic fuzzy alternating 4-cycle can induce three types of intuitionistic fuzzy subgraph:

an intuitionistic fuzzy path P₄: (μ_B (a, d) , v_B (a, d)) = (0, 0) (μ_B (b, c) , v_B (b, c)) ≠ (0, 0);

(μ_B (b, c) , v_B (b, c)) = (0, 0) (μ_B (a, d) , v_B (a, d)) ≠ (0, 0).

an intuitionistic fuzzy square C₄: (μ_B (a, d) , v_B (a, d)) ≠ (0, 0) (μ_B (b, c) , v_B (b, c)) ≠ (0, 0).

an intuitionistic fuzzy matching 2K₂: (μ_B (a, d) , v_B (a, d)) = (0, 0) (μ_B (b, c) , v_B (b, c)) = (0, 0).

Proposition 3.3. An IFTG does not have an intuitionistic fuzzy alternating 4-cycle.

Proof. Let G = (A, B ; t₁, t₂). Assume the IFTG has an intuitionistic fuzzy alternating 4-cycle, then there exist four vertices a, b, c, d satisfying $\begin{matrix} (μ_{B} (a, b), v_{B} (a, b)) \neq (0, 0), \end{matrix}$ $\begin{matrix} (μ_{B} (c, d), v_{B} (c, d)) \neq (0, 0), \end{matrix}$ $\begin{matrix} (μ_{B} (a, c), v_{B} (a, c)) = (0, 0) \end{matrix}$ and $\begin{matrix} (μ_{B} (b, d), v_{B} (b, d)) = (0, 0) . \end{matrix}$

By the definition of IFG, we know that $\begin{matrix} (μ_{A} (a), v_{A} (a)) \neq (0, 1), (μ_{A} (b), v_{A} (b)) \neq (0, 1), \end{matrix}$ $\begin{matrix} (μ_{A} (c), v_{A} (c)) \neq (0, 1) (μ_{A} (d), v_{A} (d)) \neq (0, 1) . \end{matrix}$

Since G = (A, B ; t₁, t₂), then $μ_{A} (a) + μ_{A} (b) > t_{1}, v_{A} (a) + v_{A} (b) < 2 - t_{2},$ (3.1) $\begin{matrix} μ_{A} (a) & + μ_{A} (c) \leq t_{1}, (1 - v_{A} (a)) \\ + (1 - v_{A} (c)) \leq t_{2}, \end{matrix}$ (3.2) $μ_{A} (c) + μ_{A} (d) > t_{1}, v_{A} (c) + v_{A} (d) < 2 - t_{2},$ (3.3) $\begin{matrix} μ_{A} (b) & + μ_{A} (d) \leq t_{1}, (1 - v_{A} (b)) \\ + (1 - v_{A} (d)) \leq t_{2} . \end{matrix}$ (3.4)

From Equation (3.1), (3.2),(3.3) and (3.4), we obtain $μ_{A} (b) - μ_{A} (c) > 0, v_{A} (b) - v_{A} (c) < 0;$ (3.5) $μ_{A} (c) - μ_{A} (b) > 0, v_{A} (c) - v_{A} (b) < 0 .$ (3.6)

Obviously, Equation (3.5) contradicts with Equation (3.6). Therefore we get the conclusion.□

Theorem 3.1. Let G = (A, B) be an IFG, G^* = (V^*, E^*) be a split graph, K be the largest clique and V^* - K be the independent set in G^*. If there exist three non-negative real number s₁, t₁, and t₂ satisfying the following conditions:

s₁ < min {μ_A (u) |u ∈ K} and $min {ν_{A} (u) | u \in K} > 1 - \frac{t_{2}}{n}$ ,

where n = |V^*|_IF;

∑_u∈V^*-Kμ_A (u) ≤ s₁ and $min {v_{A} (u) | u \in V^{*} - K} \geq 1 - \frac{t_{2}}{n}$ ,

where n = |V^*|_IF;

s₁ ≤ max {μ_A (u^*) + s₁|u^* ∈ K} ≤ t₁ < min

{μ_{A} (u) + μ_{A} (v) | \begin{matrix} u \in K, v \in V^{*}, \\ u and v is adjacent \end{matrix}}

where {u^*} ∪ (V^* - K) is an independent set in G^*. then we have

\sum_{u \in U} μ_{A} (u) \leq t_{1} and \sum_{u \in U} (1 - v_{A} (u)) \leq t_{2}

(3.7)

if and only if U ⊆ V^* is an independent set in G. This means that an IFG satisfying conditions (I),(II) and (III) is an IFTG, i.e., G = (A, B ; t₁, t₂).

Proof. Sufficiency: Let U ⊆ V^* be an independent set in G^*, then we know that $\begin{matrix} U \subseteq V^{*} - K or U \cap K \neq \emptyset . \end{matrix}$

(1) If U ⊆ V^* - K, from the condition (I), (II) and (III), we get that $\begin{matrix} \sum_{u \in U} μ_{A} (u) \leq \sum_{u \in V^{*} - K} μ_{A} (u) \leq s_{1} \leq t_{1}, \end{matrix}$ and $\begin{matrix} \begin{matrix} \sum_{u \in U} (1 - v_{A} (u)) \leq \sum_{u \in U} \\ (1 - min {v_{A} (u) | u \in V^{*} - K}) \\ \leq n - n (1 - \frac{t_{2}}{n}) \leq t_{2} . \end{matrix} \end{matrix}$

(2) If U∩ K ≠ ∅, and K is the largest clique, then we know that there exists one and only one vertex u^* such that U ∩ K = {u^*}. From the condition (I), (II) and (III), we get that $\begin{matrix} \begin{matrix} \sum_{u \in U} μ_{A} (u) \leq \sum_{u \in V^{*} - K} μ_{A} (u) + \sum_{u \in U \cap K} μ_{A} (u) \\ = \sum_{u \in V^{*} - K} μ_{A} (u) + μ_{A} (u^{*}) \\ \leq s_{1} + μ_{A} (u^{*}) \\ < max {s_{1} + μ_{A} (u^{*}) | u^{*} \in K} \\ \leq t_{1} \end{matrix} \end{matrix}$ and $\begin{matrix} \begin{matrix} \sum_{u \in U} (1 - v_{A} (u)) \leq \sum_{u \in V^{*} - K} \\ (1 - v_{A} (u)) + (1 - v_{A} (u_{1})) \\ \leq \frac{(n - 1)}{n} t_{2} + \frac{t_{2}}{n} = t_{2} . \end{matrix} \end{matrix}$

Necessity: Suppose U ⊆ V^* is not an independent set in G^*, then we know that U ⊆ K or $\begin{matrix} U \cap (V^{*} - K) \neq \emptyset . \end{matrix}$

(1) If U ⊆ K, then there exist at least two vertices in U, such as u₁ and v₁, such that the two vertices are adjacent. Since the two vertices both belong to K, then from the condition (III), we have $\begin{matrix} \sum_{u \in K} μ_{A} (u) > μ_{A} (u_{1}) + μ_{A} (v_{1}) > t_{1} . \end{matrix}$

This contradicts with Equation (3.7).

(2) If U∩ (V^* - K) ≠ ∅, then there exist at least two vertices in U, such as u₁ and v₁, such that the two vertices are adjacent. It should be noted that one of the two vertices belong to K, then from the condition (III), we have $\begin{matrix} \sum_{u \in K} μ_{A} (u) > μ_{A} (u_{1}) + μ_{A} (v_{1}) > t_{1} . \end{matrix}$

This contradicts with Equation (3.7).

Therefore we know that if $\begin{matrix} \sum_{u \in U} μ_{A} (u) \leq t_{1} and \sum_{u \in U} (1 - v_{A} (u)) \leq t_{2}, \end{matrix}$ then U ⊆ V^* is an independent set in G.□

Theorem 3.2. Let G = (A, B ; t₁, t₂) be an IFTG, then its underlying graph G^* = (V^*, E) is a split graph; Conversely, if G^* = (V^*, E) is a split graph, then it can be converted to an IFTG after some modifications to the membership degree and non-membership degree of vertices of V^*.

Proof. Let G = (A, B ; t₁, t₂) be an IFTG. Take K as the largest clique in G^*, then the rest is just to prove V^* - K is an independent set.

Assume V^* - K is not an independent set, then there exists an edge (a, b) in V^* - K such that $\begin{matrix} (μ_{B} (a, b), v_{B} (a, b)) \neq (0, 0) . \end{matrix}$

Since K is the largest clique, then there exist distinct vertices c, d in K such that $\begin{matrix} (μ_{B} (a, c), v_{B} (a, c)) = (0, 0) \end{matrix}$ and $\begin{matrix} (μ_{B} (b, d), v_{B} (b, d)) = (0, 0) . \end{matrix}$

Thus the four vertices a, b, c, d constitute an intuitionistic fuzzy alternating 4-cycle, and by Proposition 3.3 we get the contradiction. Therefore V^* - K is an independent set, and G^* is a split graph.

Conversely, if Since G^* = (V^*, E) is a split graph, we can get the largest clique K and the independent set V^* - K in G^*. Then, we modify the membership degree and non-membership degree for each vertex and each arc in G^* over and over, until we get an IFG, which satisfies the conditions (I), (II) and (III) in Theorem 3.1. That is, we obtain an IFTG finally.□

Theorem 3.3. An IFTG can be constructed from a single vertex graph by repeatedly adding an isolated vertex or an dominating vertex to its underlying graph.

Proof. In fact, a threshold graph can be constructed from a single vertex graph by repeatedly adding an isolated vertex or an dominating vertex. Now we take this threshold graph as an underlying graph G^* = (V^*, E). Then we can get an IFG (i.e., G = (A, B ; t₁, t₂)) by modifying its membership degree and non-degree of vertices and edges. It should be noted that G^* = (V^*, E) is required to be the underlying graph of the IFG during the process of modification.□

Definition 3.3. The threshold dimension t (G) of IFG G = (A, B) is the minimum number k of intuitionistic fuzzy threshold subgraphs, such as G₁, G₂, ⋯ , G_k, which cover the edge set of G. That is, G₁ ∪ G₂ ∪ ⋯ ∪ G_k = G.

Definition 3.4. The intuitionistic fuzzy threshold partition number tp (G) of IFG G = (A, B) is the minimum number k of intuitionistic fuzzy threshold subgraphs, such as G₁, G₂, ⋯ , G_k, which cover the edge set of G, and do not contain common arcs.

Remark 3.3. Clearly, t (G) ≤ tp (G) ≤ |E (G) |, where |E (G) | denotes the number of edges of G.

Example 3.2. Let G = (A, B) be an IFG (see Fig. 2), and the graph has vertices with membership degrees and non-membership degrees, i.e., $\begin{matrix} a (0.2, 0.8), b (0.5, 0.4), c (0.3, 0.6), d (0.3, 0.7), \end{matrix}$ $\begin{matrix} e (0.4, 0.5), a^{'} (0.2, 0.8), b^{'} (0.5, 0.4), c^{'} (0.3, 0.6) . \end{matrix}$

Fig. 2

An IFG with t (G) =2, and tp (G) =3.

By Definition 3.3 and Definition 3.4, we can get $\begin{matrix} t (G) = 2, and tp (G) = 3 . \end{matrix}$

Obviously, t (G) ≤ tp (G) ≤ |E (G) |.

Theorem 3.4. Let G = (A, B) be an IFG, then t (G) ≤ n - α (G), where α (G) is the number of the maximum independent set of G^*, and n is the number of vertices of G^*

Theorem 3.5. If G = (A, B) is a triangle free IFG, then t (G)=tp (G) = n - α (G), where α (G) is the number of vertices of the maximum independent set of G^*, and n is the number of vertices of G^*.

Remark 3.4. The proof Theorem 3.4 and Theorem 3.5 is similar to Theorem 4 and Theorem 5 in [45], so we omit them here.

4. Applications of intuitionistic fuzzy threshold graphs in resource controlling

In reality, it is easy to find IFTGs can help solve resources allocation problems in intuitionistic fuzzy surroundings. Especially, IFTGs are helpful to control the flow of information. In the following, we mainly discuss about two applications of IFTGs in resource controlling.

In order to apply IFTGs in resource controlling, it is necessary to get a partition of IFGs. That is, we need to search intuitionistic fuzzy threshold subgraphs, G₁, G₂, ⋯ , G_k, which cover the edge set of G, and tp (G) = k.

Generally, it is difficulty to find intuitionistic fuzzy threshold subgraphs from IFGs. However, from Theorem 3.5, we know that t (G) = tp (G) = n - α (G) when G = (A, B) is an triangle free IFG, where α (G) is the number of vertices of the maximum independent set of G^*, and n is the number of vertices of G^*.

Below we give an algorithm for searching intuitionistic fuzzy threshold subgraphs from an triangle free IFG.

Algorithm 1. An algorithm for searching intuitionistic fuzzy threshold subgraphs
Input: An triangle free IFG G = (A, B), and its underlying graph G^* = (V^, E^).
Output: Intuitionistic fuzzy threshold subgraphs G₁, G₂, ⋯ , G_s, where s = tp (G) = n - α (G), α (G) is the number of vertices of the maximum independent set of G^, and n is the number of vertices of G^.
Step 1 Initialize V₁ = V^*, W =∅, G′ = G, V′ =∅, i = 1, j = 1;
Step 2 Take any vertex v_i ∈ V_i, and find a maximal IFTG G_j including v_i from G′;
Step 3 Compute W = W ∪ {v₁}, $G^{'} = G - ⋃_{k = 1}^{j} E (G k)$ , and search all isolated vertices V′ from G′;//E (G_k) denotes a set of edges of G_k;
Step 4 i = i + 1, V_i = V^* - V′;
Step 5 If E (G′) =∅, and i = s, then go to Step 6;
Else if E (G′)≠ ∅, then j = j + 1, and goto Step 2;
Else if E (G′) =∅, and i ≠ s, then i = 1, V_i = V^* - W and go to Step 2,
End if;
Step 6 Output G₁, G₂, ⋯ , G_s.

4.1. An application of intuitionistic fuzzy threshold graph in water resource controlling

It is well known that urban water supplies have a great effect on people’s life. People can not live without water. It is really crucial for reservoirs to provide enough water for cities.

Assume there are six cities, i.e., a, b, c, d, e, f, and two reservoirs, i.e., x, y. The amount of water provided by the two reservoirs varies every day. It is worth noting that there exists an important problem about water leakage in underground pipelines, and this directly causes water waste of each city. Obviously, in order to control water resource of each city, we need to know the amount of actual water consumption, estimated water leakage and unforeseen water consumption. Besides, the two reservoirs need to supply the required amount of water to guarantee the basic water consumption for six cities, while the two reservoirs also has the minimum amount of water storage, which is used for keeping the normal water level of the reservoir.

In order to control water resource, we need to find the minimum amount of replenishment water, which should be retained for cities. Thus at any time, the two reservoirs can supply enough water to guarantee the basic city water consumption. For simplicity, we need to convert the original data into equivalent real numbers between 0 and 1 in advance. Here the water network system can be modeled as an IFG (see Fig. 3), i.e., G = (A, B), where six cities and two reservoirs can be represented as vertices. That is, the IFG has eight vertices, i.e., a, b, c, d, e, f, x, y, and each of them has membership degree and non-membership degree. Now we choose the city “a”, and the reservoir “x” as representatives, and give the meaning of μ_A (a), v_A (a), μ_A (x), v_A (x), μ_B (a, x) and v_B (a, x). More details are shown below:

Fig. 3

An intuitionistic fuzzy graph related to water resource.

μ_A (a) denotes the amount of actual water consumption of the city “a”; v_A (a) denotes the amount of water leakage of the city “a”; 1 - μ_A (a) - v_A (a) (i.e., the hesitancy degree of a to A) denotes the amount of unforeseen water consumption of the city “a”.

μ_A (x) denotes the amount of water supply of the reservoir “x”; v_A (x) denotes the minimal amount of water storage of the reservoir “x”; 1 - μ_A (x) - v_A (x) (i.e., the hesitancy degree of x to A) denotes the amount of unforeseen water consumption of the reservoir “x”.

μ_B (a, x) denotes the non-droughty degree between the city “a” and the reservoir “x”, and v_B (a, x) denotes the droughty degree between the city “a” and the reservoir “x”, where (a, x) is an edge of the IFG.

Since the amount of water consumption of each city is dominated by reservoirs, therefore by Algorithm 1, we know that the threshold dimension is easily to be determined by the number of reservoirs. Let us see the IFG shown in Fig. 3, where the threshold dimension is 2, and the intuitionistic fuzzy threshold partition number is also 2. That is, we can induce two intuitionistic fuzzy threshold subgraphs (see Fig. 4) from this IFG.

Fig. 4

Two intuitionistic fuzzy threshold subgraphs related to water resource.

It should be noted that the threshold t₁ means the limit amount of water replenishment, and m - t₂ means the limit amount of water leakage and unforeseen water consumption, where m is the number of elements of maximum independent set of the underlying graph of IFTG. For example, we can obtain that t₁ = 0 .94 and t₂ = 3.96 from the first IFTG of Fig. 4, and t₁ = 0 .9 and t₂ = 4 . 954 from the second IFTG of Fig. 4. Note that {a, b, c, d} is the maximum independent set of the underlying graph of the first IFTG, and $\begin{matrix} μ_{A} (a) + μ_{A} (b) + μ_{A} (c) + μ_{A} (d) = 0.8 . \end{matrix}$

Therefore we know that the reservoir “x” can provide 0.94 amount of water replenishment for the four cities, which need at least 0.8 amount of water for actual water consumption, and 0.04 (0 . 04 = 4 -3 . 96) amount of water for water leakage and unforeseen water consumption. Simultaneously for the second IFTG, the maximum independent set is {b, c, d, e, f}, and $\begin{matrix} μ_{A} (b) + μ_{A} (c) + μ_{A} (d) + μ_{A} (e) + μ_{A} (f) = 0.85 . \end{matrix}$

Therefore we know that the reservoir “y” can provide 0.9 amount of water replenishment for the five cities, which need at least 0.85 amount of water for actual water consumption, and about 0.046 (0 . 046 = 5 -4 . 954) amount of water for water leakage and unforeseen water consumption.

From the above analysis, we know that it is really important to apply IFTG in controlling water resources. Moreover, through this application, we know that IFTGs are more appropriate than fuzzy threshold graphs in controlling water resource.

4.2. An application of intuitionistic fuzzy threshold graph in power resource controlling

Nowdays, people’s life is closely related to electricity. It is really important for power stations to supply enough electricity for running cities.

Assume there are five cities, i.e., a, b, c, d, e, and two power stations, i.e., x, y. The amount of electricity provided by the two stations varies from day to day. What we can not ignore is the loss of power when electricity is transmitted from power stations to cities. Obviously, in order to control power resource, on the one hand, we need to know the amount of actual electricity consumption, estimated power loss and unforeseen electricity consumption of each city. On the other hand, we need to know the required amount of electricity supplied by the two power stations for running five cities. Besides, we also need to know the minimum amount of electricity storage for maintaining power stations.

What we’re focusing on is to find the minimum amount of replenishment electricity, which should guarantee the basic electricity consumption of each city. For simplicity, we need to convert the original data into equivalent real numbers between 0 and 1 in advance. Here the grid system can be modeled as an IFG (see Fig. 5), i.e., G = (A, B), where five cities and two power stations can be represented as vertices. That is, the IFG has eight vertices, i.e., $\begin{matrix} a, b, c, d, e, x, y, \end{matrix}$ and each of them has membership degree and non-membership degree. Now we choose the city “a”, and the reservoir “x” as representatives, and give the meaning of μ_A (a), v_A (a), μ_A (x), v_A (x), μ_B (a, x), v_B (a, x), μ_B (x, y) and v_B (x, y). More details are shown below:

μ_A (a) denotes the amount of actual electricity consumption of the city “a”;v_A (a) denotes the amount of the power loss of the city “a”; 1 - μ_A (a) - v_A (a) (i.e., the hesitancy degree of a to A) denotes the amount of unforeseen electricity consumption of the city “a”.

μ_A (x) denotes the amount of electricity supply of the power station “x”;v_A (x) denotes the minimal amount of electricity storage of the power station “x”; 1 - μ_A (x) - v_A (x) (i.e., the hesitancy degree of x to A) denotes the amount of unforeseen electricity consumption of the power station “x”.

μ_B (a, x) denotes the degree of no loss of power grid from the power station “x” to the city “a”, and v_B (a, x) denotes the degree of power grid loss from the power station “x” to the city “a”, where (a, x) is an edge of the IFG.

μ_B (x, y) denotes the transfer of electricity from the power station “x” to the power station “y”, and v_B (x, y) denotes the power grid loss between the two power stations,

Since the amount of electricity consumption of each city is dominated by power stations, therefore by Algorithm 1, we know that the threshold dimension is easily to be determined by the number of power stations. Let us see the IFG shown in Fig. 5, where the threshold dimension is 2, and the intuitionistic fuzzy threshold partition number is also 2. That is, we can induce two intuitionistic fuzzy threshold subgraphs (see Fig. 6) from this IFG.

Fig. 5

An intuitionistic fuzzy graph related to power resource.

Fig. 6

Two intuitionistic fuzzy threshold subgraphs.

It should be noted that the threshold t₁ means the limit amount of electricity replenishment, and m - t₂ means the limit amount of power loss and unforeseen electricity consumption, where m is the number of elements of maximum independent set of the underlying graph of a IFTG. For example, we can obtain that t₁ = 0 .9 and t₂ = 2.92 from the first IFTG of Fig. 6, and t₁ = 0 .9 and t₂ = 2 . 955 from the second IFTG of Fig. 6. Note that {a, b, y} is the maximum independent set of the underlying graph of the first IFTG, and $\begin{matrix} μ_{A} (a) & + μ_{A} (b) = 0.8, μ_{A} (a) + μ_{A} (b) \\ + μ_{A} (y) = 1.7 . \end{matrix}$

From the first IFTG of Fig. 6, we know the power station “x” can provide 0.85 amount of electricity replenishment, while the power station “y” can also provide 0.9 amount of electricity replenishment. Obviously, the two power stations can supply enough electricity for two cities, which need at least 0.8 amount of electricity for actual consumption. Besides, we know there are about 0.08 (0 . 08 = 3 -2.92) amount of power loss and unforeseen electricity consumption. Simultaneously for the second IFTG, the maximum independent set is {c, d, e}, and $\begin{matrix} μ_{A} (c) + μ_{A} (d) + μ_{A} (e) = 0.85 . \end{matrix}$

Therefore we know the power station “y” can provide 0.9 amount of electricity replenishment for three cities, which need at least 0.85 amount of electricity for actual consumption. What’s more, we also know there are about 0.045 (0 . 045 = 3 -2 . 955) amount of power loss and unforeseen electricity consumption.

From the above analysis, we know that it is really important to apply IFTG in controlling power resources. Moreover, through this application, we know that IFTGs are more appropriate than fuzzy threshold graphs in controlling power resource, because intuitionistic sets are more suitable and powerful to deal with uncertainty and vagueness compared to fuzzy sets.

5. Conclusion

Considering intuitionistic fuzzy sets are more suitable and powerful to deal with uncertainty and vagueness compared to fuzzy sets, intuitionistic fuzzy models can give more precision and compatibility than fuzzy models in many applications. So we have introduced the notions of IFTGs, intuitionistic fuzzy alternating 4-cycle, and threshold dimension of IFGs. We have proved that under some conditions, an IFG is equivalent to an IFTG. Some other properties related to IFTGs have also been studied in this paper. Especially, we have obtained that the underlying graph of each IFG is a split graph, and conversely, for a given split graph can be converted to an IFTG. Finally, two applications of IFTGs have shown that IFTGs can be used to control water resource and power resource, and this shows that IFTGs are more appropriate than fuzzy threshold graphs in controlling water resource and power resource.

Our future work will be done on applications of IFTGs in set packing problems, and we will propose efficient algorithms to search the IFTGs from IFGs. Besides, we will further discuss about the relationships between IFTGs and its intuitionistic fuzzy independent sets, and try to do a deep research on the IFTGs theory.

Footnotes

Acknowledgments

Professor Guantao Chen, Georgia State University of the USA, provides important suggestions to improve the quality of this paper. The authors are very grateful for his contributions.

This paper is supported by NSFC (No. 61572011), and Hebei Key Laboratory of Machine Learning and Computational Intelligence.

References

Akram and

N.O.

Alshehri , Intuitionistic fuzzy cycles and intuitionistic fuzzy trees. Scientific World Journal, 2014. http://dx.doi.org/10.1155/2014/305836.

Akram and

Davvaz , Strong intuitionistic fuzzy graphs, Filomat 26(1) (2012), 177–196.

Akram and

W.A.

Dudek , Intuitionistic fuzzy hypergraphs with applications, Information Sciences 218(2013), 182–193.

Akram and

W.A.

Dudek , Interval-valued fuzzy graphs, Computers and Mathematics with Applications 61 (2011), 289–299.

Akram and

Akmal , Operations on intuitionistic fuzzy grap structures, Fuzzy Information and Engineering 8 (2016), 389–410.

Akram and

Shahzadi , Novel intuitionistic fuzzy soft multiple-attribute decision-making methods, Neural Computing and Applications 29(7) (2018), 435–447.

Alaoui , On fuzzification of some concepts of graphs, Fuzzy Sets and Systems 101 (1999), 363–389.

Alshehri1 and

Akram , Intuitionistic Fuzzy Planar Graphs, Discrete Dynamics in Natureand Society 2014, 2014, http://dx.doi.org/10.1155/2014/397823.

Andelic and

S.K.

Simic , Some notes on the threshold graphs, Discrete Mathematics 310 (2010), 2241–2248.

10.

K.T.

Atanassov , Intuitionistic fuzzy sets: Theory, applications, Studies in fuzziness and soft computing, Heidelberg, New York, Physica-Verl., 1999.

11.

K.T.

Atanassov , Intuitionistic fuzzy sets, Fuzzy Sets and Systems 20 (1986), 87–96.

12.

K.T.

Atanassov ,

Pasi ,

Yager and

Atanassova , Intuitionistic fuzzy graph interpretations of multi-person multi-criteria decision making, EUSFLAT Conf (2003), 177–182.

13.

Bhattacharya , Some remarks on fuzzy graphs, Pattern Recognition Letter 6 (1987), 297–302.

14.

K.R.

Bhutani , On automorphism of fuzzy graphs, Pattern Recognition Letter 9 (1989), 159–162.

15.

K.R.

Bhutani and

Battou , On M -strong fuzzy graphs, Information Sciences 155 (2003), 103–109.

16.

K.R.

Bhutani ,

Moderson and

Rosenfeld , On degrees of end nodes and cut nodes in fuzzy graphs, Iran J Fuzzy Syst 1(1) (2004), 53–60.

17.

K.R.

Bhutani ,

Rosenfeld , Strong arcs in fuzzy graphs, Information Sciences 152 (2003), 319–322.

18.

Chvatal and

P.L.

Hammer , Set-packing problems and threshold graphs, CORR, 73-21, University of Waterloo, Canada, 1973.

19.

P.L.

Hammer ,

U.N.

Peled and

Sun , Difference graphs, Discrete Applied Mathematics 28(1) (1990), 35–44.

20.

K.P.

Huber and

M.R.

Berthold , Application of fuzzy graphs for metamodeling, Proceedings of the 2002 IEEE Conference 2002, 640–644.

21.

M.G.

Karunambigai ,

Parvathi and

Buvaneswari , Arc in intuitionistic fuzzy graphs, Notes on Intuitionistic Fuzzy Sets 17 (2011), 37–47.

22.

M.G.

Karunambigai ,

Rangasamy ,

K.T.

Atanassov and

Palaniappan , An intuitionistic fuzzy graph method for finding the shortest paths in networks, in:

Castillo et al. (Eds.), Theoretical Advances and Applications of Fuzzy Logic and Soft Computing, vol. 42, Springer, Berlin, Heidelberg, 2007, pp. 3–10.

23.

M.G.

Karunambigai ,

Rangasamy ,

Buvaneswari , Constant intuitionistic fuzzy graphs, Notes on Intuitionistic Fuzzy Sets 17(1) (2011), 37–47.

24.

A.N.

Gani and

S.S.

Begum , Degree, order and size in intuitionistic fuzzy graphs, International journal of Algorithms, Computing and Mathematics 3(3) (2010), 11–16.

25.

A.N.

Gani ,

S.Y.

Mohamed and

R.J.

Hussain , Point set domination of intuitionistic fuzzy graphs, International Journal of Fuzzy Mathematical Archive 7(1) (2015), 43–49.

26.

Kiss , An application of fuzzy graphs in database theory, Pure Mathematics and Applications 1 (1991), 337–342.

27.

R.M.

Makwana ,

V.K.

Thakar and

N.C.

Chauhan , Extraction of illumination invariant features using fuzzy threshold based approach, IJCA (2011), 25–31.

28.

Mathew and

M.S.

Sunitha , Types of arcs in a fuzzy graph, Information Sciences 179 (2009), 1760–1768.

29.

Mathew and

M.S.

Sunitha , Node connectivity, arc connectivity of a fuzzy graph, Information Sciences 180 (2010), 519–531.

30.

J.N.

Mordeson and

C.S.

Peng , Operations on fuzzy graphs, Information Sciences 79 (1994), 159–170.

31.

J.N.

Mordeson , Fuzzy line graphs, Pattern Recognition Letter 14 (1993), 381–384.

32.

J.N.

Mordeson and

P.S.

Nair , Fuzzy graphs and fuzzy hypergraphs, Physica Verlag, Heidelberg 1998; Second Edition 2001.

33.

J.N.

Mordeson and

P.S.

Nair , Cycles, cocyles of fuzzy graphs, Information Sciences 90 (1996), 39–49.

34.

Nagoorgani ,

Akram and

Anupriya , Double domination on intuitionistic fuzzy graphs, Journal of Applied Mathematics and Computing 52 (2016), 515–528.

35.

Nagoorgani and

Radha , On regular fuzzy graphs, J Phys Sci 12 (2008), 33–40.

36.

Parvathi and

M.G.

Karunambigai , Intuitionistic fuzzy graphs, Journal of computational Intelligence: Theory and Applications (2006), 139–150.

37.

Parvathi ,

M.G.

Karunambigai and

K.T.

Atanassov , Operations on intuitionistic fuzzy graphs, Fuzzy Systems, IEEE International Conference (2009), 1396–1401.

38.

Parvathi , and

Tamizhendhi , Domination in intuitionistic fuzzy graphs, Fourteenth Int Conf on IFSs, Sofia (2010), 39–49.

39.

Pasi ,

Yager and

K.T.

Atanassov , Intuitionistic fuzzy graph interpretations of multi-person multi-criteria decision making: Generalized net approach, Second IEEE International Conference on Intelligent System (2004), 434–439.

40.

U.N.

Peled and

N.V.

Mahadev , Threshold Graphs and Related Topics, North Holland, 1995.

41.

Pramanik ,

Pal and

Mondal , Interval-valued fuzzy threshold graph, Pacific Science Review A: Natural Science and Engineering 18 (2016), 66–71.

42.

Pramanik ,

Samanta and

Pal , Interval-valued fuzzy planar graphs, Int J Mach Learn Cybern 7(4) (2016), 653–664.

43.

Pramanik ,

Samanta ,

Sarkar ,

Pal , Fuzzy f-tolerance competition graphs, Soft Comput. 2016, http://dx.doi.org/10.1007/s00500-015-2026-5.

44.

Rosenfeld , Fuzzy graphs, Fuzzy Sets and their Applications, in:

L.A.

Zadeh ,

K.S.

Fu ,

Shimura (Eds.), Academic Press, New York, 1975, pp. 77-95.

45.

Samanta and

Pal , Fuzzy threshold graphs, CiiT International Journal of Fuzzy Systems 3 (2011), 1–9.

46.

Sarwar ,

Akram , An algorithm for computing certain metrics in intuitionistic fuzzy graphs, Journal of Intelligent and Fuzzy Systems 30 (2016), 2405–2416.

47.

Shahzadi and

Akram , Graphs in an intuitionistic fuzzy soft environment, Axioms 7(2) (2018), 1–16.

48.

M.S.

Sunitha and

Vijayakumar , Complement of a fuzzy graph, Indian Journal of Pure, Applied Mathematics 33(9) (2002), 1451–1464.

49.

H.L.

Yang ,

S.G.

Li ,

W.H.

Yang and

Lu , Notes on “Bipolar fuzzy graphs”, Information Sciences 242 (2013), 113–121.

50.

L.A.

Zadeh , Fuzzy sets, Information Control 8 (1965), 338–353.

51.

L.A.

Zadeh , Toward a generalized theory of uncertainty(GTU)-anoutline, Information Sciences 172 (2005), 1–40.

52.

L.A.

Zadeh , Is there a need for fuzzy logic? Information Sciences 178(13) (2008), 2751–2779.

53.

L.A.

Zadeh , Similarity relations, fuzzy orderings, Information Sciences 3 (1971), 177–200.

54.

Zhan ,

Masood and

Akram , Novel decision-making algorithms based on intuitionistic fuzzy rough environment, International Journal of Machine Learning and Cybernetics, 2018, DOI: 10.1007/s13042-018-0827-4

Intuitionistic fuzzy threshold graphs

Abstract

Keywords

1. Introduction

2. Preliminaries

Table 1 Membership degrees and non-membership degrees for vertices and edges Vertices a b c d e μ A 0.1 0.5 0.2 0.4 0.2 v A 0.9 0.4 0.7 0.6 0.8 Edges (a,b) (b,c) (b,d) (b,e) (e,d) (c,d) μ B 0.1 0.2 0.4 0.2 0.2 0.2 v B 0.9 0.7 0.6 0.8 0.7 0.6

4.1. An application of intuitionistic fuzzy threshold graph in water resource controlling

Footnotes

Acknowledgments

References

Table 1
Membership degrees and non-membership degrees for vertices and edges

Vertices a b c d e

μ _A 0.1 0.5 0.2 0.4 0.2

v _A 0.9 0.4 0.7 0.6 0.8

Edges (a,b) (b,c) (b,d) (b,e) (e,d) (c,d)

μ _B 0.1 0.2 0.4 0.2 0.2 0.2

v _B 0.9 0.7 0.6 0.8 0.7 0.6