On strong extremal problems in fuzzy graphs

1 Introduction and preliminaries

Graphs and hyper graphs have been applied in a large number of problems including cancer detection, robotics, human cardiac functions, networking and designing [12, 19]. It was Lotfi A. Zadeh [25, 26] who introduced fuzzy sets and fuzzy logic into Mathematics to deal with problems of uncertainty. As most of the phenomenon around us involve ambiguity and vagueness, fuzzy logic and fuzzy mathematics have to play a crucial role in modelling real time systems with some level of uncertainty.

Rosenfeld [15] introduced fuzzy graphs 10 years after Zadeh’s classic ‘fuzzy sets’ [25]. Rosenfeld applied fuzzy graph techniques to clustering problems and information networks. Fuzzy graphs are used to represent relationships involving uncertainty. One of the real life application can be seen in [1].

Yeh and Bang [1] also introduced fuzzy graphs independently. Since their work, connectivity has become one of the main themes of fuzzy graph theory as it differs greatly from classical graphs. Mordeson and Nair [12], Bhutani and Rosenfeld [2–5] Vijayakumar and Sunitha [20–23] are among the other main contributorsof connectivity problems in fuzzy graphs. In 2009, Mathew and Sunitha [18, 19] introduced the concepts of fuzzy arc cuts and fuzzy node cuts to generalize cuts in graphs as sets of arcs and nodes, respectively, whose removal from the fuzzy graph reduces the strength of connectedness between some pairs of nodes but need not disconnect the fuzzy graph. They also studied different types of arcs in fuzzy graph structures and generalized Whitney’s theorem related to node connectivity, arc connectivity, and the minimum degree of a fuzzy graph.

A fuzzy graph (f-graph for short) [15] is a pair G : (σ, μ) where σ is a fuzzy subset of a set S and μ is a fuzzy relation on σ. We assume that S is finite and nonempty, μ is reflexive and symmetric. In all the examples σ is chosen suitably. Also, we denote the underlying crisp graph by G^* : (σ^*, μ^*) where σ^* = {u εS : σ (u) >0} and μ^* = {(u, v)  εSXS : μ (u, v) >0}. A fuzzy graph H : (τ, ν) is called a partial fuzzy subgraph of G : (σ, μ) if τ (u) ≤ σ (u) for every u and ν (u, v) ≤ μ (u, v) for every pair of nodes u and v. In particular we call H : (τ, ν) a fuzzy subgraph of G^* : (σ^*, μ^*) if τ (u) = σ (u) for every u ετ^* and ν (u, v) = μ (u, v) for every (u, v)  εν^*. A pathP of length n is a sequence of distinct nodes u₀, u₁, . . . . . . . u _n such that μ (u_i-1, u _i ) >0, i = 1, 2, . . . . . . , n and the degree of membership of a weakest arc is defined as its strength. The strength of connectedness between two nodes x and y is defined as the maximum of the strengths of all paths between x and y and is denoted by CONN _G  (x, y). An x - y path P is called a strongest x - y path if its strength equals CONN _G  (x, y) [18]. An f-graph G : (σ, μ) is connected if for every x, y in σ^*, CONN _G  (x, y) >0. Through out, we assume that G is connected. An arc (x, y) of anf-graph is called strong if its weight is at least as great as the connectedness of its end nodes x and y in the edge deleted fuzzy subgraph G - (x, y) and an x - y path P is called a strong path if P contains only strongarcs [5].

An arc in a fuzzy graph G is called a fuzzy bridge(f-bridge for short) of G if its removal reduces the strength of connectedness between some pair of nodes in G [18]. Similarly a fuzzy cut node (f-cut node for short)w is a node in G whose removal from G reduces the strength of connectedness between some pair of nodes other than w. A fuzzy graph having no fuzzy cut nodes is called a fuzzy block [18]. More related works can be seen in [1, 15, 16]. Themax-max composition of a square matrix with itself is again a square matrix of the same order whose (i, j) th entry is given by d_i,j = max {max(d_i1, d_1,j) , max(d_i2, d_2j) , . . . , max(d _in , d _nj )} [12].

The distance and related concepts which are mentioned in this article have got many applications in power system analysis. One such application is included at the end of the article.

2 α, β and strong distances in fuzzy graphs

In this section, we give the definitions of strong distance in fuzzy graphs along with examples.

Definition 2.1. Let: (σ, μ) be a fuzzy graph. Let u and v be any two nodes of G. Then the strongdistance between u and v is defined and denoted by d _s  (u, v) = min ∑_e∈Pμ (e) where P is a strong path between u and v, 0 if u = v, ∞ if there exists no strong u - v path.

Clearly d _s satisfies all the axioms of a metric.

1. d _s  (u, v) ≥0 for all u and v.

Remark 2.1. If we restrict the strong arcs in the Definition 2.1, into α- strong arcs only or β- strong arcs only, we get the α- distance and β- distance between the nodes u and v respectively. They are denoted by d _α and d _β respectively.

In the following example (Fig. 1), we find that the three distances are different.

Example 2.1.

The α, β and strong distances between different pair of nodes are given below.

d _α (a, b) =0.7, d _α (a, c) =1.5, d _α (a, d) =∞, d _α (b, c) =0.8, d _α (b, d) =∞, d _α (c, d) =∞, d _β (a, b) =∞, d _β (a, c) =0.4, d _β (a, d) =0.2, d _β (b, c) =∞, d _β (b, d) =∞, d _β (c, d) =0.2. d _s  (a, b) =0.7, d _s  (a, c) =0.4, d _s  (a, d) =0.2, d _s  (b, c) =0.8, d _s  (b, d) =0.9, d _s  (c, d) =0.2.

3 Strong center of a fuzzy graph

In this section, we introduce the concept of center with respect to the distances which are defined in the previous section. First we give the definitions of strong eccentricity of a node and strong radius of the fuzzy graph analogous to the classical definitions. The concepts of strong isolated nodes and arcs are also defined.

Definition 3.1. The α - eccentricity of a node u in σ^* is defined and denoted by e _α (u) = max {d _α (u, v)/v ∈ σ^*, 0 ≤ d _α (u, v) < ∞}. Similarly the β - eccentricity and strongeccentricity are defined as e _β (u) = max {d _β (u, v)/v ∈ σ^*, 0 ≤ d _β (u, v) < ∞} and e _s  (u) = max {d _s  (u, v)/v ∈ σ^*, 0 ≤ d _s  (u, v) < ∞} respectively.

Definition 3.2. A node v is called an α - eccentricnode of u if e _α (u) = d _α (u, v). Set of all α - eccentric nodes of u is denoted by u α *.

In a similar manner we can define β - eccentricnodes and strongeccentricnodes.

Definition 3.3. Among the α - eccentricity of all the nodes in a graph, the minimum is called the α - radius of G. It is denoted by r _α (G). That is r _α (G) = min {e _α (u)/u ∈ σ^*}.

Also the β - radius of G, denoted and defined by r _β (G) = min {e _β (u)/u ∈ V} and the strongradius of G is denoted and defined by r _s  (G) = min {e _s  (u)/u ∈ σ^*}.

As the radius is the minimum eccentricity, the maximum eccentricity is called the diameter of the graph.

Definition 3.4. Among the α - eccentricity of all the nodes of a graph, the maximum is called the α - diameter of G. it is denoted by d _α (G).

That is d _α (G) = max {e _α (u)/u ∈ σ^*}.

Also the β - diameter and the strongdiameter of G are denoted and defined by d _β (G) = max {e _β (u)/u ∈ σ^*} and d _s  (G) = max {e _s  (u)/u ∈ σ^*} respectively.

Definition 3.5. A node u is called α - central if e _α (u) = r _α (G), and called β - central if e _β (u) = r _β (G) and strongcentral if e _s  (u) = r _s  (G).

Definition 3.6. A node u is called α - diametral if e _α (u) = d _α (G), and called β - diametral if e _β (u) = d _β (G) and strongdiametral if e _s  (u) = d _s  (G).

Definition 3.7. The subgraph induced by the set of all α - central nodes is called the α - cetre of G. It is denoted by <C _α (G)>. Analogously the β - center of G is the subgraph induced by the set of all β - central nodes of G, denoted by <C _β (G)>. Also the strongcenter of G is denoted by <C _s  (G)> and is defined as the subgraph induced by the set of all strong central nodes.

Using the fuzzy graph shown in example 2.1, we illustrate all the above definitions.

e _α (a) =1.5, e _α (b) =0.8, e _α (c) =1.5, e _α (d) =∞, e _β (a) =0.4, e _β (b) =∞, e _β (c) =0.4, e _β (d) =0.2, e _s  (a) =0.7, e _s  (b) =0.9, e _s  (c) =0.8, e _s  (d) =0.9, r _α (G) =0.8, r _β (G) =0.2, r _s  (G) =0.7, d _α (G) =1.5, d _β (G) =0.4, d _s  (G) =0.9.

b is an α- central node, d is a β- central node and a is a strong central node.

a and c are α- diametral nodes, a and c are β- diametral nodes, and b and d are strong diametral nodes.

If we take the diametral nodes instead of central nodes we get the periphery of the fuzzy graph G.

Definition 3.8. The subgraph induced by the set of all α - diametral nodes is called the α - periphery of G. It is denoted by <P _α (G)>. Analogously the β - periphery of G is the subgraph induced by the set of all β - diametral nodes of G, denoted by <P _β (G)>. Also the strongperiphery of G is denoted by <P _s  (G)> and is defined as the subgraph induced by the set of all strong diametral nodes.

Definition 3.9. A node u ∈ σ^* is called α - isolated if there is no α- strong arc incident on u, β - isolated if there is no β- strong arc incident on u and strongisolated if there is no strong arc incident on u.

Definition 3.10. An α- strong arc e = (u, v) is called α - isolated, if there exists no other α- strong arcs which is adjacent with e. Similarly a β- strong arc e = (u, v) is called β - isolated, if there exists no other β strong arcs which is adjacent with e, and a strong arc e = (u, v) is called strongisolated, if there exists no other strong arcs which is adjacent with e.

From the last two definitions, We have the following preposition.

Preposition 3.11.Let G : (σ, μ) be a fuzzy graph. If e = (u, v) is an α- isolated arc of G, then e _α (u) - e _α (v) =0}.

Proof. Since e = (u, v) is α- isolated, e is adjacent with no α- strong arcs. That means e is the only α- strong arc, which is incident on u and v. While calculating the α- eccentricity of u, the farthest node from u is v and vice - versa. Thus e _α (u) = e _α (v) = w (e) and hence e _α (u) - e _α (v) =0. This completes the proof.

It can easily be seen that, the above preposition is valid for both β- isolated and strong- isolated arcs.

Preposition 3.2. Let G : (σ, μ) be a connected fuzzy graph. Then for every e ∈ μ^*, if μ (e) = k < 1, then e _s  (u) < e (u) for every node u in σ^*, where e (u) is the eccentricity of u in G^* .

Proof. Let G : (σ, μ) be a connected fuzzy graph such that μ (e) = k ≤ 1 for all arcs e ∈ μ^*. Let u be any node in σ^*. Let v be the farthest node of u in the underlying graph G^*. We know that, between any pair of nodes u and v of G, there exists a strong path. Now e (u) is the number of arcs in the shortest path connecting u and v in the underlying graph G^*. But e _s  (u) is the sum of the weights of all arcs in the shortest strong path connecting u and v in G. Since for every edge e, μ (e) <1, it is Clear that e _s  (u) < e (u).

The above preposition is trivial and valid for both α and β distances. As in the classical concept of distance, we have, the following inequalities.

Theorem 3.1.LetG : (σ, μ) be a connected fuzzy graph, then r α ( G ) ≤ d α ( G ) ≤ 2 r α ( G ) . r β ( G ) ≤ d β ( G ) ≤ 2 r β ( G ) . r s ( G ) ≤ d s ( G ) ≤ 2 r s ( G ) .

Proof. We prove the theorem for only strong radius and diameter. The other proofs are similar.

The first inequality follows from the definition itself. To prove the other, let u and v be any two nodes such that d _s  (u, v) = d _S  (G) . Let w be any strong central node of G. Then by triangle inequality, d _s  (u, v) ≤ d _s  (u, w) + d _s  (w, v) . But d _s  (u, w) ≤ r _s  (G) and d _s  (w, v) ≤ r _s  (G).

Thus by triangle inequality for strong distance, we have, d _s  (u, v) ≤ r _s  (G) + r _s  (G) =2r _s  (G) . □

4 Self centered fuzzy graphs

In this section, we present the concept of self centered fuzzy graphs with respect to the distances which are introduced in Section 2. Self centered graphs have got many practical applications. Here we present some necessary conditions and a characterization of self centered fuzzy graphs. Throughout this section, we assume that G : (σ, μ) is a connected fuzzy graph.

Definition 4.1. A fuzzy graph G is called α - selfcentered if G is isomorphic with its α - center and β - selfcentered if G is isomorphic with its β - center. Also G is called strongselfcentered if G is isomorphic with its strongcenter.

The following theorem is true for both β and strong self centered graphs.

Theorem 4.1. Let G : (σ, μ) be a connected fuzzy graph such that there exists exactly one α- strong arc incident on every node and that all the α- strong arcs are of equal weight, then G is α- self centered.

Proof. Given that all nodes of G are incident with exactly one α- strong arc, and all the α- strong arcs are of equal weight. This means if e = (u, v) is α- strong, then there will be no other α- strong arcs incident on u and v. Hence e _α (u) = μ (e) = e _α (v). By similar arguments, we get this equality for any other α- strong arc. Thus e _α (u) = μ (e) for every node u in σ^*. This proves that G is α- self centered. □

The next theorem is a characterization for α- self centered fuzzy graphs.

Theorem 4.2. A connected fuzzy graph G : (σ, μ) is α- self centered if for any two nodes u and v such that u is an α- eccentric node of v, v should be one of the α- eccentric nodes of u.

Proof. First assume that G is α- self centered. Also assume that u is an α- eccentric node of v. That is e _α (v) = d _α (v, u). Since G is α- self centered, all nodes will be having the same α- eccentricity. Therefore e _α (v) = e _α (u). From the above two equations we get, e _α (u) = d _α (v, u) = d _α (u, v). Thus e _α (u) = d _α (u, v). That is v is an α- eccentric node of u. Next assume that if u is an α- eccentric node of v, then v is an α- eccentric node of u. Thus e _α (u) = d _α (u, v), and e _α (v) = d _α (v, u). But d _α (u, v) = d _α (v, u). Therefore e _α (v) = e _α (u), where u and v are two arbitrary nodes of G. Thus all nodes of G have the same α- eccentricity, and hence G is α- self centered. □

In the same manner, we can prove this result for β and strong self centered graphs.

5 The distance matrix and the max-max composition

In this section, we present an easy check for a fuzzy graph G to find whether it is α- self centered or not. It can be applied for both β and strong self centered graphs.

Definition 5.1. Let G : (σ, μ) be a connected fuzzy graph with ∣σ^* ∣ = n. The α- distance matrix D _α = (d_i,j) is a square matrix of order n and is defined by (d_i,j) = d _α (v _i , v _j ). Note that the α- distance matrix is a symmetric matrix.

Analogously, we can define the β and strong distance matrices. In the following example (Fig. 2), we give the three distances matrices.

Example 5.1.

The α, β and strong distance matrices are given below. D α = ( 0 . 8 ∞ 1.5 . 8 0 ∞ . 7 ∞ ∞ 0 ∞ 1.5 . 7 ∞ 0 ) , D β = ( 0 ∞ ∞ ∞ ∞ 0 . 3 . 6 ∞ . 3 0 . 3 ∞ . 6 . 3 0 ) . D s = ( 0 . 8 1.1 1.4 . 8 0 . 3 . 6 1.1 . 3 0 . 3 1.4 . 6 . 3 0 ) .

Next, we have a theorem regarding the eccentricities of nodes using the max-max composition of the distance matrices.

Theorem 5.1. Let G : (σ, μ) be a connected fuzzy graph. The diagonal elements of the max-max composition of the α- distance matrix of G with itself are the α- eccentricities of the nodes.

Proof. Let D _α = (d_i,j) be the α- distance matrix of G.

Then (d_i,j) = d _α (v _i , v _j ). In the max-max composition, D _αoD _α, the ith diagonal entry, d_i,i = max {max(d_i,1, d_1,i) ,   max(d_i,2, d_2,i) ,   max(d_i,3, d_3,i) , . . . , max(d_i,n, d_n,i)} = max {d_i,1, d_i,2, d_i,3, . . . , d_i,n} = max {d _α (v _i , v₁) , d _α (v _i , v₂) , d _α (v _i , v₃) , . . . , d _α (v _i , v _n )} = e _α (v _i ). This completes the proof of the theorem. □

Theorem 5.2. A connected fuzzy graph G : (σ, μ) is α- self centered if and only if all the entries in the principal diagonal of the max-max composition of the α- distance matrix with itself are the same.

Proof. As proved in theorem 5.1, the principal diagonal entries in the max - max composition of the α- distance matrix with itself are the α- eccentricities of the nodes. If they are same, this means e _α (u) is the same for all u in G. Then G is α- self centered. Hence the proof is completed. □

We illustrate the above theorem in the following examples.

Example 5.2. Consider the fuzzy graph in Fig. 3.

The α distance matrix and the max-max composition are given below.

D α = ( 0 ∞ ∞ . 5 ∞ 0 . 5 ∞ ∞ . 5 0 ∞ . 5 ∞ ∞ 0 ) , D α oD α = ( . 5 ∞ ∞ . 5 ∞ . 5 . 5 ∞ ∞ . 5 . 5 ∞ . 5 ∞ ∞ . 5 )

The graph is α self centered.

Example 5.3. Consider the fuzzy graph shown in Fig. 4.

The α- distance matrix and the max-max composition are given below.

D α = ( 0 ∞ ∞ ∞ 0 . 2 ∞ . 2 0 ) , D α oD α = ( ∞ ∞ ∞ ∞ . 2 . 2 ∞ . 2 . 2 )

Clearly, all diagonal elements in the composition are not same, and hence the graph is not α- self centered.

Remark 5.1. From the above two examples it is clear that, a fuzzy block may or may not be α- self centered.

6 The center of fuzzy trees and fuzzy blocks

In this section, we discuss about the central nodes of fuzzy trees and blocks. In the following theorem, α- central nodes of fuzzy trees are characterized.

Theorem 6.1. If a node in a fuzzy tree is α- central, then it is a common node of at least two α- strong arcs.

Proof. Let G : (σ, μ) be a fuzzy tree. Then G has no β-strong arcs. We know that between any two nodes of a connected fuzzy graph G, there exists a strong path. As G is independent of β- strong arcs, there exists an α- strong path between any two nodes of G. Let u be an α- central node of G. We want to prove that two or more α- strong arcs are incident on u. If possible suppose the contrary. Let there be exactly one α- strong arc, namely e incident on u. Therefore any α-strong path between u and any other node of G will contain the arc e. This proves that e _α (u) > r _α (G), which is a contradiction to the fact that u is α- central. Therefore our assumption is wrong. Thus the proof of the theorem is completed.

□

Remark 6.1. If u is a common node of at least two α-strong arcs, then u is a fuzzy cut node of G. So from the above theorem it is clear that, if a node u of a fuzzy tree G is α- central, then it is a fuzzy cut node of G.

Remark 6.2. As fuzzy trees are free from β- strong arcs, e _β (u) =0 for every node u. Hence the equality e _s  (u) = e _β (u) + e _β (u) is trivially true in all fuzzy trees.

The next theorem is about the α- center of blocks.

Theorem 6.2.The α- center of a block G contains all α- strong arcs with minimum weight.

Proof. Suppose that G : (σ, μ) is a block. Therefore G has no fuzzy cut nodes. We know that, if a node u in a connected fuzzy graph is common to more than one α- strong arcs, then it is a fuzzy cut node. As G is free from fuzzy cut nodes, at most one α- strong arc can be incident on every node of G. Thus the α- eccentricity, e _α of a node u is the weight of the α- strong arc incident on u.

So the α- radius of G, that is r _α (G) is the weight of the smallest α- strong arc. Hence the α- center of G, <C _α (G)> contains all α- strong arcs of G with minimum weight. This completes the proof of the theorem.

The next theorem helps us to find the number of connected components in the α- center of a block. □

Theorem 6.3. Let G : (σ, μ) be a block. If there exists a path containing all α- strong arcs of G with minimum weight alternatively, then <C _α (G)> is connected.

Proof. By the previous theorem, <C _α (G)> consists of all α- strong arcs of G with minimum weight. Also in a block, not more than one α- strong arc can be incident on any node. So if there are k number of α- strong arcs present in G with minimum weight, all these arcs will be in <C _α (G)>. Moreover they are not adjacent also. Hence if we can find a path containing all α- strong arcs with minimum weight alternatively. Thus it follows that <C _α (G)> is connected. Thus the proof iscompleted. □

Theorem 6.4. If a connected fuzzy graph G : (σ, μ) is a block with k number of α- strong arcs. Then k ≤ (∣ σ^* ∣)/2.

Proof.  Suppose that G : (σ, μ) is a block. Then G has no fuzzy cut nodes. Let k be the number of α- strong arcs in G. We have to prove that k ≤ (∣ σ^* ∣)/2. If possible suppose the contrary. Let k > (∣ σ^* ∣)/2. Then there will be at least ⌊k - (|σ^*)/2⌋ number of nodes with more than one α- strong arcs incident on them. Clearly these nodes are fuzzy cut nodes of G, a contradiction to the fact that G is free from fuzzy cut nodes. So our assumption is wrong. This proves the theorem. □

7 Application

Voltage collapses usually occur in power systems, which are heavily loaded or faulted or have shortage of reactive power. Voltage collapse is a system instability involving many power system components. In fact, a voltage collapse may involve an entire power system. Voltage collapse is typically associated with reactive power demand of load not being met due to shortage in reactive power production and transmission. Voltage collapse is a manifestation of voltage instability in the system. A system is said to be in voltage stable state if at a given operating condition, for every bus in the system, the bus voltage magnitude increases as the reactive power injection at the same bus is increased. A system is voltage unstable if for at least one bus in the system, the bus voltage magnitude decreases as the reactive power injection at the same bus is increased.

The term voltage collapse is also often used for voltage instability conditions. It is the process, by which, the sequence of events following voltage instability leads to abnormally low voltages or even a black out in a large part of the system.

For maintaining voltage stability in the whole power system, it is vital to find voltage weak buses and initiate reactive power injection so as to elevate its voltage to rated value. Earlier methods used iterative algorithms such as Gauss Siedel, Newton Raphson and Decoupled load flow methods to find voltage weak buses. But these iterative based algorithms are tedious when applying on real time power systems consisting not more than a thousand buses. A slightest delay in reactive power injection on voltage weak buses may lead to voltage collapse in the entire power system network. Here comes the importance of fuzzy graph theory based methods to find voltage weak buses. Since the methods uses only addition and subtraction, the method can generate result at faster rate compared to its predecessors. The method is not presented here. It will be published in the forthcoming papers.

8 Conclusion and future works

In this article, three new distances in fuzzy graphs are introduced. As reduction in strength between two nodes is more important than total disconnection of the graph, the authors made use of the connectivity concepts in defining the distances. A special focus on fuzzy self centered graphs can be seen as they are applied widely. The max - max composition, which is presented in Section 5 is very useful in characterizing the three types of self centered graphs. Studies and characterizations for both fuzzy trees and blocks are also made.

As there exists at least one strong path between any given pair of nodes of a fuzzy graph, the strong distance between any two nodes will be finite. Thus the strong distance matrix of any fuzzy graph contains only finite elements. Hence further studies can focussed on strong spectrum of fuzzy graphs. Other than the adjacency matrix, if we use the strong distance matrix in graph signal processing, we can indicate the signal strength variation in a better way. This shows the relevance of the work presented in this article.