
Graph theory has vast applications in data mining, image segmentation, clustering, image capturing, networking, communication, planning, scheduling, etc. Similarly, modeling of network topologies can be done using the concept of a graph. In addition, paths, walks, and circuits are used to solve many problems, such as the traveling salesman problem, database design, and resource networking. These lead to the development of new algorithms and new theories that can be used in various applications.
Recently, graph theory has been used to represent all types of real system. However, science and technology are characterized by complex processes and phenomena for which complete information is not always available for any system. For such cases, mathematical models have been developed to handle various types of system containing elements of uncertainty. A large number of these models are based on fuzzy sets, which are an extension of the ordinary set theory. In many cases, some aspects of a graph-theoretic problem may be uncertain. In 1975, Zadeh [1] introduced the notion of interval-valued fuzzy sets as an extension of fuzzy sets in which the values of the membership degrees are interval numbers instead of the single point. Rosenfeld [1] introduced the notation of fuzzy graphs in 1975, introducing the concept of μ-distance in fuzzy graphs. Based on this μ-distance, Bhattacharya [3] introduced the concepts of eccentricity and center in fuzzy graphs, and the properties of this metric were further studied by Sunitha and Vijayakumar [4]. Samanta and Pal [5] introduced different types of fuzzy graph, such as fuzzy tolerance graphs, fuzzy threshold graphs [6], fuzzy planar graphs [7], and fuzzy competition graphs [
In 2011, Akram and Dudec [20] defined the interval-valued fuzzy graph (IVFG) and described operations on it. Rashmanlou and Pal [21] defined the μ-length, ν-length, and μν-length between two vertices in an IVFG. They also described the μ-distance, ν-distance, and μν-distance between two vertices in an IVFG. Further information on IVFGs can be found in previous works [22, 23]. However, these distances do not satisfy the metric properties. Also, these distances are intervals. Therefore, one cannot measure the proper distances between two vertices. Some related research can be found elsewhere [24–27].
In this report, the sum distance between vertices of IVFGs is introduced. This definition satisfies the metric properties. In addition, different properties related to the definitions are established. The eccentricity, radius, and diameter are defined based on the sum distance. In addition, the sum distance between vertices of an interval-valued complete fuzzy graph is deduced.
A graph G = (V, E) is finite if V and E are finite sets. An infinite graph is one with an infinite set of vertices, edges, or both. Most commonly in graph theory, it is implied that the graphs discussed are finite (Table 1).
A fuzzy set [1] A on a universal set X is characterized by a mapping m : X → [0, 1], which is called the membership function. A fuzzy set is denoted by A = (X, m).
A fuzzy graph [2] G = (V, σ, μ) is a nonempty set V together with a pair of functions σ : V → [0, 1] and μ : V × V → [0, 1], such that, for all x, y ∈ V, μ(x, y) ≤ min{σ(x), σ(y)}, where σ(x) and μ(x, y) represent the membership values of the vertex x and of the edge (x, y) in G, respectively. A loop at a vertex x in a fuzzy graph is represented by μ(x, x)/ = 0. An edge is nontrivial if μ(x, y)/ = 0.
An IVFG [20] is a pair G = (A, B), where A = (V, [σ−, σ+]) is an interval-valued fuzzy set on V, and B = (V × V, [μ−, μ+]) is an interval-valued fuzzy set on V × V, such that μ−(x, y) ≤ min{σ−(x), σ−(y)} and μ+(x, y) ≤ min{σ+(x), σ+(y)} for all (x, y) ∈ E. Here, A is the interval-valued fuzzy vertex set of G, and B is the interval-valued fuzzy edge set of ξ.
An IVFG G = (A, B) is a complete interval-valued fuzzy graph [22] if μ−(x, y) = min{σ−(x), σ−(y)} and μ+(x, y) = min{σ+(x), σ+(y)}, for all x, y ∈ V. An IVFG is bipartite if the vertex set V can be partitioned into two independent sets V1 and V2 such that μ+(v1, v2) > 0 if v1 ∈ V1 (or V2) and v2 ∈ V2 (or V1). An IVFG G is connected if any two vertices are joined by a path. Let G be a connected IVFG. The μ+ length of a path P : v1 − v2 − ⋯ − vn is defined as
Let G be a connected IVFG. The μ+-distance δ+(vi, vj) is the smallest μ+-length of any vi − vj path P in G, where vi, vj ∈ V — that is, δ+(vi, vj) = min Lμ+(P). The μ−-distance δ−(vi, vj) is the largest μ−-length of any vi − vj path P in G, where vi, vj ∈ V — that is, δ−(vi, vj) = max Lμ−(P). Thus, the distance δ(vi, vj)=[δ−(vi, vj), δ+(vi, vj)] = [max Lμ−(P), min Lμ+(P)].
Let G be a connected IVFG. The μ+-eccentricity of a vertex vi is eμ+(vi) = max{δ(vi, v) | v ∈ V, v vi}. The μ−-eccentricity of vertex vi is eμ−(vi) = max{δ−(vi, v) | v ∈ V, v/ = vi}. Thus, the eccentricity of a vertex vi is [eμ−(vi), eμ+(vi)].
Let G be a connected IVFG. The μ+-radius of G is rμ+(G) = min{eμ+(vi) | vi ∈ V }. The μ−-radius of G is rμ−(G) = min{eμ−(vi) | vi ∈ V}. Thus, the radius of G is [rμ−(G), rμ+(G)].
Let G be a connected IVFG. The μ+-diameter of G is dμ+(G) = max{eμ+(vi) | vi ∈ V }. The μ−-diameter of G is dμ−(G) = max{eμ−(vi) | vi ∈ V}. Thus, the diameter of G is [dμ−(G), dμ+(G)].
The independent strength [12] of an edge (a, b) in an IVFG is defined by an interval number
The distance between two vertices in a graph is the number of edges in the shortest path between them. In reality, the distance between two nodes is not a reflection of the nature of the paths. To capture the nature of a path, the distances measured in fuzzy graphs are more useful. There are a few types of distance available in the literature. Here, the distance between two vertices in an IVFG is given below. Herein, G is used as the IVFG.
Let G = (A, B) be an IVFG. For any path, P : u0 − u1 − u2 − ⋯ − un, the length of P is denoted by L(P) and is defined as
If n = 0, one can define L(P) = 0. For n ≥ 1, and if the graph has at least one nontrivial edge, then L(P) > 0. For any two vertices u, v in G, let P(u, v) be the set of all possible u − v paths between u and v, i.e., P(u, v) = {Pi : Pi is a (u, v)-path, i = 1, 2, 3, …}. The sum distance between u and v is defined as ds(u, v) = min{L(Pi) | Pi ∈ P(u, v), i = 1, 2, 3, …}.
This definition of distance satisfies the following properties for an IVFG G = (A, B).
(a) ds(u, v) ≥ 0, ∀ u, v ∈ A,
(b) ds(u, v) = 0 if and only if u = v,
(c) ds(u, v) = ds(v, u), ∀ u, v ∈ A.
The statement (c) is true; as in every path, one can find a reverse path with the same sum distance.
Let G = (A, B) be an IVFG and u, v, w ∈ A. ds(u, w) ≤ ds(u, v) + ds(v, w).
Let P1 be a (u, v)-path and P2 be a (v, w)-path following P1. Now, one can find an another u, w path. Then, the sum distance of the latter path is, at most, ds(u, v) + ds(v, w). Thus, from Lemma 1 and the properties, ds : V × V → [0, 1] is a metric.
The aim is to introduce an algorithm to find the sum distance between two given vertices. To find the sum distance between two given vertices, the breadth-first search (BFS) technique is used.
In this algorithm, the notations defined below are used
i) Q: Is a queue.
ii) Q.enqueue(t, Pt): Enqueues a vertex t and path Pt to queue Q.
iii) Q.dequeue(): Dequeues the first entry of the queue Q.
iv) Pt: Is the set of vertices that induces a subpath of the IVFG G = (A, B) from the vertex u to the vertex t.
v) L(Pt): Is the length of the path Pt of the IVFG G.
vi) G.adjacentEdges(t): Retrieves all the adjacent edges of the t.
vii) G.adjacentVertex(t, e): Retrieves the other end of the edge e whose one end is t.
Algorithm SD(u, v)
Input: Adjacency matrix of the IVFG G = (A, B) and two vertices u and v. |
Output: Sum distance between the vertices u and v. |
Step 1: Create an empty queue Q. |
Step 2: Create an empty set S. |
Step 3: Initially set Pu = {u} and L(Pu) = 0. In addition, set S = S ∪ {u} and Q.enqueue((u, Pu)). |
Step 4: Set sum_distance = M, a large possible number. |
Step 5: While Q is not empty |
(t, Pt) ← Q.dequeue(). |
if t = v then |
sum_distance |
= min{sum_distance, L(Pt)} |
end if. |
for each edge e in G.adjacentEdges(t) |
s ← G.adjacentVertex(t, e) |
Ps ← Pt ∪ {s}. |
Ls(P) = Lt(P) + μ−(e) + μ+(e). |
if s is not in S then |
S ← S ∪ {s}. |
Q.enqueue((s, Ps)). |
end if; |
end for; |
end while; |
Step 6: Return sum_distance. |
The Algorithm SD takes O(mn) times.
Let the processor take unit time to perform a single instruction. Steps 1, 2, 3, and 4 take O(1) time each. The algorithm consists of a loop in Step 5. This loop carries over O(n) times because the queue contains only the vertices of the graph. Within this loop, a loop occurs that is terminated after m times. Hence, the overall time complexity of Algorithm SD is O(mn).
The eccentricity, radius, and diameter of an IVFG are defined based on the sum distance as follows:
Let G = (A, B) be a connected IVFG and u be a vertex of G. The eccentricity e(u) of u is the sum distance to a vertex farthest from u. Thus, e(u) = max{ds(u, v) | v ∈ A}. Now, the eccentric vertex of u is a vertex whose sum distance u is e(u). The radius of G is denoted by r(G), and r(G) is the minimum of the eccentricities of all vertices. The diameter of G is denoted by d(G), and it is the maximum eccentricities of all vertices. A vertex u is a central vertex if e(u) = r(G). The set of vertices C(G) is the set of all central vertices. The fuzzy subgraph induced by C(G) is the center of G. A connected fuzzy graph G is self-centered if each vertex is a central vertex. A vertex u is peripheral if e(u) = d(G).
The following example illustrates the definitions.
An IVFG G is shown in Figure 1. The membership values of the edges are given as follows: (a, b) → [0.2, 0.4], (a, c) → [0.4, 0.5], (a, d) → [0.3, 0.7], (b, c) → [0.4, 0.7], (b, d) → [0.8, 0.9], (c, d) → [0.4, 0.7]. The sum distance between a and d is calculated as follows: The paths between a and d are P1 : a → c → d, P2 : a → d, P3 : a → b → d, P4 : a → c → b → d, P5 : a → b → c → d. Now, L(P1) = 1, L(P2) = 0.5, L(P3) = 1.15, L(P4) = 1.85, L(P5) = 1.4. So, ds(a, d) = min{L(Pi) | i = 1, 2, …, 5} = 0.5. Here, the eccentricity of a, e(a) = 0.3. Similarly, one can find the eccentricities of other vertices. Now, the radius of the graph r(G) = 0.3. Again, d(G), the diameter of the graph, is the maximum eccentricity of the vertices of the graph. Here, d(G) = 0.5. The central vertices are a and b. The peripheral vertex is d.
The following theorem describes the relation between radius and diameter for any IVFG.
For any connected IVFG G, r(G) ≤ d(G).
If all the edges of a path are independent strong, then the following condition is true.
Let G be an IVFG. If all the edges of a(u, v)-path are independent strong, then
Let G be an IVFG. Assume that the minimum value of L(P) between u and v is attained in path P. Let P contain n edges, and all the edges of P be strong. Then, μ−(ui, ui+1) ≥ 0.5 for all edges (ui, ui+1) in the path. Now, the sum distance between vertices u and v is ds(u, v) = min{L(Pi) | Pi ∈ P(u, v), i = 1, 2, 3, …}, where
Again, it is clear that μ+(ui−1, ui) + μ−(ui−1, ui) ≥ 1 for all independently strong edges of the path. Thus,
For every two vertices u and v in a connected IVFG G, |e(u) − e(v)| ≤ ds(u, v).
Assume without loss of generality e(u) ≥ e(v). Let x be a vertex farthest from u, i.e., e(u) = ds(u, x) ≤ ds(u, v) + ds(v, x), by triangle inequality. Thus, e(u) ≤ ds(u, v) + e(v), i.e., |e(u) − e(v)| ≤ ds(u, v).
This theorem can be further extended to the following one.
For every two adjacent vertices u and v in a connected IVFG G, |e(u) − e(v)| ≤ σ+(u) ∧ σ+(v).
Assume without loss of generality e(u) ≥ e(v). Let x be a vertex farthest from u, i.e., e(u) = ds(u, x) ≤ ds(u, v) + ds(v, x), by triangle inequality. Thus, e(u) ≤ ds(u, v) + e(v). Because u, v are adjacent,
For every two adjacent vertices u and v in a connected IVFG, |e(u) − e(v)| ≤ 1.
The necessary and sufficient condition of a vertex to be eccentric can be found from the following theorem.
Let G be an IVFG. Furthermore, v is an eccentric vertex of u if and only if
where P is the path connecting u to v.
It is known that ds(u, v) = min{L(Pi) | Pi ∈ P(u, v), i = 1, 2, 3, …}, where
Thus,
Conversely, let ∑(x,y)∈P μ+(x, y) + ∑(x,y)∈P μ−(x, y) = 2e(u), where P is the path connecting u to v. Then, ds(u, v) = e(u). Thus, v is an eccentric vertex of u.
If G is a self-centered fuzzy graph, then each vertex of G is eccentric. This statement can be described by the following theorem.
Let G be an IVFG. If G is self-centered, then for every vertex u, another vertex v is found such that
where P is the path connecting u to v.
Let, if possible, a vertex u1 be found such that ∑(x,y)∈P μ+(x, y) + ∑(x,y)∈P μ−(x, y) = 2e(v1), where v1 is the farthest vertex from u1, and P is the path from u1 to v1. However, because v1 is the farthest vertex from u1, ∑(x,y)∈P μ+(x, y) +∑(x,y)∈P μ−(x, y) = 2e(u1), where P is the path from u1 to v1.
In addition, if G is self-centered, then the eccentricity of every vertex is the same. Therefore, e(u1) = e(v1). Then, u1 is eccentric of v1. This gives the result ∑(x,y)∈P μ+(x, y) + ∑(x,y)∈P μ−(x, y) = μ+(ui−1, ui) + μ−(ui=1, ui). However, 2e(v1), where P is the path from u1 to v1. Hence, for every vertex u in G, another vertex v is found such that ∑(x,y)∈P μ+(x, y) + ∑(x,y)∈P μ−(x, y) = 2e(u), where P is the path connecting u to v.
If G is a self-centered IVFG, then each vertex of G is eccentric.
Assume G is self-centered and let u be any vertex of G. Let v be an eccentric vertex of u. Then, e(u) = ds(u, v). Because G is self-centered, e(v) = e(u). Therefore, e(u) = ds(u, v) = e(v), which shows that u is an eccentric vertex of v. Hence, the proof is completed.
This lemma is not sufficient. If all the vertices of an IVFG are eccentric, then the graph need not be self-centered. In Figure 1, all vertices are eccentric, and the central vertices are only b and c.
Let G be a connected IVFG. The central vertices may not form a connected IVFG.
The proof of the theorem is obvious.
The sum distance for complete IVFG is deduced in the following theorem.
Let G be a complete IVFG. Then,
Let P : u0 − u1 − u2 − ⋯ − un be any path in a complete IVFG G. Now, from Definition 1, one has
The sum of the distances between the vertices in an IVFG was described. This distance is not an interval but rather a real number. Depending on the distance, the eccentricity, radius, diameter, etc. were introduced. The relation between the radius and diameter and the eccentricities between any two vertices were established. The necessary and sufficient conditions for a vertex to be eccentric were derived. In addition, the condition of the vertices in a self-centered IVFG was established. The definition of sum distance and other concepts were applied to a complete IVFG.
A technique was used empirically to determine the sum distance between vertices in an IVFG. An algorithm was also proposed to determine the sum distance. The BFS technique was used to determine the distance. Some other techniques can be used to define the sum distances. However, the method used is appropriate because the sum distance between vertices in an IVFG can be deduced as the sum distance between vertices in fuzzy graphs. This result is significant because an IVFG is the generalization of fuzzy graphs. The distance measured in this study should be helpful in capturing the real distances in any network. Based on this, network centrality can be defined.
An interval-valued fuzzy graph.
Algorithm SD(
( |
if |
|
= min{ |
end if. |
for each edge |
|
|
|
if |
|
|
end if; |
end for; |
end while; |
Some important notations
Names | Notations |
---|---|
Interval-valued fuzzy graphs | |
Edge membership value | |
Vertex membership value | |
Distance | |
Eccentricity | |
Sum distance |
E-mail: tarasankar.math07@gmail.com
E-mail: ssamantavu@gmail.com
E-mail: mmpalvu@gmail.com