Edge geodesic number of a fuzzy graph

Abstract

In this paper, the edge version of the geodesic number of a fuzzy graph is introduced and the properties satisfied are identified. A comparison between the vertex and edge version of the geodesic number of fuzzy graphs is obtained. The edge geodesic number of fuzzy trees, complete fuzzy graphs, complete bipartite fuzzy graphs and of fuzzy cycles are identified. A necessary and sufficient condition for the existence of an edge geodesic cover in a fuzzy graph is obtained. An application of edge geodesic sets in transportation systems in optimizing the number of traffic inspectors patrolling an urban road network is demonstrated. The fuzziness in the problem helps to identify routes receiving less priority among passengers, elimination of which minimizes the loss suffered by various transport corporations due to lack of collection.

Keywords

Edge geodesic cover edge geodesic basis

1 Introduction

In 1965, Lotfi Aliasker Zadeh [41], a renowned mathematician, computer scientist, electrical engineer, artificial intelligence researcher and professor emeritus of computer science at the University of California, Berkeley, introduced the concept of fuzzy sets as a way for representing uncertainty. Azriel Rosenfeld [29] was one of the researchers motivated by the work of Zadeh and his interest in fuzzy sets lead to the development of the concept of fuzzy graphs in 1975. The first definition of a fuzzy graph was however given by Kauffman [17] in 1973. R. T. Yeh and S. Y. Bang [40] were other such researchers who contributed to the field of fuzzy relations and fuzzy graphs thereby providing an application of fuzzy graphs in clustering analysis. A. Rosenfeld also obtained the fuzzy analogue of several graph theoretic concepts like paths, cycles, trees and connectedness along with some of their properties [29] and the concept of fuzzy trees [26], automorphism of fuzzy graphs [9], fuzzy interval graphs [23], cycles and co-cycles of fuzzy graphs [24] etc has been established by several authors during the course of time. M. Akram et al. in [2 –6] introduced the concepts of bipolar fuzzy graphs and interval-valued fuzzy line graphs and established some of the properties satisfied by them. Fuzzy groups and the notion of a metric in fuzzy graphs was introduced by P. Bhattacharya [8]. The concept of strong arcs [12] was introduced by K. R. Bhutani and A. Rosenfeld in the year 2003. This paved path for the introduction of strong paths and shortest strong paths, also known as geodesics, in fuzzy graphs [11]. The definition of fuzzy end nodes and some of its properties were established by the same authors in [10]. S. Samanta and B. Sarkar conducted studies on Generalized fuzzy graphs [33] and generalized fuzzy trees [34]. Talal Al-Hawary [1] conducted studies on complete fuzzy graphs. Several other significant works on fuzzy graphs can be found in [22 , 28]. Rashmanlou et al. in [20] defined three new operations on interval-valued fuzzy graphs namely strong product, tensor product and lexicographic product. The authors also conducted studies about the degree of a vertex in interval-valued fuzzy graphs which are obtained from two given interval-valued fuzzy graphs using the operations Cartesian product, composition, tensor and strong product of two interval-valued fuzzy graphs. The embedding of m-polar fuzzy graphs constructed on the surface of spheres was introduced by Mandal et al. in [21]. Some other important works in fuzzy graphs include [30 –32]. Frank Harary et al. defined the concept of geodetic number of crisp graphs for vertices in [13 , 16]. This concept was extended to fuzzy graphs using geodesic distance by N. T. Suvarna and M. S. Sunitha in [39] and using μ-distance by J. P. Linda and M. S. Sunitha in [18]. The edge version of geodetic numbers in crisp graph was formally defined by Musthafa Atici in [7] and also by A. P. Santhakumaran and J. John in [36]. Further Studies on the edge geodetic covers in graphs were carried out by Rochelleo. E. Mariano and Sergio. R. Canoy in [28]. In this paper, we introduce the concept of edge geodesic number in fuzzy graphs using geodesic distance and establish some of the properties satisfied by them. The edge geodesic number of certain classes of fuzzy graphs are determined. An application of edge geodesic sets in optimizing the number of traffic inspectors required to patrol and inspect the bus routes prevailing in an urban road network and at the same time to identify those routes receiving less priority among passengers and hence eliminating them in order to minimize the loss suffered by various transport corporations due to lack of collection is demonstrated.

2 Preliminaries

In this section, a brief summary of some basic definitions in fuzzy graph theory is given.

Definition 2.1. [25] A fuzzy graph is a triplet G : (V, σ, μ) where σ is a fuzzy subset of a set V of vertices and μ is a fuzzy relation on σ. That is, μ (u, v) ≤ σ (u) ∧ σ (v),∀u, v ∈ V . We assume that V is finite and non-empty, μ is reflexive (i . e . , μ (x, x) = σ (x) , ∀ x) and symmetric (i . e . , μ (x, y) = μ (y, x) , ∀ (x, y)). Also we denote the underlying crisp graph [15] by G^* : (σ^*, μ^*) where σ^* = {u ∈ V/σ (u) >0} and μ^* = {(u, v) ∈ V × V/μ (u, v) >0} . Throughout we assume σ^* = V.

A fuzzy graph G : (V, σ, μ) is called trivial if G^* is trivial. Otherwise it is called non-trivial.

Definition 2.2. [25] The fuzzy graph H : (V, τ, ν) is called a fuzzy subgraph of G : (V, σ, μ) if τ (u) = σ (u), ∀u ∈ τ^* and ν (u, v) = μ (u, v), ∀ (u, v) ∈ ν^* and if in addition τ^* = σ^*, then H is called a spanning fuzzy subgraph of G.

Definition 2.3. [25] A fuzzy graph G : (V, σ, μ) is a complete fuzzy graph if μ (u, v) = σ (u) ∧ σ (v) ∀u, v ∈ σ^* .

Definition 2.4. [25] A sequence of distinct nodes u₀, u₁, . . . , u_n such that μ (u_i-1, u_i) >0, i = 1, 2, 3, . . . , n is called a path P_n of length n.

Definition 2.5. [26] An arc (x, y) of G : (V, σ, μ) with least non-zero membership value is the weakest arc of G. The degree of membership of a weakest arc in a path is defined as the strength of the path. The path becomes a cycle if u₀ = u_n, n ≥ 3 and a cycle is called a fuzzy cycle if it contains more than one weakest arc.

Definition 2.6. [25] The strength of connectedness between two nodes u and v is the maximum of the strengths of all paths between u and v and is denoted by CONN_G (u, v) . A fuzzy graph G : (V, σ, μ) is said to be connected if CONN_G (u, v) >0 for every u, v in σ^*.

Definition 2.7. [12] An arc (u, v) of a fuzzy graph is called strong if its weight is at least as great as the strength of connectedness of its end nodes u, v when the arc (u, v) is deleted and a u - v path P is called a strong path if P contains only strong arcs.

Definition 2.8. [22] Depending on the CONN_G (u, v) of an arc (u, v) in a fuzzy graph G, three different types of arcs denoted by α, β and δ are defined. Note that CONN_G-(u,v) (u, v) denote the strength of connectedness between u and v in the fuzzy graph G obtained by deleting the arc (u, v). Then

an arc (u, v) in G is α-strong if CONN_G-(u,v) (u, v) < μ (u, v).

an arc (u, v) in G is β-strong if CONN_G-(u,v) (u, v) = μ (u, v).

an arc (u, v) in G is δ-arc if CONN_G-(u,v) (u, v) > μ (u, v) .

a δ-arc (u, v) is called a δ^*-arc if μ (u, v) > μ (x, y) where (x, y) is a weakest arc of G.

an arc (u, v) in G is said to be strong if it is either α-strong or β-strong. A path P is called a strong path if all arcs of P are either α-strong or β-strong.

Definition 2.9. [29] A connected fuzzy graph G : (V, σ, μ) is called a fuzzy tree if it has a spanning fuzzy subgraph F : (V, σ, ν), which is a tree such that for all arcs (u, v) not in F, CONN_F (u, v) > μ (u, v).

Definition 2.10. [37] A fuzzy graph G is said to be bipartite if the vertex set V can be partitioned into two non-empty sets V₁ and V₂ such that μ (v₁, v₂) =0 if v₁, v₂ ∈ V₁ or v₁, v₂ ∈ V₂. Further if μ (u, v) = σ (u) ⋀ σ (v) ∀u ∈ V₁ and ∀v ∈ V₂, then G is called a complete bipartite fuzzy graph and is denoted by K_σ₁,σ₂, where σ₁ and σ₂ are respectively the restrictions of σ to V₁ and V₂.

Definition 2.11. [10] Two nodes u and v in a fuzzy graph G : (V, σ, μ) are neighbors (adjacent) if μ (u, v) >0 and v is called a strong neighbor of u if the arc (u, v) is strong. Also N (u) denotes the set of neighbors of u other than u where as N [u] denotes the set of neighbors of u including u. The degree of u is deg (u) = |N (u) |. A node v is called a fuzzy end node of G if it has at most one strong neighbor in G.

Definition 2.12. [11] A strong path P from u to v is called geodesic if there is no shorter strong path from u to v and the length of a u - v geodesic is the geodesic distance from u to v denoted by d_g (u, v).

Definition 2.13. [35] The geodesic eccentricity e_g (u) of a node u in a connected fuzzy graph G : (V, σ, μ) is given by $e_{g} (u) = \max_{v \in V} d_{g} (u, v)$ . The maximum g-eccentricity among the nodes of G is its g-diameter denoted by d_g (G). The minimum g-eccentricity among the nodes of G is its g-radius denoted by r_g (G). A node with maximum e_g is called a g-peripheral node or diametral node and a geodesic with maximum geodesic distance is a diametral path. The geodesic eccentric node (g-eccentric node) of u in G is a node v such that e_g (u) = d_g (u, v).

The following definitions and results have been taken from [11, 39].

Definition 2.14. [11] Let S be a set of nodes of a connected fuzzy graph G. The geodesic closure (S) of S is the set of all nodes in S together with the nodes that lie on geodesics between nodes of S. S is said to be convex if S contains all nodes of every u - v geodesic for all u, v in S. i.e, if (S) = S. S is said to be geodesic cover (geodesic set) of G if (S) = V (G) and any cover of G with minimum number of nodes is called a geodesic basis for G. Order of a geodesic basis is the number of nodes in it.

Definition 2.15. [39] The geodesic number of a fuzzy graph G : (V, σ, μ) is the order of a geodesic basis of G and is denoted by gn (G).

Proposition 2.16. [39] For a complete fuzzy graph G on n nodes, gn (G) = n .

3 Edge geodesic number of a fuzzy graph [gn_e (G)]

Studies on the edge geodetic number of crisp graphs were carried out by Mustafa Atici in [7] and by Santhakumaran and John in [36]. Some of the properties satisfied by the edge geodetic number of graphs were discussed in [28] by Rochelleo E.Mariano and Sergio R.Canoy. In this section, the concept of edge geodesic number in fuzzy graphs using geodesic distance is introduced. It is established that a fuzzy graph contains an edge geodesic basis if and only if it has no δ-arcs. A comparison between the vertex and edge version of the geodesic number of fuzzy graphs is obtained. The edge geodesic number of fuzzy trees, complete fuzzy graphs, complete bipartite fuzzy graphs and of fuzzy cycles are obtained.

Definition 3.1. Let S be a set of nodes in a connected non-trivial fuzzy graph G : (V, σ, μ). Then the edge geodesic closure of S, denoted by (S) _e, is the set of all edges lying on the geodesics between nodes of S.

Definition 3.2. A set S of nodes in a connected non-trivial fuzzy graph G : (V, σ, μ) is defined to be an edge geodesic cover (edge geodesic set) of G if (S) _e = E (G), the edge set of G.

Definition 3.3. An edge geodesic set of minimum cardinality is called an edge geodesic basis of G and the cardinality of an edge geodesic basis in G is the edge geodesic number of G, denoted by gn_e (G) .

Example 3.4. Consider the fuzzy graph G : (V, σ, μ) given in Fig. 1.

Fig.1

Edge geodesic number of a fuzzy graph.

If S = {u, v, x} then (S) _e = E (G) and so S is an edge geodesic cover of G. No other subset of V (G) of cardinality less than 3 is an edge geodesic cover and so gn_e (G) =3. Also note that is a geodesic basis of G so that gn (G) =2. Thus the geodesic number and the edge geodesic number of a fuzzy graph need not be the same.

Remark 3.5. Note that the edge geodesic basis of a connected non-trivial fuzzy graph need not be unique. There can be more than one edge geodesic basis for a fuzzy graph. For the fuzzy graph G : (V, σ, μ) given in Fig. 2, S₁ = {z, y, v, w} and S₂ = {z, u, x, w} are two edge geodesic bases of G.

Fig.2

A fuzzy graph containing two edge geodesic bases.

Remark 3.6. There may be cases when a connected non-trivial fuzzy graph G : (V, σ, μ) does not have any edge geodesic cover. For example, consider the fuzzy graph G : (V, σ, μ) given in Fig. 3.

Fig.3

A fuzzy graph containing no edge geodesic cover.

Here (S) _e ≠ E (G) for any choice of S ⊆ V (G) since the arc (u, x) is a δ-arc and does not lie on any geodesic. Note that a geodesic in a fuzzy graph contains only strong arcs such as α-strong or β-strong arcs and no δ-arcs. Thus it follows that if a fuzzy graph contains at least one δ-arc, then it has no edge geodesic cover and thus we have the following result.

Proposition 3.7. A connected non-trivial fuzzy graph G : (V, σ, μ) contains an edge geodesic cover if and only if it has no δ-arcs.

Proof. Suppose first that G : (V, σ, μ) is a connected non-trivial fuzzy graph that has an edge geodesic cover say S. Then clearly each edge of G lies on a geodesic joining some pair of nodes in S. Assume on the contrary that G contains a δ-arc (u, v). Then it is evident from the definition of geodesics [11] that (u, v) is not an edge of any geodesic path joining nodes of S, contradicting the fact that S is an edge geodesic cover of G. Thus G contains no δ-arcs. To prove the converse, suppose that G is a fuzzy graph containing no δ-arcs. Then since each arc of G is strong, V (G) forms an edge geodesic cover of G. □

Proposition 3.8. For any connected non-trivial fuzzy graph G : (V, σ, μ) on n nodes having no δ-arcs, 2 ≤ gn_e (G) ≤ n.

Proof. An edge geodesic cover needs at least 2 nodes and so gn_e (G) ≥2. Also, since G has no δ-arcs, the set of all nodes in G is an edge geodesic cover of G. Hence it is clear that gn_e (G) ≤ n. Thus 2 ≤ gn_e (G) ≤ n. □

Remark 3.9. For a path P_n on n nodes, it is clear that its end-nodes form a unique edge geodesic cover and so gn_e (P_n) =2.

Remark 3.10. Note that a fuzzy tree never contains β-strong arcs [22] and a fuzzy tree with no δ-arcs becomes a crisp tree. For any crisp tree T, the edge geodetic number equals the number of end-nodes in T. In fact, the set of all end nodes of T is the unique edge geodetic basis of T [36]. For example, the fuzzy tree G : (V, σ, μ) given in Fig. 4 has no β-strong arcs and no δ-arcs. Hence G is a crisp tree with end nodes {u₁, u₂} which are also the fuzzy end nodes of G. Also S = {u₁, u₂} is an edge geodesic basis for G and so gn_e (G) =2 =number of fuzzy end nodes of G.

Fig.4

A fuzzy tree.

Thus we have the following result.

Proposition 3.11. If G : (V, σ, μ) is a non-trivial fuzzy tree that has no δ-arcs, it has a unique edge geodesic basis consisting of its fuzzy end nodes.

Proof. Let S be the set of all fuzzy end nodes of G. Since G is a fuzzy tree that has no δ-arcs and since a fuzzy tree contains no β-strong arcs [22], it follows that each arc of G is α-strong. Hence it is obvious that G is a fuzzy tree such that G^* is a tree. Therefore the fuzzy end nodes of G are the end nodes of G^* and since each path between the nodes of G^* are unique [22], it follows that each arc of G clearly lies on a geodesic joining some pair of nodes in S. Thus S is an edge geodesic cover of G. Also, it is the edge geodesic cover of minimum cardinality for if u is a fuzzy end node of G that does not belong to S, then being an end node of G^*, the edge incident on u does not lie on any geodesic joining pairs of nodes in S. Therefore, S is the edge geodesic basis for G and so gn_e (G) is the number of fuzzy end nodes of G. □

Corollary 3.12. Let G : (V, σ, μ) with n ≥ 3 nodes be a fuzzy tree such that G^* is a tree. If G^* is a star graph, then gn_e (G) = n - 1.

Proof. Suppose G^* is a star graph on n nodes say K_1,n-1. Then by Proposition 3.11, since G is a fuzzy tree containing no δ-arcs, the set of all fuzzy end nodes of G form an edge geodesic basis of G. Hence gn_e (G) = n - 1. □ In fact the above corollary can be generalized as follows.

Proposition 3.13. Let G : (V, σ, μ) be a non-trivial connected fuzzy graph on n nodes containing no δ-arcs. If G has exactly one node u of degree n - 1, then the edge geodesic number, gn_e (G) = n - 1.

Proof. Since the fuzzy graph G has no δ-arcs, it follows from Proposition 3.7 that G has an edge geodesic cover. Let u be the unique node of G having degree n - 1. Then n ≥ 3. Let S = V (G) - {u}. First we show that S is an edge geodesic cover of G. That is to show that S covers each edge in G. Consider the following cases.

Case(1): Edges incident with u. Let (u, v) be an edge incident with u. Since u is the only node of degree n - 1, there exists at least one neighbor v′ of u such that v and v′ are not adjacent. The edge (u, v) thus lies on the geodesic v′ - u - v joining v′ and v in S. Thus S covers the edge (u, v). Similarly, it can be shown that S covers all edges incident with u.

For example, consider the fuzzy graph G : (V, σ, μ) on 5 nodes given in Fig. 5.

Fig.5

A fuzzy graph.

Here, u is the unique node of degree 5 - 1 =4. Take S = V (G) - {u}. Note that (u, v) is an edge incident with u and x is a neighbor of u such that v and x are not adjacent. The edge (u, v) thus lies on the v - u - x geodesic joining v and x in S. Similarly, S covers all edges incident with u.

Case(2): Edges not incident with u. Consider any edge (x, y) which is not incident with u. Clearly it lies on the geodesic (x, y) itself where x, y ∈ S. Thus S covers the edge (x, y). Similarly S covers all edges that are not incident with u. In Fig. 5, (x, y) is an edge not incident with u. Since x, y ∈ S, the edge (x, y) itself is the unique geodesic path joining x and y. Thus S covers the edge (x, y). Similarly, S covers all edges that are not incident with u. Thus it is clear from both cases that S is an edge geodesic cover of G and so gn_e (G) ≤ |S| = n - 1. Next we show that S is an edge geodesic basis of G. Let T ⊂ V (G) be such that |T| ≤ n - 2. Then there exists at least two nodes say v, w ∈ V (G) such that v, w ∉ T. Again consider the following cases.

Case(a): u ∈ T.

Then, since v, w ∉ T, the edge (u, v) or (u, w) cannot lie on a geodesic joining two nodes of T. In Fig. 5, if T = {u, x, y} ⊂ S, then the edges (u, v) and (u, w) does not lie on any geodesic joining any pair of nodes of T. Thus T cannot be an edge geodesic cover of G.

Case(b): u ∉ T.

Then u ≠ v or u ≠ w so that the edge (u, v) or (u, w) cannot lie on any geodesic joining two nodes of T.

In Fig. 5, if T = {v, x} ⊂ S, then the edge (u, w) does not lie on any geodesic joining any pair of nodes of T and so T is not an edge geodesic cover of G.

Thus in any case, T is not an edge geodesic cover of G. Hence S is the unique edge geodesic cover of G having minimum cardinality and so gn_e (G) = |S| = n - 1. □

Corollary 3.14. If G : (V, σ, μ) is a non-trivial connected fuzzy graph on n nodes containing no δ-arcs and if u is the unique node of G having degree n - 1, then gn_e (G) = n - 1 and V (G) - {u} is the unique edge geodesic basis of G that contains all nodes of G other than u.

Proof. It follows from the proof of Proposition 3.13. □

Example 3.15. Consider the fuzzy graph G : (V, σ, μ) given in Fig. 6.

Fig.6

A fuzzy graph on 5 nodes.

In G, u is the unique node of degree 5 - 1 and S = {w, y, v, x} is the unique edge geodesic basis of G that contains all nodes of G other than u. Therefore gn_e (G) =4 = 5 -1.

Remark 3.16. The converse of Proposition 3.13 is not true. For the fuzzy graph G : (V, σ, μ) given in Fig. 7, S = {u, y, v, x} is an edge geodesic basis of G and therefore, gn_e (G) =4 = 5 -1. But no node of G has degree 4.

Fig.7

A fuzzy graph containing no node of degree 4.

Proposition 3.17. Let G : (V, σ, μ) be a connected fuzzy graph on n nodes containing no δ-arcs such that G^* = K_n (n ≥ 2). Then the edge geodesic number gn_e (G) = n.

Proof. Since all arcs in G are strong and since G^* = K_n (n ≥ 2), we get each arc (u, v) is a geodesic for all u, v ∈ V (G) and no arc lies on the geodesic between any two other nodes in G. Then S = V (G) is an edge geodesic cover of G of minimum cardinality for if T ⊂ S such that the node u of S is not in T, then each arc which is incident on u is not on any geodesic joining pairs of nodes in T and so T is not an edge geodesic cover of G. Hence S = V (G) is the unique edge geodesic basis of G and so gn_e (G) = n. □

Example 3.18. Consider the connected non-trivial fuzzy graph G : (V, σ, μ) given in Fig. 8 that contains no δ-arcs.

Fig.8

A fuzzy arc containing no δ-arcs.

Here each arc is strong and hence S = {u, v, w, x} is the unique edge geodesic basis of G and so gn_e (G) =4. But note that the given fuzzy graph is not a complete fuzzy graph.

Remark 3.19. Converse of Proposition 3.17 is not true. That is, a connected non-trivial fuzzy graph G : (V, σ, μ) on n nodes having edge geodesic number n need not be a fuzzy graph such that G^* = K_n. For example, the connected fuzzy graph G : (V, σ, μ) given in Fig. 9 has S = V (G) as the unique edge geodesic basis of G and so gn_e (G) =5. But G^* is not complete.

Fig.9

A fuzzy graph G : (V, σ, μ) whose underlying crisp graph G^* is not complete.

Proposition 3.20. The edge geodesic number of a non-trivial complete fuzzy graph G : (V, σ, μ) on n nodes is n.

Proof. Since each arc in a complete fuzzy graph G is strong and since the underlying crisp graph G^* = K_n, it follows from Proposition 3.17 that gn_e (G) = n.□

Remark 3.21. It is clear from Propositions 2.16 and 3.20 that for a complete fuzzy graph G on n nodes, the geodesic number of G coincides with its edge geodesic number.

i.e, gn (G) = gn_e (G) = n .

For example, the complete fuzzy graph G : (V, σ, μ) given in Fig. 10 has S = {u, v, w, x} = V (G) as both geodesic basis and edge geodesic basis of G since each arc is strong and thus does not lie on any geodesic joining any two nodes of G.

Fig.10

A complete fuzzy graph.

Therefore, gn (G) = gn_e (G) =4.

Proposition 3.22. If a connected non-trivial fuzzy graph G : (V, σ, μ) on n nodes containing no δ-arcs has more than one node of degree n - 1, then every edge geodesic cover of G contain all nodes of degree n - 1.

Proof. Let G be a fuzzy graph on n nodes with more than one node of degree n - 1. Suppose that x and y are any two nodes of G having degree n - 1 each. Then x must be adjacent to y and y to x, thereby forming an edge (x, y) that does not lie on any geodesic joining two nodes of G other than x and y. Thus it can be concluded that every edge geodesic cover of G contain both x and y. Since x and y are arbitrary, it follows that every edge geodesic cover of G contain all nodes of degree n - 1. □

Proposition 3.23. If a connected non-trivial fuzzy graph G : (V, σ, μ) on n nodes containing no δ-arcs has more than one node of degree n - 1, then the edge geodesic number of G, gn_e (G) = n.

Proof. Note that if all nodes of G are of degree n - 1, then G^* = K_n and so by Proposition 3.17, gn_e (G) = n.

Otherwise, suppose that v₁, v₂, . . . , v_k (2 ≤ k ≤ n - 2) are nodes of G having degree n - 1 each. Then by Proposition 3.22, all these nodes belong to the edge geodesic basis of G (say) S. If possible, suppose |S| < n.

Let v be a node of G such that v ∉ S. Then v must be of degree less than n - 1 for otherwise v would have been in S. We prove that no edge of the form (v, v_i), (1 ≤ i ≤ k) lies on a geodesic joining two nodes of S.

Case(1): Both nodes of S are of degree n - 1 each.

Since among the nodes v_i, (1 ≤ i ≤ k) of degree n - 1, any two of them are always adjacent, an edge of the form (v, v_i) (1 ≤ i ≤ k) cannot lie on a geodesic joining a pair of nodes v_j and v_l, (j ≠ l), (1 ≤ j, l ≤ k) of S.

For example, consider the fuzzy graph G : (V, σ, μ) given in Fig. 11.

Fig.11

A fuzzy graph containing two nodes of degree 4.

Here, the nodes y and x are both of degree 5 - 1 =4 each. Then by Proposition 3.22, both of these nodes belong to the edge geodesic basis S of G. If possible suppose S = V (G) - {u}.

Now, if the node u ∉ S, then the edges (u, y) and (u, x) do not lie on any geodesic joining the nodes y and x of S.

Case(2): One node of S is of degree n - 1 and the other is of degree less than n - 1.

Note that each node v_i, (1 ≤ i ≤ k) is always adjacent to some node (say) u of S of degree less than n - 1, which is different from v_i, (1 ≤ i ≤ k). Thus the edge (v, v_i), (1 ≤ i ≤ k) cannot lie on a geodesic joining a node v_i and the node u of S. In Fig. 11, consider the two nodes y and w of S. If the node u ∉ S, then the edge (u, y) does not lie on a geodesic joining the node y (which is of degree 5 - 1 =4) and the node w (which is of degree 3).

Case(3): Both nodes of S are of degree less than n - 1.

Let s and t be any two nodes of S different from v_i, (1 ≤ i ≤ k). Since each v_i, (1 ≤ i ≤ k) is adjacent to both s and t and since d_g (s, v) ≤2, the edge (v, v_i) cannot lie on a geodesic joining s and t.

In Fig. 11, consider the two nodes v and w in S, both of which are of degree less than 5 - 1. Note that the edges (u, y) and (u, x) does not lie on any geodesic joining v and w since the nodes y and x are both adjacent to v and w.

Thus in all three cases it can be seen that the edges (v, v_i), (1 ≤ i ≤ k) do not lie on any geodesic joining a pair of nodes of S, which contradicts the fact that S is an edge geodesic basis of G. Hence |S| = n and so gn_e (G) = n.□

Example 3.24. In the fuzzy graph G : (V, σ, μ) given in Fig. 9, u, w and y are nodes of G having degree 5 - 1 and S = {u, v, w, x, y} = V (G) is the unique edge geodesic cover of G. Surely it contains all nodes of degree 5 - 1.

Remark 3.25. The converse of Proposition 3.23 is false. For the fuzzy graph G containing no δ-arcs given in Fig. 12, S = {u, v, w, x, y, z} = V (G) is an edge geodesic basis of G so that gn_e (G) =6 = n and G has no node of degree n - 1 =6 - 1 =5.

Fig.12

A fuzzy graph on 6 nodes.

Proposition 3.26. Every edge geodesic cover in a connected non-trivial fuzzy graph G : (V, σ, μ) is also a geodesic cover.

Proof. Let G be a connected fuzzy graph and let S be an edge geodesic cover of G. Consider a node v of G and let (u, v) be an edge incident on v. Then clearly the edge (u, v) lies on a geodesic joining some pair of nodes in S. Thus it is obvious that v also lies on a geodesic joining some pair of nodes of S. Since v is arbitrary, it follows that S is a geodesic cover of G. □

Corollary 3.27. For any connected non-trivial fuzzy graph G : (V, σ, μ), gn (G) ≤ gn_e (G).

Proof. Let S be any edge geodesic cover of G with minimum cardinality. Then gn_e (G) = |S|.

By Proposition 3.26, S is also a geodesic cover of G and hence gn (G) ≤ |S|.

Thus gn (G) ≤ gn_e (G). □

Proposition 3.28. For every pair k, n of integers with 2 ≤ k ≤ n, there exists a connected non-trivial fuzzy graph G : (V, σ, μ) on n nodes such that gn_e (G) = k.

Proof. For k = n, the result follows from Proposition 3.20. Also, for each pair of integers with 2 ≤ k < n, there exists a fuzzy tree on n nodes with k fuzzy end nodes containing no δ-arcs. Hence the result follows from Proposition 3.11.□

Remark 3.29. Santhakumaran and John in [36] proved that for a complete bipartite graph G = K_m,n, the edge geodetic number g₁ (G) is as follows:

g₁ (G) =2 if m = n = 1.

g₁ (G) = n if n ≥ 2, m = 1.

g₁ (G) = min {m, n} if m, n ≥ 2.

Note that since all arcs in a complete bipartite fuzzy graph are strong, a similar result for the edge geodesic number is obtained.

Proposition 3.30. Let K_σ₁,σ₂ = (V₁ ∪ V₂, σ, μ) be a complete bipartite fuzzy graph on n nodes. Then

gn_e (K_σ₁,σ₂) =2, if |V₁| = |V₂|=1.

gn_e (K_σ₁,σ₂) = |V₂|, if |V₁|=1 and |V₂|≥2.

gn_e (K_σ₁,σ₂) = min {r, s}, if |V₁| = r and |V₂| = s where r, s ≥ 2.

Proof.

Follows from Proposition 3.20.

Follows from Corollary 3.12.

Let r, s ≥ 2. First assume that r < s.

Let V₁ = {u₁, u₂, . . . , u_r} and V₂ = {w₁, w₂, . . . , w_s} be a partition of K_σ₁,σ₂. Let S = V₁. We prove that S is an edge geodesic cover of K_σ₁,σ₂.

Any edge (u_i, w_j) (1 ≤ i ≤ r, 1 ≤ j ≤ s) lies on the geodesic u_i - w_j - u_k for any k ≠ i so that S is an edge geodesic cover of K_σ₁,σ₂.

Claim: S is an edge geodesic basis of K_σ₁,σ₂.

That is, we prove that S is an edge geodesic cover of K_σ₁,σ₂ having minimum cardinality.

Let T be any set of nodes such that |T| < |S| = r. We show that T is not an edge geodesic cover of K_σ₁,σ₂. Consider the following cases.

Case(1): If T ⊂ V₁, then there exists a node u_i ∈ V₁ such that u_i ∉ T. Then for any edge (u_i, w_j) (1 ≤ j ≤ n), the only geodesics containing (u_i, w_j) are u_i - w_j - u_k (k ≠ i) and w_j - u_i - w_l (l ≠ j) and so (u_i, w_j) cannot lie on a geodesic joining 2 nodes of T. Thus T is not an edge geodesic cover of K_σ₁,σ₂.

Case(2): If T ⊂ V₂, then by a similar argument T is not an edge geodesic cover of K_σ₁,σ₂.

Case(3): If T ⊂ S ∪ V₂ such that T contains at least one node from each of S and V₂, then since |T| < |S|, there exists nodes u_i ∈ V₁ and w_j ∈ V₂ such that u_i ∉ T and w_j ∉ T. Then clearly the edge (u_i, w_j) does not lie on a geodesic connecting two nodes of T so that T is not an edge geodesic cover.

Thus in any case, T is not an edge geodesic cover of K_σ₁,σ₂. Hence S is an edge geodesic basis of K_σ₁,σ₂ so that gn_e (G) = |S| = r.

Now if r = s, we can prove similarly that S = V₁ or V₂ is an edge geodesic basis of K_σ₁,σ₂. □

Example 3.31. Consider the complete bipartite fuzzy graph G given in Fig. 13.

Fig.13

A complete bipartite fuzzy graph.

Here d_g (u, v) =2 and S = {u, v} is an edge geodesic basis of G since (S) _e = E (G) . Hence gn_e (G) =2 = min {2, 3}.

Proposition 3.32. For a fuzzy cycle G on n nodes, the edge geodesic number gn_e (G) = ${\begin{matrix} 2; & when n iseven \\ 3; & when n isodd \end{matrix}$

Proof. Let G : (V, σ, μ) be a fuzzy cycle on n nodes with the node set V = {v₁, v₂, . . . , v_n} , n ≥ 3. Note that all arcs of G are strong [10]. Consider the following two cases:

Case(1): n is even.

Then, for an arbitrary node v_i in G, v_(i+n/2)modn is the g-eccentric node of v_i in G [35]. Also, there are exactly two geodesics between v_i and v_(i+n/2)modn, which together form the fuzzy cycle. So, when S = {v_i, v_(i+n/2)modn}, (S) _e = E (G) and so gn_e (G) =2.

Case(2): n is odd.

In this case, for an arbitrary node v_i in G, v_{(i+(n-1)/2)modn} and v_{(i+(n+1)/2)modn} are the g-eccentric nodes of v_i in G [35]. Also, the v_i - v_{(i+(n-1)/2)modn} geodesic and v_i - v_{(i+(n+1)/2)modn} geodesic together contain all of E (G).

So, taking S = {v_i, v_{(i+(n-1)/2)modn}, v_{(i+(n+1)/2)modn}}, we get (S) _e = E (G) and hence gn_e (G) =3. □

Proposition 3.33. Let G : (V, σ, μ) be a connected non-trivial fuzzy graph containing no δ-arcs and v be a node of G such that N (v) ⊆ N [u] for some u ∈ N (v). Then v belongs to every edge geodesic cover of G.

Proof. Let S be an edge geodesic cover of G and v ∈ V (G). If possible suppose that v ∉ S. Then since u ∈ N (v), the edge (u, v) must lie on a geodesic P joining some pair of nodes say x, y in S. Clearly v ∉ {x, y}. Now let w be a node of P distinct from u and adjacent to v. That is, w ∈ N (v) and since by hypothesis N (v) ⊆ N [u], w must be adjacent to u also, contradicting the fact that P is a geodesic of G. Hence v belongs to every edge geodesic cover of G.□

Proposition 3.34. Let G : (V, σ, μ) be a connected non-trivial fuzzy graph on n nodes containing no δ-arcs. Then edge geodesic number gn_e (G) = n if and only if for each node v of G, N (v) ⊆ N [u] for some u ∈ N (v).

Proof. If for each node v of G, N (v) ⊆ N [u] for some u ∈ N (v), then by Proposition 3.33, v belongs to every edge geodesic cover of G. Since this holds for each node of G, the result follows and so the edge geodesic number gn_e (G) = n.

Conversely suppose that gn_e (G) = n. Assume to the contrary that there exists a node v of G such that N (v) ⊈ N [u] for any node u ∈ N (v). Let S = V - {v}.

Claim: S is an edge geodesic cover of G.

Let (x, y) be an edge of G. If v ∉ {x, y} then x, y ∈ S and so S covers the edge (x, y). On the other hand if v = y(or v = x), then x ∈ N (v)(or y ∈ N (v)). Since by assumption N (v) ⊈ N [x] (or N (v) ⊈ N [y]), there exists a node u ∈ N (v) such that u ∉ N [x] (or u ∉ N [y]). Clearly u ≠ x (or u ≠ y) and so the edge (x, y) lies on the geodesic x - y - u (or u - x - y) where x, u ∈ S (or y, u ∈ S). Thus S is an edge geodesic cover of G and so gn_e (G) ≤ |S| = n - 1, which is a contradiction. Hence the result. □

4 Application of edge geodesic numbers in transporation systems

Transportation plays an important role in developing a countries economic status and growth thus leading to globalization. While it is heavily subsidized by governments of certain countries, good planning of transport is essential to make traffic flow smoothly and at the same time to restrain from loss.

Covering problems are among the fundamental problems in graph theory and some of them have also been introduced in fuzzy graphs such as fuzzy vertex covering problem, fuzzy edge covering problem, fuzzy minimum weight edge covering problem and so on. An important subclass of fuzzy covering problems is formed by path coverings, in particular, coverings with shortest paths or geodesics. A related problem called strong edge geodetic problem was studied by Paul Manuel et al. in [19] which optimizes the number of road inspectors required to maintain the roads in an urban road network.

In this paper, we introduce and study a similar problem that optimizes the number of traffic inspectors required to patrol and inspect the bus routes prevailing in the urban road network and at the same time to identify those routes receiving less priority among passengers and hence eliminate them in order to minimize the loss suffered due to lack of collection by various transport corporations.

Urban road network is modeled by a fuzzy graph whose nodes represent bus depots or stations and edges represent the available bus routes connecting these depots. The membership values of nodes and edges are defined as follows.

4.1 Membership values of nodes

Before introducing the membership values of nodes, a co-related term “depot-capacity” is defined. It indicates the maximum number of buses that can be put in track in a bus depot at a particular time interval. It is denoted by N. This number (N) may not be equal for all bus depots. But it should be pre-determined for a particular bus depot. Thus membership value of a bus depot is defined to be the ratio of the number of buses entering the bus depot to N.

Let V = {D₁, D₂, . . . , D_m} be the available bus depots in a particular urban road network. Let N₁, N₂, . . . , N_m be the depot-capacities of each bus depot respectively.

Define the mapping σ : V ⟶ [0, 1] such that σ (D_k) = ${\begin{matrix} \frac{E_{k}}{N_{k}}; & if Ek≤ Nk \\ 1; & if Ek> Nk \end{matrix}$ (1 ≤ k ≤ m), where E_k denotes the number of buses entering the depot D_k at a particular time interval.

4.2 Membership values of edges

Each edge in an urban road network represents a road segment of a particular bus route. Before defining membership values of edges, a co-related term “satisfied passenger number” is defined.

We take P, a real positive number, as fixed number of passengers. If the number of passengers along a particular bus route is greater than P, the bus route is taken as valuable. This fixed number of passengers is called “satisfied passenger number”. Let μ : V × V ⟶ [0, 1] be a mapping such that

μ (D_i, D_j) = ${\begin{matrix} \frac{p}{P} (σ (D_{i}) \land σ (D_{j})); & if p∈ [0,P] \\ σ (D_{i}) \land σ (D_{j}); & if p> P \end{matrix}$ where p is the number of passengers along a bus route in a particular time interval and P is the satisfied passenger number.

4.3 The patrolling problem

The urban road network is patrolled and the bus routes are inspected by traffic inspectors. Without loss of generality, we assume the network to be a simple graph.

A road patrolling scheme is prepared satisfying the following conditions:

A bus route is a geodesic in the road network.

It is patrolled by a pair of traffic inspectors by stationing one inspector at each end.

δ-arcs in the fuzzy graph representing the urban road network are considered to be bus routes receiving least priority and hence are not considered for patrolling and inspection.

No bus route must be left un-inspected except those receiving least priority (δ-arcs).

The problem is to optimize the number of traffic inspectors required to patrol and inspect the bus routes in the urban road network by satisfying the scheme provided above.

4.4 An example of an urban road network as a fuzzy graph model

Let V = {D₁, D₂, . . . , D₅} be the set of bus depots in the urban road network given in Fig. 14.

The urban road network model is thus illustrated as follows:

Fig.14

An Urban road network model.

Fix “depot-capacity” of each bus depot as N₁, N₂, . . . , N₅ respectively, the values of which are given in column 2 of Table 1, and “satisfied passenger number” as 20 persons per interval of time.

The urban road network is patrolled and the bus routes are inspected by traffic inspectors T₁, T₂, T₃,...etc.

To illustrate our model, we assumed that the bus depots are connected to each other by bus routes as per data given in Tables 1 and 2.

Table 1

Membership value of bus depots in the urban road network

Bus depot	Depot-capacity (N_i)	E_i-values	σ-values
D ₁	30	15	0.5
D ₂	20	25	1
D ₃	25	10	0.4
D ₄	40	34	0.85
D ₅	10	15	1

The σ-values of each depot is evaluated and shown in column 4 of Table 1.

The number of buses entering the depot D₁ per interval of time is 15 and its depot capacity is 30. So $σ (D_{1}) = \frac{15}{30} = 0.5$ .

Similarly, membership values of other depots are calculated.

Now, the membership values of edges are evaluated and given in Table 2.

Table 2

Membership values of edges in the urban road network

Edges	p-values	μ-values
(D₁, D₂)	4	0.1
(D₂, D₃)	14	0.28
(D₃, D₄)	15	0.3
(D₄, D₅)	25	0.85
(D₅, D₁)	16	0.4
(D₁, D₄)	12	0.3
(D₂, D₅)	8	0.4

From Table 2, we see that the number of passengers along the bus route D₁ - D₂ per interval of time is 4 and the satisfying passenger number of the network is 20. So $μ (D_{1}, D_{2}) = \frac{4}{20} (0.5 \land 1) = 0.1$ .

Similarly, membership values of all the other edges in the network are calculated and is given in column 3 of Table 2.

4.5 Optimization using edge geodesic number

Strength between two bus depots depends on how much priority is given by the passengers to the bus route connecting the two. In Fig. 14, the bus route directly connecting the bus depots D₁ and D₂ is receiving the least priority perhaps due to bad road conditions or due to dangerous physical environmental conditions such as forest area, Maoist zone and so on. Thus we do not consider the edge (D₁, D₂) from the urban road network for patrolling and inspection. A patrolling solution for the network of Fig. 14 is thus determined as given below:

T₁, T₂ patrol bus route D₁ - D₅.

T₁, T₃ patrol bus route D₁ - D₄ - D₃.

T₂, T₃ patrol bus route D₅ - D₄ - D₃ and D₅ - D₂ - D₃.

Note that the traffic inspectors T₁, T₂ and T₃ are placed in the bus depots D₁, D₅ and D₃ respectively where {D₁, D₃, D₅} is the edge geodesic basis of the fuzzy graph given in Fig. 14. The edge geodesic number thus helps to identify the minimum number of traffic inspectors required to patrol the urban road network and the fuzziness of the network helps to determine the priority given to each bus route by the passengers. Eliminating bus routes receiving less priority thereby helps transport corporations in minimizing the loss suffered due to lack of collection and also helps in promoting alternate transport facilities.

4.6 The patrolling problem modified

The road patrolling scheme given in section 4.3 is modified by adding a new clause as follows.

One pair of traffic inspectors is not assigned to more than one bus route. However, one traffic inspector is assigned to patrol other bus routes with other inspectors.

The patrolling solution for the optimization problem of the urban road network in Fig. 14 satisfying the modified patrolling scheme is evaluated as follows:

T₁, T₂ patrol bus route D₁ - D₅

T₁, T₃ patrol bus route D₁ - D₄ - D₃.

T₂, T₃ patrol bus route D₅ - D₂ - D₃.

T₂, T₄ patrol bus route D₅ - D₄

The restriction in this scheme is that one pair of inspectors is assigned at most one bus route. In Fig. 14, there are two bus routes of equal geodesic distance between inspectors T₂ and T₃ namely D₅ - D₂ - D₃ and D₅ - D₄ - D₃. However these two inspectors are assigned a single bus route in the patrolling scheme.

Note that here 4 traffic inspectors T₁, T₂, T₃ and T₄ are required, each placed in the bus depots D₁, D₅, D₃ and D₄ respectively where {D₁, D₃, D₄, D₅} is an edge geodesic cover of the fuzzy graph given in Fig. 14. However, it is not an edge geodesic basis.

4.7 Another example

Let V = {D₁, D₂, D₃, D₄, D₅} be the set of bus depots in the urban road network given in Fig. 15.

Fig.15

An urban road network model.

Fix “depot-capacity” of each bus depot as N₁, N₂, . . . , N₅ respectively, the values of which are given in column 2 of Table 4, and “satisfied passenger number” as 15 persons per interval of time. Suppose that the bus depots are connected to each other by bus routes as per data given in Tables 3 and 4.

Table 3

Membership value of bus depots in the urban road network

Bus depot	Depot-capacity (N_i)	E_i-values	σ-values
D ₁	40	25	0.625
D ₂	10	15	1
D ₃	35	20	0.571
D ₄	30	24	0.8
D ₅	20	25	1

The membership values of the edges are evaluated and given in Table 4.

Table 4

Membership values of edges in the urban road network

Edges	p-values	μ-values
(D₁, D₂)	9	0.375
(D₂, D₃)	19	0.571
(D₃, D₄)	20	0.571
(D₃, D₅)	5	0.190
(D₅, D₁)	21	0.625
(D₁, D₄)	17	0.625
(D₁, D₃)	13	0.495

In Fig. 15, bus route directly connecting the bus depots D₁, D₂ and the one connecting D₃, D₅ are δ-arcs and hence the edges (D₁, D₂) and (D₃, D₅) are not considered for patrolling and inspection. A patrolling solution for the network in Fig. 15 is thus determined as follows:

T₁, T₂ patrol bus route D₁ - D₃ - D₂.

T₁, T₃ patrol bus route D₁ - D₄ - D₃.

T₁, T₄ patrol bus route D₁ - D₅.

The traffic inspectors T₁, T₂, T₃ and T₄ are placed at the bus depots D₁, D₂, D₃ and D₅ respectively where {D₁, D₂, D₃, D₅} is the edge geodesic basis of the fuzzy graph given in Fig. 15. Thus the minimum number of traffic inspectors required to patrol the urban road network is the edge geodesic number 4.

5 Conclusion

In this paper, the concept of edge geodesic number of a fuzzy graph is introduced and some of the properties satisfied are discussed. A necessary and sufficient condition for a fuzzy graph to have an edge geodesic cover is established. A comparison between the vertex and edge version of the geodesic number of fuzzy graphs is obtained. The edge geodesic number of fuzzy trees, complete fuzzy graphs, complete bipartite fuzzy graphs and of fuzzy cycles are obtained. The edge geodesic number of fuzzy graphs, depending on the degree of nodes in the fuzzy graphs, are identified. An application of edge geodesic sets in optimizing the number of traffic inspectors patrolling an urban road network is demonstrated. The fuzziness in the problem is used to identify routes receiving less priority among passengers, elimination of which minimizes the loss suffered by various transport corporations due to lack of collection.

Footnotes

Acknowledgment

The first author is grateful to the University Grants Commission (UGC), New Delhi, India, for providing the financial assistance.

References

Al-Hawary

Complete fuzzy graphs, International Journal of Mathematical Combinatorics 4 (2011), 26–34.

Akram

Bipolar fuzzy graphs, Information Sciences 181 (2011), 5548–5564.

Akram

and Dudek

W.A.

Regular bipolar fuzzy graphs, Neural Computing and Applications 21 (2012), 197–205.

Akram

Interval-valued fuzzy line graphs, Neural Computing and Applications 21 (2012), 145–150.

Akram

and Dudek

W.A.

Interval-valued fuzzy graphs, Computers Math Applications 61 (2011), 289–299.

Akram

Bipolar fuzzy graphs with applications, Knowledge-Based Systems 39 (2013), 1–8.

Atici

On the edge geodetic number of a graph, International Journal of Computer Mathematics 80 (2010), 853–861.

Bhattacharya

Some remarks on fuzzy graphs, Pattern Recognition Letters 6 (1987), 297–302.

Bhutani

K.R.

On automorphisms of fuzzy graphs, Pattern Recognition Letters 9 (1989), 159–162.

10.

Bhutani

K.R.

and Rosenfeld

Fuzzy end nodes in fuzzy graphs, Information Sciences 152 (2003), 323–326.

11.

Bhutani

K.R.

and Rosenfeld

Geodesics in fuzzy graphs, Electronic Notes in Discrete Mathematics 15 (2003), 49–52.

12.

Bhutani

K.R.

and Rosenfeld

Strong arcs in fuzzy graphs, Information Sciences 152 (2003), 319–322.

13.

Chartrand

, Harary

and Zhang

On the geodetic number of a graph, Networks 39 (2002), 1–6.

14.

Chartrand

, Harary

and Zhang

Geodetic sets in graphs, Discussiones Mathematicae Graph Theory 20 (2000), 129–138.

15.

Harary

Graph Theory, Addison-Wesley, 1969.

16.

Harary

, Loukakis

and Tsourus

The geodetic number of a graph, Mathematical and Computer Modelling 17 (1993), 89–95.

17.

Kauffman

Introduction a la Theorie des Sous-emsembles Flous, Paris: Masson et Cie Editeurs, 1973.

18.

Linda

J.P.

and Sunitha

M.S.

Geodesic and Detour distances in Graphs and Fuzzy Graphs, Scholars’ Press, 2015.

19.

Manuel

, Klavzar

, Xavier

, Arokiaraj

and Thomas

Strong edge geodetic problem in networks, Open Mathematics 15(1) (2017), 1225–1235.

20.

Rashmanlou

, Pal

, Borzooei

R.A.

, Mofidnakhaei

and Sarkar

Product of interval-valued fuzzy graphs and degree, Journal of Intelligent & Fuzzy Systems 35(6) (2018), 6443–6451.

21.

Mandal

, Sahoo

, Ghorai

and Pal

Genus value of m-polar fuzzy graphs, Journal of Intelligent & Fuzzy Systems 34(3) (2018), 1947–1957.

22.

Mathew

and Sunitha

M.S.

Types of arcs in a fuzzy graph, Information Sciences 179 (2009), 1760–1768.

23.

Moderson

J.N.

Fuzzy line graphs, Pattern recognition Lett 14 (1993), 381–384.

24.

Moderson

J.N.

and Nair

P.S.

Cycles and Cocycles of fuzzy graphs, Information Sciences 90 (1996), 39–49.

25.

Moderson

J.N.

and Nair

P.S.

Fuzzy Graphs and Fuzzy Hypergraphs, Physica-Verlag, Heidelberg, 2000.

26.

Moderson

J.N.

and Yao

Y.Y.

Fuzzy cycles and fuzzy trees, The Journal of Fuzzy Mathematics 10 (2002), 189–202.

27.

Narayan

K.R.S.

and Sunitha

M.S.

Connectivity in a fuzzy graph and its complement, General Mathematics Notes 9 (2012), 38–43.

28.

Mariano

R.E.

and Canoy

S.R.

Edge geodetic covers in graphs, International Mathematical Forum 4 (2009), 2301–2310.

29.

Rosenfeld

Fuzzy graphs, In: Zadeh

L.A.

, Fu

K.S.

and Shimura

(Eds), Fuzzy Sets and their Applications, Academic Press, New York, 1975, pp. 77–95 .

30.

Samanta

and Pal

Fuzzy planar graphs, IEEE Transactions on Fuzzy Systems 23(6) (2015), 1936–1942.

31.

Samanta

and Pal

Fuzzy tolerance graphs, International Journal of Latest Trends in Mathematics 1(2) (2011), 57–67.

32.

Nayeem

SK.MD.Abu.

and Pal

Shortest path problem on a network with imprecise edge weight, Fuzzy Optimization and Decision Making 4(4) (2005), 293–312.

33.

Samanta

and Sarkar

A study on generalized fuzzy graphs, Journal of Intelligent & Fuzzy Systems 35(3) (2018), 3405–3412.

34.

Sarkar

and Samanta

Generalized fuzzy trees, Journal of Computational Intelligence Systems 10 (2017), 711–720.

35.

Sameena

and Sunitha

M.S.

A characterization of g-self centered fuzzy graphs, Journal of Fuzzy Mathematics 16 (2008), 787–791.

36.

Santhakumaran

A.P.

and John

Edge geodetic number of a graph, Journal of Discrete Mathematical Sciences and Cryptography (2013), 415–432.

37.

Somasundaram

and Somasundaram

Domination in fuzzy graphs-I, Pattern Recognition Letters 19 (1998), 787–791.

38.

Sunitha

M.S.

and Vijayakumar

Some metric aspects of fuzzy graphs, Proceedings of the Conference on Graph Connections, CUSAT, Allied Publishers, (1999), pp. 111–114.

39.

Suvarna

N.T.

and Sunitha

M.S.

Convexity and Types of Arcs & Nodes in Fuzzy Graphs, Scholar’s Press, 2015.

40.

Yeh

R.T.

and Bang

S.Y.

Fuzzy relations, fuzzy graphs and their application to clustering analysis, In Fuzzy sets and their Application to Cognitive and Decision Processes, Zadeh

L.A.

, Fu

K.S.

and Shimura

, (Eds), Academic Press, New York, 1975, pp. 125–149.

41.

Zadeh

L.A.

Fuzzy sets, Information and Control 8 (1965), 338–353.

Edge geodesic number of a fuzzy graph

Abstract

Keywords

1 Introduction

2 Preliminaries

3 Edge geodesic number of a fuzzy graph [gn e (G)]

4.1 Membership values of nodes

4.2 Membership values of edges

4.3 The patrolling problem

4.4 An example of an urban road network as a fuzzy graph model

4.6 The patrolling problem modified

4.7 Another example

Footnotes

Acknowledgment

References

3 Edge geodesic number of a fuzzy graph [gn_e (G)]