Menger’s theorem for m-polar fuzzy graphs and application of m-polar fuzzy edges to road network

1 Introduction

Zadeh [32] introduced a mathematical framework to discuss the imprecision and uncertainty in real systems. Since then, fuzzy set theory has emerged as an active research branch in several areas such as graph theory, social sciences, medicine, decision-making, signal processing, artificial intelligence, engineering, and management. Chen et al. [12] proposed the concept of m-polar fuzzy set as a generalized approach of fuzzy set. The reason for the existence of “multi-polar information” is that sometimes the data for real-world problems comes from m agents (m ≥ 2). For instance, the exact degree of human telecommunications security is a point within [0, 1]  ^m (m = 7 ×10⁹) as different people are monitored at different times. There exist many other examples like truthfulness of logical formulas based on m logical implication operators (m ≥ 2), the similarity between two logical formulas based on m logical implication operators (m ≥ 2), magazine ordering results, university ordering results, and rough set inclusion degrees. Consider the statement, “China is a good country” as an example. This statement may not have its membership value as a single real number in [0, 1]. Becoming a good country might have different constituents such as good at political awareness, good at public transportation systems, good at medical facilities etc. Each constituent can be a real number in [0, 1]. If j shows the number of such constituents/components under study, then the membership value of fuzzy sentences is a j-tuple of real numbers in [0, 1].

Based on fuzzy relations [32], Kaufmann [15] provided the basic idea related to fuzzy graphs. Fuzzy graph theory has many applications in various fields such as cluster analysis, network analysis, information theory and database theory. Rosenfeld [25] also studied fuzzy relations on fuzzy sets. He investigated fuzzy analogues of certain elementary graph-theoretical concepts, including paths, cycles, trees, connectedness, bridges, and determined several of their related properties. Actually, the theory of fuzzy graphs was established by Rosenfeld [25]. Fuzzy graphs were also independently introduced by Yeh and Bang [31]. They presented various connectivity parameters of a fuzzy graph and examined their applications. Mordeson and Nair [21] introduced different operations on fuzzy graphs. Later on, some concepts of connectivity regarding fuzzy cut-vertex and fuzzy bridges were provided by Bhattacharya [9]. Bhattacharya and Suraweera [10] presented an algorithm to find the connectivity between pairs of vertices in fuzzy graphs. Banerjee [8] provided an optimal algorithm to find the strength of connectedness in fuzzy graphs. Tong and Zheng [29] obtained an algorithm to find the connectedness matrix of a fuzzy graph. Xu [30] utilized connectivity parameters of fuzzy graphs to the problems of chemical structures. Bhutani and Rosenfeld [11] introduced the concepts of strong edges and strong paths in fuzzy graphs. Mathew and Sunitha [18] classified different types of edges in fuzzy graphs and obtained the edge identification procedure. In [18], a sufficient condition for a vertex to become a fuzzy cut-vertex is also established.

Menger’s theorem in crisp graph theory has a lot of applications in decision-making and social networks. But, a fuzzy graph version of Menger’s theorem [20] is more appropriate and flexible than a crisp graph version. To increase accuracy, a further extended version of Menger’s theorem is discussed in [14]. One of the significant differences between crisp graph and fuzzy graph is that the strength of connectedness between pairs of vertices in crisp graph (G^★) is either 0 or 1 while in fuzzy graph, it can be any real number in [0, 1]. Similarly, the reduction of flow between pairs of vertices is more applicable and it may frequently happen compared to the total separation of flow or the disconnection of the entire network. The concept of fuzzy cut-vertex was defined by Rosenfeld [26] in order to discuss such characteristics of information networks. Akram and Waseem [3] introduced the notion of m-polar fuzzy graphs (mPF graphs). An mPF graph can be useful in uncertain problem handling multi-polarity to get more precise and accurate outcomes. Later on, different authors presented many new concepts, including mPF labeling graphs [1], mPF graph structures [2], certain types of edge mPF graphs [4], certain types of irregular mPF graphs [7], faces and dual of mPF graphs [13], coloring of mPF graphs [16], products in mPF graphs [27], double dominating energy of mPF hypergraphs [28], novel applications of mPF hypergraphs [5], and transversals of mPF hypergraphs [6].

Recently, the strength of connectedness between pairs of vertices in mPF graphs has been studied in [1, 17]. Mandal et al. [17] discussed certain basic concepts like strongest mPF path, strong mPF path, mPF bridge, mPF forests etc. mPF graph theory is a generalization of fuzzy graph theory. There are still many fuzzy graph theoretic results which have not been yet studied in case of mPF graph theory, e.g., edge analysis, vertex and edge connectivity parameters etc. Edge analysis is very important for identifying the nature of edges. To our knowledge, no such edge analysis is available in literature of mPF graph theory. This motivates us to discuss the types of mPF edges in an mPF graph. Depending on the strength of connectedness between pairs of vertices, we categorize mPF edges in an mPF graph into strong and weak mPF edges. Further, we classify strong mPF edges into two types termed as α-strong and β-strong mPF edges and discuss two types of weak mPF edges termed as δ-weak and δ^*-weak mPF edges. The analysis of types of mPF edges explores the basic structure of an mPF graph. Also, in terms of application, this classification highlights the significance of each edge, which will result in minimizing the cost and improving the efficiency of the uncertain system, especially in problems involving networks. The divisions of this study are as follows: In section 2, some basic definitions and results which are helpful in constructing the properties relating to our research work are given. In section 3, we classify the different types of mPF edges namely α-strong mPF edges, β-strong mPF edges, δ-weak mPF edges, δ^*-weak mPF edges. We discuss some remarks related to the strongest mPF edges, strong mPF edges and weak mPF edges. We distinguish between strong mPF path and strongest mPF path. We analyze types of mPF edges in an mPF cycle. In section 4, we first define strength reduction mPF vertex and strength reduction mPF edge. On the basis of these defined terms, we modify the definitions of mPF cut-vertex and mPF bridge. We investigate the criterion to find out mPF cut-vertex and mPF bridge. We define x _i -x _k strength reducing set of vertices and x _i -x _k strength reducing set of edges in an mPF graph. We show that internally disjoint [x _i , x _k ]-mPF paths are always edge disjoint [x _i , x _k ]-mPF paths but converse may not be true. We also define the strong size of mPF graph. Then, we present the vertex version of Menger’s theorem for mPF graphs with proof and apply this theorem to find the suitable strongest mPF paths from non-affected cities to affected cities due to an earthquake. We also discuss the edge version of Menger’s theorem for mPF graphs and highlight the difference between both versions. Section 5 deals with an application related to the types of m-PF edges to determine different traffic-accidental zones in a road network. The comparison between our research work and existing techniques is given in Section 6. Section 7 highlights the concluded remarks of our research study.

2 Preliminaries

In this section, some basic definitions are given. These definitions are helpful to construct the properties related to this study.

Definition 2.1. [12] An m-polar fuzzy set (mPF set) on a non-empty set X is a mapping Ψ : X → [0, 1]  ^m . The set of all mPF sets on X is denoted by m (X). Note that for a natural number m, [0, 1]  ^m is considered as a poset with the point-wise order ≤, where “≤” is defined by x ≤ y ↔ P _j  (x) ≤ P _j  (y), where x, y ∈ [0, 1]  ^m and for each 1 ≤ j ≤ m, P _j  : [0, 1]  ^m  → [0, 1] is defined as the j-th projection mapping.

Definition 2.2. [3] Let Ψ be an mPF set on X. An m-polar fuzzy relation (mPF relation) Φ on Ψ is a mapping Φ = (P₁ ∘ Φ, P₂ ∘ Φ, …, P _m  ∘ Φ) : Ψ ⟶ Ψ such that for all x, y ∈ X, P _j  ∘ Φ (xy) ≤ inf {P _j  ∘ Ψ (x) , P _j  ∘ Ψ (y)}, 1 ≤ j ≤ m, where P _j  ∘ Ψ (x) and P _j  ∘ Φ (xy) represent the j-th membership value of vertex x and edge xy, respectively. An mPF relation Φ on Ψ is said to be a symmetric relation if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) = P _j  ∘ Φ (yx), where x, y ∈ X.

Definition 2.3. [3] An mPF graph on X is an ordered pair of functions G = (Ψ, Φ), where Ψ : X ⟶ [0, 1]  ^m is an mPF set on X and Φ : X × X ⟶ [0, 1]  ^m is an mPF relation on X such that for each xy ∈ E, P _j  ∘ Φ (xy) ≤ inf {P _j  ∘ Ψ (x) , P _j  ∘ Ψ (y)}, 1 ≤ j ≤ m and for each xy ∈ X × X \ E, Φ (xy) = 0. Note that 0 = (0, 0, …, 0) is the smallest element in [0, 1]  ^m and 1 = (1, 1, …, 1) is the largest element in [0, 1]  ^m . Here, Φ is a symmetric mPF relation on Ψ. We call Ψ and Φ an mPF vertex set (mPF vertex set) and mPF edge set (mPF edge set) of G, respectively.

Here after G = (Ψ, Φ) represents an mPF graph of the crisp graph G^★ = (X, E).

Definition 2.4. [17] An m-polar fuzzy path (mPF path) P in an mPF graph G = (Ψ, Φ) is a sequence of distinct vertices x = x₁, x₂, x₃, …, x _n  = y such that there exists at least one 1 ≤ j ≤ m satisfying P _j  ∘ (x _i x_i+1) >0 for each 1 ≤ i ≤ n-1. An mPF path P between two vertices x _i and x _k is denoted by [x _i , x _k ]-mPF path, where 1 ≤ i, k ≤ n. An [x _i , x _k ]-mPF path is said to be an m-polar fuzzy cycle (mPF cycle) C if x _i  = x _k and n ≥ 3. The strength of an mPF path P is defined as S ( P ) = ( inf 1 ≤ i < k ≤ n P 1 ∘ Φ ( x i x k ) , inf 1 ≤ i < k ≤ n P 2 ∘ Φ ( x i x k ) , … , inf 1 ≤ i < k ≤ n P m ∘ Φ ( x i x k ) ) . The strength of connectedness between two vertices x _i and x _k (CONN _G  (x _i x _k )) is the maximum of the strengths of all mPF paths between x _i and x _k . Mathematically, it is defined as CONN _G  (x _i x _k ) = ((P₁ ∘ Φ (x _i x _k )) ^∞, (P₂ ∘ Φ (x _i x _k )) ^∞, …, (P _m  ∘ Φ (x _i x _k )) ^∞), where ( P j ∘ Φ ( x i x k ) ) ∞ = sup { inf 1 ≤ i < k ≤ n P j ∘ Φ ( x i x k ) } . An mPF path is said to be a strongest mPF path if S (P) = CONN _G  (x _i x _k ). An mPF graph G = (Ψ, Φ) is defined to be connected if there is an m-PF edge between each pair of vertices, i.e., (P _j  ∘ Φ (x _i x _k )) ^∞ > 0 for at least one j.

Through out this study, we assume that G is a connected mPF graph.

Example 2.1. Let X = {x₁, x₂, x₃, x₄} be the set of vertices and E = {x₁x₂, x₁x₃, x₁x₄, x₂x₃, x₂x₄, x₃x₄} be the set of edges. Let Ψ be a 3PF set on X (given in Table 1) and Φ be a 3PF relation on X (given in Table 2). The correspondent 3PF graph G = (Ψ, Φ) is shown in Fig. 1. Consider two vertices x₁ and x₄. The mPF paths from x₁ to x₄ with their corresponding strengths are P¹: x₁-x₄ S (P¹) = (0.4, 0.3, 0.6), P²: x₁-x₂-x₄ S (P²) = (0.4, 0.3, 0.6), P³: x₁-x₃-x₄ S (P³) = (0.4, 0.3, 0.5), P⁴: x₁-x₂-x₃-x₄ S (P⁴) = (0.4, 0.3, 0.5), P⁵: x₁-x₃-x₂-x₄ S (P⁵) = (0.4, 0.3, 0.5). The strength of connectedness between x₁ and x₄ is CONN _G  (x₁x₄) = (0.4, 0.3, 0.6). Since, S (P¹) = S (P²) = (0.4, 0.3, 0.6) = CONN _G  (x₁x₄), therefore P¹ and P² both are strongest [x₁, x₄]-3PFPs.

OPEN IN VIEWER

Fig. 1

3PF graph.

Definition 2.5. An mPF graph G = (Ψ, Φ) is defined to be strong if for each xy ∈ E, P _j  ∘ Φ (xy) = inf {P _j  ∘ Ψ (x) , P _j  ∘ Ψ (y)}, 1 ≤ j ≤ m. An mPF graph G = (Ψ, Φ) is defined to be complete if for each x, y ∈ X, P _j  ∘ Φ (xy) = inf {P _j  ∘ Ψ (x) , P _j  ∘ Ψ (y)}, 1 ≤ j ≤ m. An mPF graph G ˜ = ( Ψ ˜ , Φ ˜ ) is said to be a partial mPF subgraph of mPF graph G = (Ψ, Φ) if for every 1 ≤ j ≤ m, P j ∘ Ψ ˜ ( x ) ≤ P j ∘ Ψ ( x ) for each x ∈ X ˜ and P j ∘ Φ ˜ ( xy ) ≤ P j ∘ Φ ( xy ) for each xy ∈ E ˜ . In particular, a partial mPF subgraph G ˜ = ( Ψ ˜ , Φ ˜ ) is said to be an mPF subgraph of G = (Ψ, Φ) if for every 1 ≤ j ≤ m, P j ∘ Ψ ˜ ( x ) = P j ∘ Ψ ( x ) for each x ∈ X ˜ and P j ∘ Φ ˜ ( xy ) = P j ∘ Φ ( xy ) for each xy ∈ E ˜ . An mPF subgraph G ˜ = ( Ψ ˜ , Φ ˜ ) spans the mPF graph G = (Ψ, Φ) if for every 1 ≤ j ≤ m, P j ∘ Ψ ˜ ( x ) = P j ∘ Ψ ( x ) for each x ∈ X, i.e., X = X ˜ and Ψ ( x ) = Ψ ˜ ( x ) for each x ∈ X = X ˜ .

Example 2.2. Let X = {x₁, x₂, x₃, x₄, x₅} be the set of vertices and E = {x₁x₂, x₁x₃, x₁x₅, x₂x₄, x₃x₄, x₃x₅} be the set of edges. Let Ψ be a 4PF set on X (given in Table 3) and Φ be a 4PF relation on X (given in Table 4). The correspondent 4PF graph G = (Ψ, Φ) is shown in Fig. 2(a). According to Definition 2.5, partial mPF subgraph, mPF subgraph, spanning mPF subgraph are shown in Fig. 2(b), Fig. 2(c), Fig. 2(d), respectively.

OPEN IN VIEWER

Fig. 2

4PF graph.

Definition 2.6. Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is defined to be a strong mPF edge of G if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) ≥ P _j  ∘ CONN_G\{xy} (xy), i.e., if the membership value of edge xy ∈ E is at least as great as the connectedness of its incident vertices x and y when edge xy is deleted then edge xy is said to be a strong mPF edge of G. The vertices x and y incident to a strong mPF edge are called strong mPF neighbors if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) >0. An [x, y]-mPF path P is defined to be a strong path if each edge contributing to that path is strong mPF edge.

Definition 2.7. [17] Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is defined to be a weak mPF edge of G if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) < P _j  ∘ CONN_G\{xy} (xy). The vertices x and y incident to a weak mPF edge are called weak mPF neighbors.

Definition 2.8. [17] Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is defined to be a weakest mPF edge of G if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) < P _j  ∘ Φ (ab) for any edge ab ∈ E different from edge xy.

Through out this research study, we will use the following list of abbreviations (Table 5).

In crisp graph theory, each edge in the network is strong. For this reason edge analysis has no importance in crisp graph theory. However, in mPF graph theory, mPF edges in the mPF graphs are defined as strong mPF edges and non-strong mPF edges [17]. Therefore, mPF edge analysis in mPF graph theory has a significant role and it is very important to determine the nature of an mPF edge in an mPF graph. There is no such analysis on mPF edges in mPF graph theory in the literature. Depending on strength of connectedness between pairs of adjacent vertices of an mPF graph G, we characterize mPF edges according to the following definitions:

Definition 3.1. Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is defined to be a strong mPF edge of G if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) ≥ P _j  ∘ CONN_G\{xy} (xy), i.e., if the membership value of edge xy ∈ E is at least as great as the connectedness of its incident vertices x and y when edge xy is deleted then edge xy is said to be strong mPF edge of G. A strong mPF edge xy ∈ E is defined to be an α-strong mPF edge (α-edge) if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) > P _j  ∘ CONN_G\{xy} (xy). A strong mPF edge xy ∈ E is defined to be a β-strong mPF edge (β-edge) if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) = P _j  ∘ CONN_G\{xy} (xy).

Definition 3.2. Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is defined to be a weak mPF edge of G if it is not strong mPF edge of G, i.e., if it does not satisfy the condition P _j  ∘ Φ (xy) ≥ P _j  ∘ CONN_G\{xy} (xy) for some 1 ≤ j ≤ m. A weak mPF edge xy is defined to be a δ-weak mPF edge (δ-edge) if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) < P _j  ∘ CONN_G\{xy} (xy). A weak mPF edge xy ∈ E is defined to be a mixed mPF edge if it is not δ-edge, i.e., a weak mPF edge xy is said to be a mixed mPF edge if it is strong as well as weak with respect to its components.

Through out this study, we assume that G has no mixed mPF edges.

Definition 3.3. Let G = (Ψ, Φ) be an mPF graph. An edge ab ∈ E is defined to be a weakest mPF edge of G if for each 1 ≤ j ≤ m, P _j  ∘ Φ (ab) < P _j  ∘ Φ (xy) for any edge xy ∈ E different from edge ab ∈ E. An edge cd ∈ E is defined to be a strongest mPF edge of G if for each 1 ≤ j ≤ m, P _j  ∘ Φ (cd) > P _j  ∘ Φ (xy) for any edge xy ∈ E different from edge cd.

Definition 3.4. Let G = (Ψ, Φ) be an mPF graph and ab be a weakest mPF edge of G. A δ-edge xy is defined to be a δ^* mPF edge (δ^*-edge) if for each 1 ≤ j ≤ m, P _j  ∘ Φ (xy) > P _j  ∘ Φ (ab), i.e., a δ-edge xy is said to be a δ^*-edge if its membership value is greater than the membership value of the weakest mPF edge of G.

Example 3.1. Let X = {x₁, x₂, x₃, x₄} be the set of vertices and E = {x₁x₂, x₁x₃, x₂x₃, x₂x₄, x₃x₄} be the set of edges. Let Ψ be a 3PF set on X (given in Table 6) and Φ be a 3PF relation on X (given in Table 7). The correspondent 3PF graph G = (Ψ, Φ) is shown in Fig. 3. The strength of connectedness between vertices of G are: CONN _G  (x₁x₂) = (0.3, 0.2, 0.3), CONN _G  (x₁x₃) = (0.3, 0.2, 0.3), CONN _G  (x₂x₃) = (0.7, 0.9, 0.8), CONN _G  (x₂x₄) = (0.4, 0.3, 0.5) and CONN _G  (x₃x₄) = (0.4, 0.3, 0.5). It is easy to verify that x₂x₄ and x₃x₄ are α-edges, x₁x₂ and x₁x₃ are β-edges and x₂x₃ is δ-edge. The edge x₂x₃ is also δ^*-edge.

OPEN IN VIEWER

Fig. 3

3PF graph.

Remarks:

(i)- There may be one or more than one weakest as well as strongest mPF edges in an mPF graph G. It may also be possible that there does not exist any weakest or strongest mPF edges. For example, in G of Fig. 3, x₁x₂ and x₁x₃ both are weakest mPF edges and x₃x₄ is a strongest mPF edge.

(ii)- A strongest mPF edge of G is always strong mPF edge. But, converse may not hold, i.e., a strong mPF edge of G needs not be a strongest mPF edge. For example, in G of Fig. 3, x₁x₂, x₁x₃ and x₂x₄ are strong mPF edges but they are not strongest mPF edges. Here, x₃x₄ is strongest mPF edge of G.

(iii)- A weakest mPF edge of G needs not be a weak mPF edge and vice versa, i.e., a weak mPF edge of G needs not be a weakest mPF edge. For example, in G of Fig. 3, x₁x₂ and x₁x₃ both are weakest mPF edges but they are not weak mPF edges. x₂x₃ is weak mPF edge but it is not weakest mPF edge.

(iv)- A weakest mPF edge of G may be a strong mPF edge (β-edge). For example, in G of Fig. 3, x₁x₂ and x₁x₃ both are weakest mPF edges as well as they are β-edges.

(v)- The membership value of a weak mPF edge may exceed the membership value of a strong mPF edge. For instance, in G of Fig. 3, the membership value of δ-edge x₂x₃ is greater than the membership value of β-edges x₁x₂ and x₁x₃.

Definition 3.5. Let G = (Ψ, Φ) be an mPF graph and P be an mPF path in G. Then P is defined to be an α-strong mPF path (α-path) if all of its distinct edges are α-edges. Similarly, it is defined to be a β-strong mPF path (β-path) if all of its distinct edges are β-edges.

Example 3.2. Consider a 3PF graph G in Fig. 3. Here, the mPF path P : x₂-x₄-x₃ is α-path as edges x₂x₄ and x₄x₃ both are α-edges. Also, the mPF path P : x₂-x₁-x₃ is β-path as edges x₂x₁ and x₁x₃ both are β-edges.

Types of mPF edges in strongest mPF path: It is interesting to note that all types of mPF edges may exist in the strongest mPF path in G. A strongest mPF path containing no δ-edges is a strong mPF path in G. However, a strong mPF path needs not be a strongest mPF path in G. A strong mPF path from vertex x _i to x _k will also be a strongest mPF path if it satisfies one of the condition, i.e., it is the unique strong mPF path from x _i to x _k or it contains no β-edges or all mPF paths from vertex x _i to x _k are of equal strength.

Types of mPF edges in mPF cycle: It is also interesting to note that more than one weakest mPF edges must contain in an [x _i , x _k ]-mPF cycle in G. This means that an mPF cycle can not have δ-edge (otherwise δ-edge will become a unique weakest mPF edge). Also, note that α-edges can never be weakest mPF edges. This shows that all mPF edges in an mPF cycle can not be α-edges. Thus, weakest mPF edges in an mPF cycle are β-edges and the remaining are α-edges.

In network theory, x _i -x _k separating set X′ of vertices is a collection of vertices in G^★ = (X, E) whose removal disconnects G^★ into different components G^★ \ {x _k } and G^★ \ {x _i } with vertices x _i and x _k not belong to the same components of G^★ \ X′. Similarly, x _i -x _k separating set E′ of edges is defined. See also [19, 20]. Since, the reduction in strength is more significant and frequent in networks, therefore we define x _i -x _k strength reducing set of vertices (SRSVs) and x _i -x _k strength reducing set of edges (SRSEs) in an mPF graph G = (Ψ, Φ) as follows:

Definition 4.1. Let G = (Ψ, Φ) be an mPF graph. A vertex x ∈ X is defined to be a zero-strength reduction mPF vertex of G if we obtained a partial mPF subgraph G ˜ = G \ { x } by replacing Ψ ( x ) = 0 = Ψ ˜ ( x ) in which for each 1 ≤ j ≤ m, P _j  ∘ CONN_G\{x} (yz) =0 for some pair of vertices y and z of G \ {x}, i.e., x ∈ X is said to be a zero-strength reduction mPF vertex if there is no path between some pair of vertices y and z of G \ {x}. Also, vertex x ∈ X is defined to be a reduction mPF vertex of G if we obtained a partial mPF subgraph G ˜ = G \ { x } by replacing Ψ ˜ ( x ) = 0 in which for each 1 ≤ j ≤ m, P _j  ∘ CONN_G\{x} (yz) < P _j  ∘ CONN _G  (yz) for some pair of vertices y and z of G \ {x}, i.e., x ∈ X is said to be a reduction mPF vertex of G if the removal of x from G reduces the strength of some pair of vertices y, z of G \ {x}.

Definition 4.2 Let G = (Ψ, Φ) be an mPF graph. A vertex x ∈ X is defined to be an mPF cut-vertex of G if we obtained a partial mPF subgraph G ˜ = G \ { x } by replacing Ψ ( x ) = 0 = Ψ ˜ ( x ) in which for each 1 ≤ j ≤ m, either P _j  ∘ CONN_G\{x} (yz) =0 or P _j  ∘ CONN_G\{x} (yz) < P _j  ∘ Ψ (yz) for some pair of vertices y and z of G \ {x}, i.e., x ∈ X is said to be an mPF cut-vertex if it is either a zero-strength reduction mPF vertex or a reduction mPF vertex of G \ {x}.

Theorem 4.1. (Criterion to find out mPF cut-vertex of an mPF graph G) Let G = (Ψ, Φ) be an mPF graph. A vertex x ∈ X is an mPF cut-vertex of G if and only if there exists some pair of vertices y and z (different from x) of G such that each strongest [y, z]-mPF path in G passes through vertex x.

Proof. Let G = (Ψ, Φ) be an mPF graph and vertex x ∈ X be an mPF cut-vertex of G then for each 1 ≤ j ≤ m, either P _j  ∘ CONN_G\{x} (yz) =0 or P _j  ∘ CONN_G\{x} (yz) < P _j  ∘ CONN _G  (yz) for some pair of vertices y and z of G \ {x}. Hence, each strongest [y, z]-mPF path in G passes through vertex x. Conversely, suppose that each strongest [y, z]-mPF path in G passes through vertex x of G then two cases arise:

Case (a). There will be no mPF path path between some pair of vertices y and z of G \ {x}, i.e., for each 1 ≤ j ≤ m, P _j  ∘ CONN_G\{x} (yz) =0. This implies that vertex x is a zero-strength reduction mPF vertex of G.

Case (b). The maximum of strengths of all strongest [y, z]-mPF paths in G \ {x} is less than the maximum of strengths of all strongest [y, z]-mPF paths in G, i.e., P _j  ∘ CONN_G\{x} (yz) < P _j  ∘ CONN _G  (yz) for some pair of vertices y and z of G \ {x}. This implies that vertex x is a reduction mPF vertex of G.

In either case vertex x is an mPF cut-vertex of G. □

Example 4.1. (Illustration of Theorem. 4.1) Let X = {x₁, x₂, x₃, x₄, x₅, x₆, x₇} be the set of vertices and E = {x₁x₄, x₁x₅, x₂x₄, x₂x₅, x₂x₆, x₂x₇, x₃x₆, x₃x₇} be the set of edges. Let Ψ be a 3PF set on X (given in Table 8) and Φ be a 3PF relation on X (given in Table 9). The correspondent 3PF graph G = (Ψ, Φ) is shown in Fig. 4. Consider two vertices x₁ and x₃. The mPF paths from x₁ to x₃ with their corresponding strengths are P¹: x₁-x₄-x₂-x₇-x₃ S (P¹) = (0.1, 0.3, 0.2), P²: x₁-x₅-x₂-x₆-x₃ S (P²) = (0.6, 0.6, 0.7), P³: x₁-x₅-x₂-x₇-x₃ S (P³) = (0.1, 0.3, 0.2), P⁴: x₁-x₄-x₂-x₆-x₃ S (P⁴) = (0.1, 0.3, 0.2) and CONN _G  (x₁x₃) = (0.6, 0.6, 0.7) = S (P²). This shows that P² is the strongest [x₁, x₃]-mPF path. It is easy to see that P² passes through vertices x₂, x₅ and x₆. Therefore, all these vertices are mPF cut-vertices of G with x₂ as a zero-strength reduction mPF vertex while x₅ and x₆ both are as reduction mPF vertices of G.

OPEN IN VIEWER

Fig. 4

3PF graph.

Definition 4.3. Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is defined to be a zero-strength reduction mPF edge of G if we obtained a partial mPF subgraph G ˜ = G \ { xy } by replacing Ψ ( xy ) = 0 = Ψ ˜ ( xy ) in which for each 1 ≤ j ≤ m, P _j  ∘ CONN_G\{xy} (uv) =0 for some pair of vertices u and v of G \ {xy} (where u and v may be taken as vertex x or y but not both at a time), i.e., xy ∈ E is said to be a zero-strength reduction mPF edge if there is no path between some pair of vertices u and v of G \ {xy}. Also, edge xy ∈ E is defined to be a reduction mPF edge of G if we obtained a partial mPF subgraph G ˜ = G \ { xy } by replacing Ψ ( xy ) = 0 = Ψ ˜ ( xy ) in which for each 1 ≤ j ≤ m, P _j  ∘ CONN_G\{xy} (uv) < P _j  ∘ CONN _G  (uv) for some pair of vertices u and v of G \ {xy}, i.e., xy ∈ E is said to be a reduction mPF edge of G if the removal of xy from G reduces the strength of some pair of vertices u and v of G \ {xy}.

Definition 4.4. Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is defined to be a mPF bridge of G if we obtained a partial mPF subgraph G ˜ = G \ { xy } by replacing Ψ ( xy ) = 0 = Ψ ˜ ( xy ) in which for each 1 ≤ j ≤ m, either P _j  ∘ CONN_G\{xy} (uv) =0 or P _j  ∘ CONN_G\{xy} (uv) < P _j  ∘ CONN _G  (uv) for some pair of vertices u and v of G \ {xy}, i.e., xy ∈ E is said to be an mPF bridge if it is either a zero-strength reduction mPF edge or a reduction mPF edge of G \ {xy}.

Theorem 4.2 (Criterion to find out mPF bridge of an mPF graph G) Let G = (Ψ, Φ) be an mPF graph. An edge xy ∈ E is an mPF bridge of G if and only if there exists some pair of vertices w and z of G such that each strongest [w, z]-mPF path in G passes through edge xy.

Proof. Let G = (Ψ, Φ) be an mPF graph and edge xy ∈ E be an mPF bridge of G then for each 1 ≤ j ≤ m, either P _j  ∘ CONN_G\{xy} (wz) =0 or P _j  ∘ CONN_G\{xy} (wz) < P _j  ∘ CONN _G  (wz) for some pair of vertices w and z of G \ {xy}. Hence, each strongest [w, z]-mPF path in G passes through edge xy. Conversely, suppose that each strongest [w, z]-mPF path in G passes through edge xy of G then two cases arise:

Case (a). There will be no mPF path path between some pair of vertices w and z of G \ {xy}, i.e., for each 1 ≤ j ≤ m, P _j  ∘ CONN_G\{xy} (wz) =0. This implies that edge xy is a zero-strength reduction mPF edge of G.

Case (b). The maximum of strengths of all strongest [w, z]-mPF paths in G \ {xy} is less than the maximum of strengths of all strongest [w, z]-mPF paths in G, i.e., P _j  ∘ CONN_G\{xy} (wz) < P _j  ∘ CONN _G  (wz) for some pair of vertices w and z of G \ {xy}. This implies that edge xy is a reduction mPF edge of G.

In either case edge xy is an mPF bridge of G. □

Example 4.2. (Illustration of Theorem. 4.2) Let X = {x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈} be the set of vertices and E = {x₁x₅, x₁x₆, x₂x₅, x₂x₆, x₂x₃, x₃x₇, x₃x₈, x₄x₇, x₄x₈} be the set of edges. Let Ψ be a 3PF set on X (given in Table 10) and Φ be a 3PF relation on X (given in Table 11). The correspondent 3PF graph G = (Ψ, Φ) is shown in Fig. 5. Consider two vertices x₁ and x₄. The mPF paths from x₁ to x₄ with their corresponding strengths are P¹: x₁-x₅-x₂-x₃-x₇-x₄ S (P¹) = (0.1, 0.3, 0.2), P²: x₁-x₆-x₂-x₃-x₈-x₄ S (P²) = (0.1, 0.1, 0.2), P³: x₁-x₆-x₂-x₃-x₇-x₄ S (P³) = (0.4, 0.3, 0.2), P⁴: x₁-x₅-x₂-x₃-x₈-x₄ S (P⁴) = (0.1, 0.1, 0.2) and CONN _G  (x₁x₄) = (0.4, 0.3, 0.2) = S (P³). This shows that P³ is the strongest [x₁, x₄]-mPF path. It is easy to see that P³ passes through edges x₁x₆, x₂x₆, x₂x₃, x₃x₇ and x₄x₇. Therefore, all these edges are mPF bridges of G with x₂x₃ as a zero-strength reduction mPF edge while x₁x₆, x₂x₆, x₃x₇ and x₄x₇ are as reduction mPF edges of G.

OPEN IN VIEWER

Fig. 5

3PF graph.

Definition 4.5. Let G = (Ψ, Φ) be an mPF graph and x _i x _k be an edge of G such that it is not a strong mPF edge. A set X′ of vertices (i.e., X′ ⊂ X) is defined to be an x _i -x _k SRSVs if for each 1 ≤ j ≤ m, P _j  ∘ Φ_G\X′ (x _i x _k ) < P _j  ∘ Φ _G  (x _i x _k ) for some pair of vertices x _i and x _k of G \ X′ (x _i and x _k are not strong mPF neighbors). Here, G \ X′ is partial mPF subgraph of G which we obtained after deleting each vertex in the set X′.

Definition 4.6. Let G = (Ψ, Φ) be an mPF graph. A set E′ of edges (i.e., E′ ⊂ E) is defined to be an x _i -x _k SRSEs if for each 1 ≤ j ≤ m, P _j  ∘ Φ_G\E′ (x _i x _k ) < P _j  ∘ Φ _G  (x _i x _k ) for some pair of vertices x _i and x _k of G \ E′. Here, G \ E′ is partial mPF subgraph of G which we obtained after deleting each edge in the set E′.

Definition 4.7. An x _i -x _k SRSVs with n members is defined to be a minimum x _i -x _k SRSVs if there does not exist any x _i -x _k SRSVs having less than n members. A minimum x _i -x _k SRSVs is denoted by X G ′ ( x i , x k ) .

Definition 4.8. An x _i -x _k SRSEs with n members is defined to be a minimum x _i -x _k SRSEs if there does not exist any x _i -x _k SRSEs having less than n members. A minimum x _i -x _k SRSEs is denoted by E G ′ ( x i , x k ) .

Example 4.3. Let X = {x₁, x₂, x₃, x₄, x₅} be the set of vertices and E = {x₁x₂, x₁x₃, x₂x₃, x₂x₄, x₂x₅, x₃x₅, x₄x₅} be the set of edges. Let Ψ be a 3PF set on X (given in Table 12) and Φ be a 3PF relation on X (given in Table 13). The correspondent 3PF graph G = (Ψ, Φ) is shown in Fig. 6. Consider two vertices x₁ and x₃. The mPF paths from x₁ to x₃ with their corresponding strengths are P¹: x₁-x₂-x₄-x₅-x₃ S (P¹) = (0.2, 0.1, 0.3), P²: x₁-x₂-x₄-x₃ S (P²) = (0.2, 0.1, 0.3), P³: x₁-x₂-x₃ S (P³) = (0.7, 0.6, 0.8) and CONN _G  (x₁x₃) = (0.7, 0.6, 0.8). Here, Φ (x₁x₃) = (0.8, 0.7, 0.9) > (0.7, 0.6, 0.8) = CONN _G  (x₁x₃). Since, x₁x₃ is a strong mPF edge of G, therefore, G has no x₁-x₃ SRSVs. Now, consider two vertices x₁ and x₂. The mPF paths from x₁ to x₂ with their corresponding strengths are P¹: x₁-x₃-x₅-x₄-x₂ S (P¹) = (0.1, 0.0, 0.2), P²: x₁-x₃-x₄-x₂ S (P²) = (0.2, 0.1, 0.3), P³: x₁-x₃-x₂ S (P³) = (0.8, 0.7, 0.9) and CONN _G  (x₁x₂) = (0.8, 0.7, 0.9). Here, Φ (x₁x₂) = (0.7, 0.6, 0.8) < (0.8, 0.7, 0.9) = CONN _G  (x₁x₂). Since, x₁x₂ is not a strong mPF edge of G, therefore, G has X′ = {x₃} as x₁-x₂ SRSVs. Also, G has E′ = {x₁x₃} as x₁-x₂ SRSEs.

OPEN IN VIEWER

Fig. 6

3PF graph.

Remark: x _i -x _k SRSVs in G may not be unique. Also, minimum x _i -x _k SRSVs in G may not be unique but contain same number of vertices. Similarly, x _i -x _k SRSEs in G may not be unique. Also, minimum x _i -x _k SRSEs in G may not be unique but contain same number of edges.

Theorem 4.3. (Criterion to find out x _i -x _k SRSVs in an mPF graph G) Let G = (Ψ, Φ) be a connected mPF graph and x _i x _k be an edge of G such that it is not a strong mPF edge. Then X′ ⊂ X is an x _i -x _k SRSVs in G if and only if each strongest mPF path from vertex x _i to x _k contains at least one vertex of the set X′.

Proof. Let G = (Ψ, Φ) be a connected mPF graph and x _i x _k be an edge of G such that it is not a strong mPF edge. Also, suppose that X′ be an x _i -x _k SRSVs and P be a strongest [x _i , x _k ]-mPF path in G. Suppose on contrary that P does not contain any vertex of X′. Then the removal X′ does not reduce the strength of connectedness between vertices x _i and x _k , i.e., the removal of X′ keep P intact. Thus, partial mPF subgraph G \ X′ still contain [x _i , x _k ]-mPF path P. This implies that CONN_G\X′ (x _i x _k ) = CONN _G  (x _i x _k ). This contradicts the supposition that X′ is an x _i -x _k SRSVs in G. Hence, P must contain at least one vertex of X′ (note that any strong mPF edge is strongest [x _i , x _k ]-mPF path containing no vertex from X′. It is Obvious that this criterion is not true if x _i x _k is strong-mPF edge of G). Now, conversely suppose that each strongest [x _i , x _k ]-mPF path contains at least one vertex of X′ (X′ ⊂ X and x _i , x _k does not belong to X′). Then the removal of X′ destroys every strongest mPF path from x _i to x _k in G. This implies that CONN_G\X′ (x _i x _k ) < CONN _G  (x _i x _k ). Hence, X′ is an x _i -x _k SRSVs in an mPF graph G. □

Example 4.4. (Illustration of Theorem. 4.3) Let X = {x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉} be the set of vertices and E = {x₁x₂, x₁x₄, x₁x₆, x₂x₃, x₃x₅, x₃x₉, x₄x₅, x₆x₇, x₆x₉, x₇x₈, x₈x₉} be the set of edges. Let Ψ be a 3PF set on X (given in Table 14) and Φ be a 3PF relation on X (given in Table 15). The correspondent 3PF graph G = (Ψ, Φ) is shown in Fig. 7. Consider two vertices x₁ and x₃. The mPF paths from x₁ to x₃ with their corresponding strengths are P¹: x₁-x₂-x₃ S (P¹) = (0.2, 0.3, 0.1), P²: x₁-x₄-x₅-x₃ S (P²) = (0.2, 0.3, 0.1), P³: x₁-x₆-x₉-x₃ S (P³) = (0.0, 0.1, 0.0), P⁴: x₁-x₆-x₇-x₈-x₉-x₃ S (P⁴) = (0.2, 0.3, 0.1) and CONN _G  (x₁x₃) = (0.2, 0.3, 0.1) = S (P¹) = S (P²) = S (P⁴). This shows that P¹, P² and P⁴ are the strongest [x₁, x₃]-mPF paths. These strongest [x₁, x₃]-mPF paths are passing through vertices x₂, x₄, x₅, x₆, x₇, x₈ and x₉. According to Theorem 4.3, all possible x₁-x₃ SRSVs (we do not destroy mPF path P³) are listed below:

{x₂, x₄, x₇}, {x₂, x₄, x₈}, {x₂, x₄, x₉},

{x₂, x₅, x₇}, {x₂, x₅, x₈}, {x₂, x₅, x₉},

{x₂, x₄, x₇, x₈}, {x₂, x₄, x₇, x₉}, {x₂, x₄, x₈, x₉}, {x₂, x₅, x₇, x₈},

{x₂, x₅, x₇, x₉}, {x₂, x₅, x₈, x₉}, {x₂, x₄, x₅, x₇}, {x₂, x₄, x₅, x₈}, {x₂, x₄, x₅, x₉},

{x₂, x₄, x₅, x₇, x₈}, {x₂, x₄, x₅, x₇, x₉}, {x₂, x₄, x₅, x₈, x₉},

{x₂, x₄, x₅, x₇, x₈, x₉}.

OPEN IN VIEWER

Fig. 7

3PF graph.

It is interesting to note that in this example minimum x₁-x₃ SRSVs contains at least three vertices. For instance, X G ′ ( x 1 , x 3 ) = { x 2 , x 4 , x 7 } . It is easy to see that each strongest [x₁, x₃]-mPF path contains at least one vertex from X G ′ ( x 1 , x 3 ) .

Theorem 4.4 (Criterion to find out x _i -x _k SRSEs in an mPF graph G) Let G = (Ψ, Φ) be a connected mPF graph and x _i , x _k be any two vertices of G. Then E′ ⊂ E is an x _i -x _k SRSEs in G if and only if each strongest mPF path from vertex x _i to x _k contains at least one edge of the set E′.

Proof. Let G = (Ψ, Φ) be a connected mPF graph and x _i , x _k be any two vertices of G. Also, suppose that E′ be an x _i -x _k SRSEs and P be a strongest [x _i , x _k ]-mPF path in G. Suppose on contrary that P does not contain any edge of E′. Then the removal E′ does not reduce the strength of connectedness between vertices x _i and x _k , i.e., the removal of E′ keep P intact. Thus, partial mPF subgraph G \ E′ still contain [x _i , x _k ]-mPF path P. This implies that CONN_G\E′ (x _i x _k ) = CONN _G  (x _i x _k ). This contradicts the supposition that E′ is an x _i -x _k SRSEs in G. Hence, P must contain at least one vertex of E′. Now, conversely suppose that each strongest [x _i , x _k ]-mPF path contains at least one edge of E′. Then the removal of E′ destroys every strongest mPF path from x _i to x _k in G. This implies that CONN_G\E′ (x _i x _k ) < CONN _G  (x _i x _k ). Hence, E′ is an x _i -x _k SRSEs in an mPF graph G.

Example 4.5. (Illustration of Theorem. 4.4) Consider mPF graph G = (Ψ, Φ) (Fig. 7). It has already observed that P¹, P² and P⁴ are strongest mPF paths from vertex x₁ to x₃. Here, E G ′ ( x 1 , x 3 ) = { x 1 x 2 , x 1 x 4 , x 6 x 7 } . It is easy to see that each strongest [x₁, x₃]-mPF path contains at least one edge from E G ′ ( x 1 , x 3 ) .

Definition 4.9. Let G = (Ψ, Φ) be an mPF graph and P¹, P² be two [x _i , x _k ]-mPF paths of G, where x _i , x _k  ∈ X (x _i  ≠ x _k ). Then P¹ and P² are called edge-disjoint [x _i , x _k ]-mPF paths if E (P¹)∩ E (P²) = ∅, i.e., P¹ and P² have no common edges. Two edge-disjoint [x _i , x _k ]-mPF paths are called internally disjoint [x _i , x _k ]-mPF paths if V (P¹) ∩ V (P²) = {x _i , x _k }, i.e., P¹ and P² have no common vertices except x _i and x _k .

Remark. Internally disjoint [x _i , x _k ]-mPF paths are always edge-disjoint [x _i , x _k ]-mPF paths but converse needs not be true.

Example 4.6. Consider mPF graph G = (Ψ, Φ) (Fig. 7). P¹ : x₁-x₂-x₃ and P² : x₁-x₄-x₅-x₃ are internally disjoint [x _i , x _k ]-mPF paths. However, P³ : x₁-x₆-x₉-x₃ and P⁴ : x₁-x₆-x₇-x₈-x₉-x₃ are edge-disjoint [x₁, x₃]-mPF paths as V (P³) ∩ V (P⁴) = {x₁, x₆, x₉, x₃} ≠ {x₁, x₃}.

Definition 4.10. Let G = (Ψ, Φ) be an mPF graph and E _S be the set of all strong edges of G. Then strong size of G is denoted by S _S  (G) = (P₁ ∘ S _S  (G) , P₂ ∘ S _S  (G) , …, P _m  ∘ S _S  (G)) and defined as: P _j  ∘ S _S  (G) = ∑_{xy∈E S} P _j  ∘ Φ (xy) for each 1 ≤ j ≤ m.

4.1 Menger’s theorem for mPF graphs

We now present an mPF graph version of one of the famous results in graph theory due to the Karl Menger. For fuzzy version of Menger’s theorem, the readers may read reference [20].

Theorem 4.5 (Vertex version of Menger’s Theorem for an mPF graph G) Let G = (Ψ, Φ) be an mPF graph. For any two vertices x _i , x _k  ∈ X such that x _i x _k  ∈ E is not strong mPF edge, the maximum number of internally disjoint strongest [x _i , x _k ]-mPF paths in G is equal to the number of vertices in a minimal x _i -x _k SRSVs.

Proof. Let G = (Ψ, Φ) be an mPF graph and x _i , x _k  ∈ X be any two vertices such that x _i x _k  ∈ E is not strong mPF edge of G. We have to show that the maximum number of internally disjoint strongest [x _i , x _k ]-mPF paths in G is equal to the number of vertices in a minimal x _i -x _k SRSVs in G. We will prove this result by mathematical induction on the strong size of G, i.e., S _S  (G).

Step i. When S _S  (G) = 0, G = (Ψ, Φ) is such that E _S  =∅ and the result is trivially true for any pair of vertices x _i , x _k  ∈ X.

Step ii. Assume that the statement is true for every mPF graph with S _S  (G) < n (n ≥ 1).

Step iii. Let G be an mPF graph of S _S  (G) = n and x _i , x _k  ∈ X be any two vertices such that x _i x _k is not strong mPF edge of G. The statement is obviously true if vertices x _i and x _k belong to different components of G. So, we suppose that both vertices x _i and x _k belong to different components of G. Then either x _i x _k is not an edge of G, i.e., x _i x _k  ∉ E _S or it is δ-edge. In both situations x _i -x _k SRSVs exists in G. (If x _i x _k is strong mPF edge of G then removal of any number of vertices will not reduce the strength of connectedness between vertices x _i and x _k , thus no x _i -x _k SRSVs exist in G.)

Now, suppose that X G ′ ( x i , x k ) is a minimum x _i -x _k SRSVs in G with | X G ′ ( x i , x k ) | = t ≥ 1 . By Theorem 4.3, every strongest [x _i , x _k ]-mPF path must contain at least one vertex from X G ′ ( x i , x k ) . This implies that each x _i -x _k SRSVs must contain at least as many vertices as the number of internally disjoint strongest [x _i , x _k ]-mPF paths. Here, this shows that there exist at most t internally disjoint strongest [x _i , x _k ]-mPF paths. Thus, we have shown that G contains exactly t internally disjoint strongest [x _i , x _k ]-mPF paths. If t = 1 then | X G ′ ( x i , x k ) | = 1 . Suppose that X G ′ ( x i , x k ) = { x } . Then CONN_G\{x} (x _i , x _k ) < CONN _G  (x _i , x _k ), i.e., x is an mPF cut-vertex of G. Therefore, each strongest [x _i , x _k ]-mPF path must pass through vertex x. Thus, the number of internally disjoint strongest [x _i , x _k ]-mPF paths is one and the result is true. So, assume that t ≥ 2. Then three cases arise:

Case I. G has a minimum x _i -x _k SRSVs containing a vertex x such that x is α-strong neighbor of both vertices x _i and x _k , i.e., x _i x and xx _k both are α-edges.

Case II. For every minimum x _i -x _k SRSVs X G ′ ( x i , x k ) in G, either every vertex in X G ′ ( x i , x k ) is an α-strong neighbor of x _i (that is if x is a vertex in X G ′ ( x i , x k ) then x _i x is an edge which is unique strongest [x _i , x _k ]-mPF path) but not of vertex x _k or every vertex in X G ′ ( x i , x k ) is an α-strong neighbor of x _k but not of vertex x _i .

Case III. There exists an x _i -x _k SRSVs V in G such that no vertex from V is an α-strong neighbor of vertices x _i and x _k and V contains at least one vertex which is not α-strong neighbor of vertex x _i and at least one vertex which is not α-strong neighbor of vertex x _k .

Claim: In all three cases, there exists exactly t internally disjoint strongest [x _i , x _k ]-mPF paths in G.

Let X G ′ ( x i , x k ) be the minimum x _i -x _k SRSVs with the property mentioned in case I. Then X G ′ ( x i , x k ) \ { x } is a minimum x _i -x _k SRSVs in partial mPF subgraph G \ {x} having t-1 vertices. As x _i x and xx _k both are α-edges, they are obviously strong mPF edges and therefore S _S  (G \ {x}) < S _S  (G). By induction, G \ {x} has t-1 internally disjoint strongest [x _i , x _k ]-mPF paths. Also, x _i x and xx _k both are α-edges, P : x _i -x-x _k is a strongest [x _i , x _k ]-mPF path in it.

Let X G ′ ( x i , x k ) be the minimum x _i -x _k SRSVs with the property mentioned in case II. Suppose that each vertex in X G ′ ( x i , x k ) is an α-strong neighbor of vertex x _i but not of vertex x _k . Consider a strongest [x _i , x _k ]-mPF path P in G. Let x be the first vertex of P such that x ∈ X G ′ ( x i , x k ) . Then x _i x is an α-edge and because xx _k is not α-edge, there exists at least one vertex y other than x _i and x _k such that xy is β-edge.

Our claim: We have to show that each x _i -x _k SRSVs in G \ {xy} has exactly t vertices.

We assume on contrary that there exists a minimum x _i -x _k SRSVs (say U = {u₁, u₂, …, u_t-1}) in G \ {xy} with t-1 vertices. Then U ∪ {x} is a minimum x _i -x _k SRSVs in G. Also, note that each vertex in the set U ∪ {x}, i.e., u₁, u₂, …, u_t-1 and x is α-strong neighbor of vertex x _i . As U ∪ {y} is also a minimum x _i -x _k SRSVs in G. It follows that vertex y is an α-strong neighbor of vertex x _i . This contradicts to the fact that xy is β-edge. (x _i x, x _i y and xy form a triangle with xy as weakest mPF edge. The unique weakest mPF edge of an mPF cycle is a δ-edge). Hence, t is the minimum number of vertices in an x _i -x _k SRSVs in G \ {x}. As S _S  (G \ {x}) < S _S  (G). By induction, it follows that G \ {xy} has t internally disjoint strongest [x _i , x _k ]-mPF paths and hence in G.

Let V = {v₁, v₂, …, v _t } be the minimum x _i -x _k SRSVs having t vertices with the property mentioned in case III. Consider each strongest mPF path from vertex x _i to vertex x _k (see in Fig. 8(a)). As V is a minimum x _i -x _k SRSVs this implies that vertices v₁, v₂, …, v _t must belong to at least one such [x _i , x _k ]-mPF path. Let G _{x i} be the mPF subgraph of G containing all [x _i -v _i ]-mPF subpath of each strongest [x _i , x _k ]-mPF path in which v _i  ∈ V is the only vertex of the mPF path belonging to V. Note that if P _j  ∘ CONN _G  (x _i , x _k ) = f _j then P _j  ∘ Φ (xy) ≥ f _j (where for each 1 ≤ j ≤ m, f _j be any real number in [0, 1]) for every edge xy in these mPF paths. Let G x i ′ be the mPF subgraph constructed from G _{x i} by considering a new vertex w and joining w to each vertex v₁, v₂, …, v _t (see in Fig. 8)(b).

OPEN IN VIEWER

Fig. 8

Construction of mPF subgraphs G x i ′ and G x k ′ .

Assume that for each 1 ≤ j ≤ m, P _j  ∘ Ψ (w) =1 and P _j  ∘ Φ (v _i , w) = P _j  ∘ Ψ (v _i ) for all i = 1, 2, …, t. Similarly, mPF subgraphs G _{x k} and G x k ′ (see in Fig. 8(c)) are defined. As V contains a vertex which is not α-strong neighbor of vertex x _i and a vertex which is not α-strong neighbor of vertex x _k . (Note that each newly introduced edge is a strong mPF edge). Here, we have S S ( G x i ′ ) < S S ( G ) . It follows by induction that G x i ′ contains t internally disjoint [x _i , w]-mPF paths say P _{A i} , i = 1, 2, …, t, such as P _{A i} contains v _i . Also, we have S S ( G x k ′ ) < S S ( G ) . It follows by induction that G x k ′ contains t internally disjoint [u, x _k ]-mPF paths say P _{B i} , i = 1, 2, …, t, such as P _{B i} contains v _i . Let P A i ′ be the [x _i , v _i ]-mPF subpaths of P _{A i} and P B i ′ be the [v _i , x _k ]-mPF subpaths of P _{B i} for i = 1, 2, …, t. Now, t internally disjoint strongest [x _i , x _k ]-mPF paths can be formed by joining P _{A i} and P _{B i} , i = 1, 2, …, t. Hence, by induction the theorem is proved. □

Example 4.7. (Illustration of Theorem. 4.5) Suppose different cities of a country are affected by an earthquake. These affected (disaster) areas need essentials like health kits, food, shelter, etc. The other non-affected cities of that country should help those affected areas. Here, we take an example of 8 different cities, including Birmingham, Centerbury, Durham, Gloucester, Lincoin, Northwich, Peterborough and Salisbury of the United Kingdom. Suppose, Lincoin is affected by an earthquake. The other cities are non-effected areas and want to help the people of Lincoin with essential items. We model this problem with the help of 3PF graph in which vertices represent cities (affected and non-affected areas) and edges represent relationships (roads) between two cities. Let X = {Birmingham, Centerbury, Durham, Gloucester, Lincoin, Northwich, Peterborough, Salisbury} be the set of vertices and Ψ be 3PF set on X (given in Table 16).

OPEN IN VIEWER

Table 16

3PF vertex set

Cities	P1 ∘ Ψ	P2 ∘ Ψ	P3 ∘ Ψ
Birmingham	0.5	0.6	0.4
Centerbury	0.4	0.5	0.3
Durham	0.4	0.5	0.3
Gloucester	0.5	0.6	0.4
Lincoin	0.7	0.2	0.9
Norwich	0.3	0.4	0.2
Peterborough	0.8	0.9	0.7
Salisbury	0.5	0.6	0.4

The membership value of each vertex is measured according to three characteristics: {population, city condition, expenses}. The membership value of each edge is measured according to three characteristics: {traffic jam on road, road condition, travel cost}. The membership values of roads are calculated according to the condition: P _j  ∘ Φ (xy) ≤ inf {P _j  ∘ Ψ (x) , P _j  ∘ Ψ (y)} for each 1 ≤ j ≤ m. The correspondent 3PF graph G = (Ψ, Φ) is shown in Fig. 9. Since, Lincoin is the disaster area, it needs help from non-disaster cities through efficient roots. For this purpose, we will find out the strongest mPF paths from non-affected cities to Lincoin. Consider two cities Centerbury and Lincoin (not strong neighbors of each other). The mPF paths from Centerbury to Lincoin with their corresponding strengths are:

P¹: Centerbury - Lincoin, S (P¹) = (0.3, 0.2, 0.1)

P²: Centerbury - Birmingham - Peterborough - Lincoin, S (P²) = (0.2, 0.1, 0.0)

P³: Centerbury - Salisbury - Peterborough - Lincoin, S (P³) = (0.3, 0.2, 0.0)

P⁴: Centerbury - Gloucester - Peterborough - Lincoin, S (P⁴) = (0.4, 0.2, 0.1)

The minimum {Centerbury}-{Lincoin} SRSVs in this network consists of only one vertex, i.e., X′ = {Peterborough}. According to Theorem 4.5 there is only one internally disjoint strongest mPF path from Centerbury to Lincoin, i.e., P⁴ (CONN _G  (Centerbury, Lincoin) = (0.4, 0.2, 0.1) = S (P⁴)). Therefore, Centerbury has to send essentials to Lincoin through strongest mPF path P⁴. Similarly, we can find out strongest mPF paths from other non-affected cities to Lincoin.

OPEN IN VIEWER

Fig. 9

3PF graph

We now discuss the edge version of Menger’s Theorem for mPF graphs.

Theorem 4.6. (Edge version of Menger’s Theorem for an mPF graph G) Let G = (Ψ, Φ) be a connected mPF graph. For any two vertices x _i , x _k  ∈ X, the maximum number of internally disjoint strongest [x _i , x _k ]-mPF paths in G is equal to the number of edges in a minimal x _i -x _k SRSEs.

Proof. Let G = (Ψ, Φ) be an mPF graph and x _i , x _k  ∈ X be any two vertices. We have to show that the maximum number of internally disjoint strongest [x _i , x _k ]-mPF paths in G is equal to the number of edges in a minimal x _i -x _k SRSEs in G. We will prove this result by mathematical induction on the strong size of G, i.e., S _S  (G).

Step i. When S _S  (G) = 0, G = (Ψ, Φ) is such that E _S  =∅ and the result is trivially true for any pair of vertices x _i , x _k  ∈ X.

Step ii. Assume that the statement is true for every mPF graph with S _S  (G) < n (n ≥ 1).

Step iii. Let G be an mPF graph of S _S  (G) = n and x _i , x _k  ∈ X be any two vertices. The statement is obviously true if vertices x _i and x _k belong to different components of G. So, we suppose that both vertices x _i and x _k belong to different components of G. In this situation x _i -x _k SRSEs exists in G.

Now, suppose that E G ′ ( x i , x k ) is a minimum x _i -x _k SRSEs in G with | E G ′ ( x i , x k ) | = t ≥ 1 . By Theorem 4.4, every strongest [x _i , x _k ]-mPF path must contain at least one edge from E G ′ ( x i , x k ) . This implies that each x _i -x _k SRSEs must contain at least as many edges as the number of internally disjoint strongest [x _i , x _k ]-mPF paths. Here, this shows that there exist at most t internally disjoint strongest [x _i , x _k ]-mPF paths. Thus, we have shown that G contains exactly t internally disjoint strongest [x _i , x _k ]-mPF paths. If t = 1 then | E G ′ ( x i , x k ) | = 1 . Suppose that E G ′ ( x i , x k ) = { xy } . Then CONN_G\{xy} (x _i , x _k ) < CONN _G  (x _i , x _k ), i.e., xy is an mPF bridge of G. Therefore, each strongest [x _i , x _k ]-mPF path must pass through edge xy. Thus, the number of internally disjoint strongest [x _i , x _k ]-mPF paths is one and the result is true. So, assume that t ≥ 2. Then three cases arise:

Case I. G has a minimum x _i -x _k SRSEs containing an α-edge xy such that x is α-strong neighbor of vertex x _i and y is α-strong neighbor of x _k , i.e., x _i x and yx _k both are α-edges.

Case II. For every minimum x _i -x _k SRSEs E G ′ ( x i , x k ) in G, either every edge in E G ′ ( x i , x k ) has an end vertex which is an α-strong neighbor of x _i but not of vertex x _k or every edge in E G ′ ( x i , x k ) has an end vertex which is an α-strong neighbor of x _k but not of vertex x _i .

Case III. There exists an x _i -x _k SRSEs F in G such that no edge from F has an end vertex which is an α-strong neighbor of vertices x _i and x _k and F contains at least one edge whose both end vertices are not α-strong neighbors of vertex x _i and at least one edge whose both end vertices are not α-strong neighbors of vertex x _k .

Claim: In all three cases, there exists exactly t internally disjoint strongest [x _i , x _k ]-mPF paths in G.

Let E G ′ ( x i , x k ) be the minimum x _i -x _k SRSEs with the property mentioned in case I. Then E G ′ ( x i , x k ) \ { xy } is a minimum x _i -x _k SRSEs in partial mPF subgraph G \ {xy} having t-1 vertices. As x _i x and yx _k both are α-edges, they are obviously strong mPF edges and therefore S _S  (G \ {xy}) < S _S  (G). By induction, G \ {xy} has t-1 internally disjoint strongest [x _i , x _k ]-mPF paths. Also, x _i x, xy, and xx _k all are α-edges, P : x _i -x-y-x _k is a strongest [x _i , x _k ]-mPF path in it.

Let E G ′ ( x i , x k ) be the minimum x _i -x _k SRSEs with the property mentioned in case II. Suppose that each edge in E G ′ ( x i , x k ) has an end vertex which is α-strong neighbor of vertex x _i but not of vertex x _k . Consider a strongest [x _i , x _k ]-mPF path P in G. Let xy be the first edge of P such that xy ∈ E G ′ ( x i , x k ) . Then x _i x is an α-edge and because xx _k is not α-edge, there exists at least one vertex z other than x _i and x _k such that xz is β-edge.

Our claim: We have to show that each x _i -x _k SRSEs in G \ {xy} has exactly t edges.

We assume on contrary that there exists a minimum x _i -x _k SRSEs (say H = {e₁, e₂, …, e_t-1}) in G \ {xy} with t-1 edges. Then H ∪ {xy} is a minimum x _i -x _k SRSEs in G. Also, note that each edge in the set H ∪ {xy}, i.e., e₁, e₂, …, e_t-1 and xy is incident with vertex x _i such that x is α-strong neighbor of vertex x _i . As H ∪ {xz} is also a minimum x _i -x _k SRSEs in G. It follows that vertex yz is incident with vertex x _i such that z is an α-strong neighbor of vertex x _i . This contradicts to the fact that xz is β-edge. Hence, t is the minimum number of edges in an x _i -x _k SRSEs in G \ {xy}. As S _S  (G \ {xy}) < S _S  (G). By induction, it follows that G \ {xy} has t internally disjoint strongest [x _i , x _k ]-mPF paths and hence in G.

Let F = {f₀ = v₀v₁, f₁ = v₁v₂, …, f_t-1 = v_t-1v _t } be the minimum x _i -x _k SRSEs having t edges with the property mentioned in case III. Consider each strongest mPF path from vertex x _i to vertex x _k (see in Fig. 8(a)). As F is a minimum x _i -x _k SRSEs this implies that edges f₀, f₁, …, f_t-1 must belong to at least one such [x _i , x _k ]-mPF path. Let G _{x i} be the mPF subgraph of G containing all [x _i -v _i ]-mPF subpath of each strongest [x _i , x _k ]-mPF path in which f _i  ∈ F is the only edge of the mPF path belonging to F with one of its end vertex v _i . Note that if P _j  ∘ CONN _G  (x _i , x _k ) = q _j then P _j  ∘ Φ (xy) ≥ q _j (where for each 1 ≤ j ≤ m, q _j be any real number in [0, 1]) for every edge xy in these mPF paths. Let G x i ′ be the mPF subgraph constructed from G _{x i} by considering a new vertex z and joining z to each end vertices v₁, v₂, …, v _t of edges f₀, f₁, …, f_t-1(see in Fig. 8)(b).

Assume that for each 1 ≤ j ≤ m, P _j  ∘ Ψ (z) =1 and P _j  ∘ Φ (v _i , z) = P _j  ∘ Ψ (v _i ) for all i = 1, 2, …, t. Similarly, mPF subgraphs G _{x k} and G x k ′ (see in Fig. 8(c)) are defined. As F contains an edge whose both end vertices are not α-strong neighbors of vertex x _i and an edge whose both end vertices are not α-strong neighbors of vertex x _k . (Note that each newly introduced edge is a strong mPF edge). Here, we have S S ( G x i ′ ) < S S ( G ) . It follows by induction that G x i ′ contains t internally disjoint [x _i , z]-mPF paths say P _{A i} , i = 1, 2, …, t, such as P _{A i} contains v _i . Also, we have S S ( G x k ′ ) < S S ( G ) . It follows by induction that G x k ′ contains t internally disjoint [u, x _k ]-mPF paths say P _{B i} , i = 1, 2, …, t, such as P _{B i} contains v _i . Let P A i ′ be the [x _i , v _i ]-mPF subpaths of P _{A i} and P B i ′ be the [v _i , x _k ]-mPF subpaths of P _{B i} for i = 1, 2, …, t. Now, t internally disjoint strongest [x _i , x _k ]-mPF paths can be formed by joining P _{A i} and P _{B i} , i = 1, 2, …, t. Hence, by induction the theorem is proved. □

Example 4.8. For illustration of Theorem. 4.6, consider 3PF graph G = (Ψ, Φ) as shown in Fig. 9 of Example 4.7. Consider two cities Centerbury and Lincoin. The mPF paths from Centerbury to Lincoin with their corresponding strengths are already mentioned in Example 4.7. The minimum Centerbury-Lincoin SRSEs in this network consists of only one edge, i.e., E′ consists of edge between Gloucester and Peterborough. According to Theorem 4.8 there is only one internally disjoint strongest mPF path from Centerbury to Lincoin.

Theorem 4.5 only able to provide maximum number of internally disjoint strongest [x _i , x _k ]-mPF paths in G if x _i and x _k both are not strong mPF neighbors of each other, i.e., x _i x _k is not strong mPF edge. If x _i and x _k both are strong mPF neighbors of each other then Theorem 4.5 can not be applied. However, Theorem 4.6 provides the maximum number of internally disjoint strongest [x _i , x _k ]-mPF paths in G no matter x _i and x _k both are strong mPF neighbors of each other or not. For illustration, consider two cities Peterborough and Lincoin in Example 4.7. Peterborough and Lincoin are strong mPF neighbors of each other. The minimum Peterborough-Lincoin SRSVs consists of no vertex. So, we are not able to apply Theorem 4.5 here to find out maximum number of internally disjoint strongest [Peterborough, Lincoin]-mPF paths. However, minimum Peterborough-Lincoin SRSEs consists of one edge, i.e., edge between Peterborough and Lincoin. Therefore, we can apply Theorem 4.6 here to find out maximum number of internally disjoint strongest [Peterborough, Lincoin]-mPF paths.