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 [?, 9]. Furthermore, they studied and proved different results on these graphs [10–15]. Bhutani and his colleagues [16, 17] discussed the strengths of arcs. Mathew and Sunitha [18] added a new concept of different types of arc. Further details about fuzzy graphs can be found elsewhere [19].

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 V₁ and V₂ such that μ⁺(v₁, v₂) > 0 if v₁ ∈ V₁ (or V₂) and v₂ ∈ V₂ (or V₁). 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₁ − v₂ − ⋯ − v_n is defined as $L_{{\mu }^{+}}(P)={\sum }_{i=1}^{n-1}{\mu }^{+}(v_i,v_{i+1})$. The μ-length of path P is defined as $L_{{\mu }^{-}}(P)={\sum }_{i=1}^{n-1}{\mu }^{-}(v_i,v_{i+1})$. The μ-length of the path is L_μ(P) = [L_μ⁻(P), L_μ⁺(P)].

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 $I_{(a,b)}=[I_{(a,b)}^{-},I_{(a,b)}^{+}]$, where $I_{(a,b)}^{-}=\frac{{\mu }^{-}(a,b)}{\text{min}\{{\sigma }^{+}(a),{\sigma }^{+}(b)\}}$, and $I_{(a,b)}^{+}=\frac{{\mu }^{+}(a,b)}{\text{min}\{{\sigma }^{+}(a),{\sigma }^{+}(b)\}}$. An edge (a, b) is nontrivial if $I_{(a,b)}^{-}>0$. Let G = (A, B) be an IVFG. An edge (a, b) in G is independent strong [12] if I_(a,b) ≥ [0.5, 0.5] and independent weak otherwise.

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.

Definition 1

Let G = (A, B) be an IVFG. For any path, P : u₀ − u₁ − u₂ − ⋯ − 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.

Lemma 1

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₁ be a (u, v)-path and P₂ be a (v, w)-path following P₁. 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 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, 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 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.

Theorem 1

The Algorithm SD takes O(mn) times.

Definition 2

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 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.

Example 1

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₁ : a → c → d, P₂ : a → d, P₃ : a → b → d, P₄ : a → c → b → d, P₅ : a → b → c → d. Now, L(P₁) = 1, L(P₂) = 0.5, L(P₃) = 1.15, L(P₄) = 1.85, L(P₅) = 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.

Theorem 2

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.

Theorem 3

Let G be an IVFG. If all the edges of a(u, v)-path are independent strong, then $d_s(u,v)\ge \frac{n}{2}$, where n is the number of edges of the corresponding path.

Theorem 4

For every two vertices u and v in a connected IVFG G, |e(u) − e(v)| ≤ d_s(u, v).

Theorem 5

For every two adjacent vertices u and v in a connected IVFG G, |e(u) − e(v)| ≤ σ⁺(u) ∧ σ⁺(v).

Note 1

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.

Theorem 6

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.

Theorem 7

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.

Lemma 2

If G is a self-centered IVFG, then each vertex of G is eccentric.

Lemma 3

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.

Theorem 8

Let G be a complete IVFG. Then, $2L(P)={\sum }_{i=1}^n\{{\sigma }^{+}(u_{i-1})\wedge {\sigma }^{+}(u_i)+{\sigma }^{-}(u_{i-1})\wedge {\sigma }^{-}(u_i)\}$ for any path, P : u₀ − u₁ − u₂ − ⋯ − u_n.

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.