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 graphtheoretic problem may be uncertain. In 1975, Zadeh [1] introduced the notion of intervalvalued 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 intervalvalued 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 intervalvalued 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 intervalvalued fuzzy set on V, and B = (V × V, [μ^{−}, μ^{+}]) is an intervalvalued 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 intervalvalued fuzzy vertex set of G, and B is the intervalvalued fuzzy edge set of ξ.
An IVFG G = (A, B) is a complete intervalvalued 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 V_{1} and V_{2} such that μ^{+}(v_{1}, v_{2}) > 0 if v_{1} ∈ V_{1} (or V_{2}) and v_{2} ∈ V_{2} (or V_{1}). 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 : v_{1} − v_{2} − ⋯ − v_{n} is defined as
Let G be a connected IVFG. The μ^{+}distance δ^{+}(v_{i}, v_{j}) is the smallest μ^{+}length of any v_{i} − v_{j} path P in G, where v_{i}, v_{j} ∈ V — that is, δ^{+}(v_{i}, v_{j}) = min L_{μ}_{+}(P). The μ^{−}distance δ^{−}(v_{i}, v_{j}) is the largest μ^{−}length of any v_{i} − v_{j} path P in G, where v_{i}, v_{j} ∈ V — that is, δ^{−}(v_{i}, v_{j}) = max L_{μ}_{−}(P). Thus, the distance δ(v_{i}, v_{j})=[δ^{−}(v_{i}, v_{j}), δ^{+}(v_{i}, v_{j})] = [max L_{μ}_{−}(P), min L_{μ}_{+}(P)].
Let G be a connected IVFG. The μ^{+}eccentricity of a vertex v_{i} is e_{μ}_{+}(v_{i}) = max{δ(v_{i}, v)  v ∈ V, v v_{i}}. The μ^{−}eccentricity of vertex v_{i} is e_{μ}_{−}(v_{i}) = max{δ^{−}(v_{i}, v)  v ∈ V, v/ = v_{i}}. Thus, the eccentricity of a vertex v_{i} is [e_{μ}_{−}(v_{i}), e_{μ}_{+}(v_{i})].
Let G be a connected IVFG. The μ^{+}radius of G is r_{μ}_{+}(G) = min{e_{μ}_{+}(v_{i})  v_{i} ∈ V }. The μ^{−}radius of G is r_{μ}_{−}(G) = min{e_{μ}_{−}(v_{i})  v_{i} ∈ 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_{μ}_{+}(v_{i})  v_{i} ∈ V }. The μ^{−}diameter of G is d_{μ}_{−}(G) = max{e_{μ}_{−}(v_{i})  v_{i} ∈ 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 : u_{0} − u_{1} − u_{2} − ⋯ − u_{n}, 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) = {P_{i} : P_{i} is a (u, v)path, i = 1, 2, 3, …}. The sum distance between u and v is defined as d_{s}(u, v) = min{L(P_{i})  P_{i} ∈ P(u, v), i = 1, 2, 3, …}.
This definition of distance satisfies the following properties for an IVFG G = (A, B).
(a) d_{s}(u, v) ≥ 0, ∀ u, v ∈ A,
(b) d_{s}(u, v) = 0 if and only if u = v,
(c) d_{s}(u, v) = d_{s}(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. d_{s}(u, w) ≤ d_{s}(u, v) + d_{s}(v, w).
Let P_{1} be a (u, v)path and P_{2} be a (v, w)path following P_{1}. Now, one can find an another u, w path. Then, the sum distance of the latter path is, at most, d_{s}(u, v) + d_{s}(v, w). Thus, from Lemma 1 and the properties, d_{s} : 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 breadthfirst search (BFS) technique is used.
In this algorithm, the notations defined below are used
i) Q: Is a queue.
ii) Q.enqueue(t, P_{t}): Enqueues a vertex t and path P_{t} to queue Q.
iii) Q.dequeue(): Dequeues the first entry of the queue Q.
iv) P_{t}: 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(P_{t}): Is the length of the path P_{t} 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 P_{u} = {u} and L(P_{u}) = 0. In addition, set S = S ∪ {u} and Q.enqueue((u, P_{u})). 
Step 4: Set sum_distance = M, a large possible number. 
Step 5: While Q is not empty 
(t, P_{t}) ← Q.dequeue(). 
if t = v then 
sum_distance 
= min{sum_distance, L(P_{t})} 
end if. 
for each edge e in G.adjacentEdges(t) 
s ← G.adjacentVertex(t, e) 
P_{s} ← P_{t} ∪ {s}. 
L_{s}(P) = L_{t}(P) + μ^{−}(e) + μ^{+}(e). 
if s is not in S then 
S ← S ∪ {s}. 
Q.enqueue((s, P_{s})). 
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{d_{s}(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 selfcentered 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 P_{1} : a → c → d, P_{2} : a → d, P_{3} : a → b → d, P_{4} : a → c → b → d, P_{5} : a → b → c → d. Now, L(P_{1}) = 1, L(P_{2}) = 0.5, L(P_{3}) = 1.15, L(P_{4}) = 1.85, L(P_{5}) = 1.4. So, d_{s}(a, d) = min{L(P_{i})  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, μ^{−}(u_{i}, u_{i}_{+1}) ≥ 0.5 for all edges (u_{i}, u_{i}_{+1}) in the path. Now, the sum distance between vertices u and v is d_{s}(u, v) = min{L(P_{i})  P_{i} ∈ P(u, v), i = 1, 2, 3, …}, where
Again, it is clear that μ^{+}(u_{i}_{−1}, u_{i}) + μ^{−}(u_{i}_{−1}, u_{i}) ≥ 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) ≤ d_{s}(u, v).
Assume without loss of generality e(u) ≥ e(v). Let x be a vertex farthest from u, i.e., e(u) = d_{s}(u, x) ≤ d_{s}(u, v) + d_{s}(v, x), by triangle inequality. Thus, e(u) ≤ d_{s}(u, v) + e(v), i.e., e(u) − e(v) ≤ d_{s}(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) = d_{s}(u, x) ≤ d_{s}(u, v) + d_{s}(v, x), by triangle inequality. Thus, e(u) ≤ d_{s}(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 d_{s}(u, v) = min{L(P_{i})  P_{i} ∈ 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, d_{s}(u, v) = e(u). Thus, v is an eccentric vertex of u.
If G is a selfcentered 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 selfcentered, 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 u_{1} be found such that ∑_{(}_{x}_{,}_{y}_{)∈}_{P} μ^{+}(x, y) + ∑_{(}_{x}_{,}_{y}_{)∈}_{P} μ^{−}(x, y) = 2e(v_{1}), where v_{1} is the farthest vertex from u_{1}, and P is the path from u_{1} to v_{1}. However, because v_{1} is the farthest vertex from u_{1}, ∑_{(}_{x}_{,}_{y}_{)∈}_{P} μ^{+}(x, y) +∑_{(}_{x}_{,}_{y}_{)∈}_{P} μ^{−}(x, y) = 2e(u_{1}), where P is the path from u_{1} to v_{1}.
In addition, if G is selfcentered, then the eccentricity of every vertex is the same. Therefore, e(u_{1}) = e(v_{1}). Then, u_{1} is eccentric of v_{1}. This gives the result ∑_{(}_{x}_{,}_{y}_{)∈}_{P} μ^{+}(x, y) + ∑_{(}_{x}_{,}_{y}_{)∈}_{P} μ^{−}(x, y) = μ^{+}(u_{i}_{−1}, u_{i}) + μ^{−}(u_{i}_{=1}, u_{i}). However, 2e(v_{1}), where P is the path from u_{1} to v_{1}. 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 selfcentered IVFG, then each vertex of G is eccentric.
Assume G is selfcentered and let u be any vertex of G. Let v be an eccentric vertex of u. Then, e(u) = d_{s}(u, v). Because G is selfcentered, e(v) = e(u). Therefore, e(u) = d_{s}(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 selfcentered. 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 : u_{0} − u_{1} − u_{2} − ⋯ − u_{n} 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 selfcentered 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 intervalvalued fuzzy graph.
Algorithm SD(
( 
if 

= min{ 
end if. 
for each edge 



if 


end if; 
end for; 
end while; 
Some important notations
Names  Notations 

Intervalvalued fuzzy graphs  
Edge membership value  
Vertex membership value  
Distance  
Eccentricity  
Sum distance 
Email: tarasankar.math07@gmail.com
Email: ssamantavu@gmail.com
Email: mmpalvu@gmail.com