Fuzzy mixed graphs and its application to identification of COVID19 affected central regions in India

1Introduction

Graph theory is the study of interactions among nodes (or vertices). The idea of graphs was initiated by Euler in 1973 to solve the Konigsberg bridge problem. After that, many branches have been developed. One of the essential branches is to study the mixed graphs where the graphs consider directed and undirected edges both. Let us consider V (non-empty) be a set of elements, called vertices. Also let, E = E₁ ∪ E₂ where E₁ ⊂ V × V is a set of unordered pairs of vertices, i.e., E₁ = {(u, v) |u, v ∈ V}, called a set of undirected edges and E→2⊂V×V is a set of ordered pair of vertices E→2={(a,b)|a,b∈V} , called a set of directed edges. Then G=(V,E1,E→2) is called a mixed graph.

The study of mixed graphs [1] was started in 1970. Sotskov and Tanaev (1976) discussed the colouring of mixed graphs [2]. Liu and Li (2015) introduced Hermitian-adjacency matrices of mixed graphs [3]. Adiga et al. (2016) studied on adjacency matrix [4] of mixed graphs. Mohammed (2017) studied on mixed graph representation and isomorphism [5]. There are many applications of mixed graphs on social networks. For example, Facebook network [6] allow mixed direction, since if one friend follows other, then there will be directed edges in a mentioned direction and there will be an undirected edge if they are friends to each other. Samanta et al. [7] introduced another type of mixed graph, called a semi-directed graph and studied competitions on these graphs.

Sometimes vertices (persons) and the relationship between them may not precisely define. So there may be fuzziness [8, 9] in the graph. The idea of fuzziness to graph theory [10] first introduced by Kauffmann (1973) and after that modification of fuzzy graphs [11] developed by Rosenfeld (1975). The homomorphism, isomorphism, automorphism [12] on fuzzy graphs were developed by Bhutani (1989). The operations [13] like the cartesian product, union, join etc. on fuzzy graphs were studied by Mordeson and Peng (1994). There were various related studies on fuzzy digraphs [14]. Akram and Dubek (2011) introduced interval-valued fuzzy graphs [15] where membership values of vertex and edges are interval. In [16], Akram proposed bipolar fuzzy graphs. There are various studies on bipolar fuzzy graphs [17–19]. The concepts of planer graph [20] under fuzzy environment was introduced by Samanta and Pal (2015). The concepts of the fuzzy environment in food web studied by Samanta and Pal (2013) and represented fuzzy competition graph [21] more realistically. After that, as a generalization of the fuzzy graph, Samanta and Sarkar (2016, 2018) proposed the generalized fuzzy graph [22] and generalized fuzzy competition graph [23]. Akram and Sarwar [24] studied on fuzzy graph structures [25, 26] and applications. More relevant studies on fuzzy graphs can be found in [27–32, 33–40]. The chronological contributions of authors towards fuzzy mixed graphs are presented (Table 1).

Thus there are huge developments on fuzzy graphs which are undirected or directed, but both types of edges not considered in a single graph. The mixed graphs are better to represent some special types of networks where both types of edges occur simultaneously like brain network, research networks, etc. But these networks contain lots of ambiguity. The ambiguity occurs in not only to the connectedness but also to the directedness. One node may strongly dominate to other connected nodes. Thus our main aim is to develop the mixed graph in fuzzy environments where the membership values of vertices, membership values of undirected edges, membership values of directed edges with the value of directedness have been considered. In this study, some operations, completeness, matrices presentation, and isomorphism, competitions on fuzzy mixed graphs are developed. An application of fuzzy mixed graph in a network of COVID19 affected regions in India has been shown.

Therefore the major contributions of this study are pointed out below:

2Fuzzy mixed graph (FMG)

To discuss fuzzy mixed graphs, the definition of fuzzy graphs is given first. Let V be a non-empty set. Then G = (V, σ, μ) is said to be a fuzzy graph if there exists a function μ : V → [0, 1], such that

Definition 2.1. Let V be a non-empty set. Then G = (V, E₁, E₂, μ₁, μ₂, σ, δ) is said to be fuzzy mixed graph if there exist functions σ : V → [0, 1], μ₁ : E₁ → [0, 1] μ₂ : E₂ → [0, 1] , δ : E₂ → [0, 1] such that

In fuzzy graphs, edges are undirected and in fuzzy di-graphs edges are directed with the following property that edge membership values are less than or equal to the minimum of end vertex membership values.

In fuzzy mixed graphs, edges may be both directed and /or undirected with the property that edge membership values are less than or equal to the minimum of end vertex membership values. Additionally, in fuzzy mixed graphs, the measure of directedness is added to directed edges with the property that measure of directedness iless than or equal to the absolute difference of end vertex membership values.

Example 2.2. We consider a graph with four vertices a, b, c, d and nine edges (Fig. 1). All vertices and edges satisfy all the restrictions defined in Definition. 2.1.; hence it is a fuzzy mixed graph.

Fig. 1

Example of a fuzzy mixed graph.

Definition 2.3. A fuzzy mixed walk in a FMG G=(V,E1,E2→,μ1,μ2,σ,δ) is an alternating sequence of vertices and edges v1,e1(ore1→),v2,e2(ore2→),v3,…,ek(or→ek),vk+1 with μ₁ (e_i) >0, or μ2(ei→)>0 , i = 1, 2, ⋯ , k and k is an any positive integer. A fuzzy mixed walk from vertex u to v is said to be a fuzzy mixed path of length m if there exist exactly m edges (directed or undirected) in the walk between the vertices u and v and no vertices, no edges peated, and it is denoted by P(u,v)m . If u = v, then it is called a fuzzy mixed cycle.

Example 2.4. Consider a fuzzy mixed graph (Fig. 1). Here a - b → c ← d is a fuzzy mixed walk and hence a fuzzy mixed path. Also, a - b → c - d → a is a fuzzy mixed cycle.

Definition 2.5. The fuzzy mixed degree FMD (v). of a vertex v in the fuzzy mixed graph G = (V, E₁, E₂, μ₁, μ₂, σ, δ) is defined by

Example 2.6. We consider a fuzzy mixed graph (Fig. 1). The fuzzy mixed degree of a vertex c. is I (c) = (0.3 + 0.5) + (0.6 + 0.6 × 0.2 + 0.5 + 0.5 × 0.2) - (0.6 + 0.6 × 0.1) = 1.46.

Definition 2.7. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) be a fuzzy mixed graph. Then a fuzzy graph H=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) is said to be a fixed subgraph of G if V′⊂V,E1′⊂E1,E2′⊂E2 with σ′ (a) ⩽ σ (a), μ1′(a,b)⩽μ1(a,b) and δ′(a,b→)⩽δ(a,b→) .

Example 2.8. Consider a fuzzy mixed graph H (Fig. 2). Hence it is a fuzzy mixed subgraph of a fuzzy mixed graph G (Fig. 1) as it satisfies all the conditions.

Fig. 2

A z mixed subgraph.

Definition 2.9. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) be a fuzzy mixed graph. Then the order of Gis∑_v∈Vσ (v) and size of G is (∑a,b∈Vμ1(a,b),∑a,b∈Vμ2(a,b→),∑a,b∈Vδ(a,b→)) .

Example 2.10. We consider a fuzzy mixed graph in Fig. 1. Then its order is 2.9, and the size is (2.5, 2.2, 0.7).

3Operations on FMG

Definition 3.1. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then the Cartesian product G × G′ of GandG′. is defined as

where X = V× V′ = { (v, v′) : v ∈ V, v′ ∈ V′ }

Theorem 3.2. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then the Cartesian product G × G′. is also a fuzzy mixed graph.

Proof. Since (μ1×μ1′)(x,u′)(x,v′)=min{σ(x),μ1′(u′v′)}

Similarly, (μ1×μ1′)(u,y)(v,y)⩽min{(σ×σ′)(u,y),(σ×σ′)(v,y)}

Aain,

Similarly (δ×δ′)(u,y)(v,y)→⩽|(σ×σ′)(u,y)-(σ×σ′)(v,y)|

This completes the proof.

Definition 3.3. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then the union G ∪ G′ is defined as G∪G′=(V∪V′,E1∪E1′,E2∪E2′,μ1∪μ1′,μ2∪μ2′,σ∪σ′,δ∪δ′) such that

Theorem 3.4. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then the union G ∪ G′ is also a fuzzy mixed graph.

Proof. Case-I: Let (x,y)∈E1-E1′.

Then (μ1∪μ1′)(x,y)=μ1(x,y)⩽min{σ(x),σ(y)}

                            = min{ (σ ∪ σ′) (x) , (σ ∪ σ′) (y) } if x, y ∈ V - V′.

                           Again (μ1∪μ1′)(x,y)⩽min{σ(x),σ(y)} implies

                            (μ1∪μ1′)(x,y)⩽min{(σ∪σ′)(x),max{σ(y),σ′(y)}

                            = min{ (σ ∪ σ′) (x) , (σ ∪ σ′) (y) } if x ∈ V - V′, y ∈ V ∩ V′

                           (μ1∪μ1′)(x,y)⩽min{σ(x),σ(y)} implies

Case-II: Let (x,y)∈E1′-E1 . Similarly, (μ1∪μ1′)(x,y)⩽min{(σ∪σ′)(x),(σ∪σ′)(y)}

Case-III: Let (x,y)∈E1∩E1′ .

Then (μ1∪μ1′)(x,y)=max{μ1(x,y),μ1′(x,y)}

Case-IV: Let (x,y→)∈E2-E2′ . Similarly as Case-I,

Now, (δ∪δ′)(x,y→)=δ(x,y→)⩽|σ(x)-σ(y)|

Case-V: Let (x,y→)∈E2′-E2 . Similarly as Case-II,

Now (δ∪δ′)(x,y→)=δ′(x,y→)⩽|σ′(x)-σ′(y)|

Case-VI: Let (x,y→)∈ . Similarly as Case-III,

Now (δ∪δ′)(x,y→)=min{δ(x,y→),δ′(x,y→)}⩽min{|σ(x)-σ(y)|,|σ′(x)-σ′(y)|}

This completes the proof.

Definition 3.5. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then the join G + G′ is defined as

G+G′=(V∪V′,E1∪E1′∪E1*,E2∪E2′∪E2*,μ1+μ1′,μ2+μ2′,σ+σ′,δ+δ′) such that

(σ + σ′) (x) = (σ ∪ σ′) (x) for all x ∈ V ∪ V′

Theorem 3.6. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then the join G + G′ is also a fuzzy mixed graph.

Proof. Case-I: Let (x,y)∈E1∪E1′ , then (μ1+μ1′)(x,y)⩽min{(σ+σ′)(x),(σ+σ′)(y)} by Theorem 3.4.

Now, if (x,y)∈E1* then (μ1+μ1′)(x,y)=min{σ(x),σ′(y)}

Case-II: Let (x,y→)∈ E2∪E2′ , then (μ2+μ2′)(x,y→)⩽min{(σ+σ′)(x),(σ+σ′)(y)} by Theorem 3.4.

Now, if (x,y→)∈E2* , then (μ2+μ2′)(x,y→)⩽min{(σ+σ′)(x),(σ+σ′)(y)} , by Case-I.

Case-III: Let (x,y→)∈E2∪E2′ , then (δ+δ′)(x,y→)⩽|(σ+σ′)(x)-(σ+σ′)(y)| , by Theorem 3.4.

Now, if (x,y→)∈E2* , then (δ+δ′)(x,y→)⩽|(σ+σ′)(x)-(σ+σ′)(y)|

This completes the proof.

4Complete FMG

Definition 4.1. If there exist all three types of connections, i.e. out-directed edges, in-directed edges and undirected edges between every pair of vertices in the fuzzy mixed graph G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and

Then the graph is called a complete fuzzy mixed graph.

Example 4.2. A complete FMG is assumed in Fig. 3. Between every pair of vertices, there exist all three types of edges with specified membership values.

Fig. 3

A complete fuzzy mixed graph.

Definition 4.3. A fuzzy mixed graph is called regular if the fuzzy mixed degrees of all vertices are equal. That is FMD (k) = constant, for all k ∈ V.

Note 4.4 Every complete fuzzy mixed graph may not be regular. A fuzzy mixed graph given in Example 4.2 is complete, but it is not regular.

Definition 4.5. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) be a FMG and G′=(V,E′,E″,μ1′,μ2′,σ′,δ′) be a corresponding complete fuzzy mixed graph. The complement of G is denoted as G^c and defined as Gc=(V,E1C,E2C,μ1c,μ2c,σc,δc) where E1C∪E1=E′ and E2C∪E2=E″ such that

Example 4.6. We consider a fuzzy mixed graph G consisting of three vertices {a, b, c}. The membership values of vertices and edges are shown below in Fig. 4. The corresponding complement G^c of G is shown below in Fig. 5.

Fig. 4

A fuzzy mixed graph G

Fig. 5

Complement G^cof G.

Remark 4.7. The complement of a complete fuzzy mixed graph may not always be a null graph.

Theorem 4.8. The complement of the complement of a fuzzy mixed graph is again the same graph. If Gbeafuzzymixedgraphthen (G^c) ^c = G.

Proof. since (σc)c(x)=σc(x)=σ(x),(μ1c)c (x,y)={σ(x)∧σ(y)}-μ1c(x,y)=μ1(x,y) , (μ2c)c(x,y→)={σ(x)∧σ(y)}-μ2c(x,y→)=μ2(x,y→) and (δc)c(x,y→)=|σ(x)-σ(y)|-δc(x,y→)=δ(x,y→) . Thus (G^c) ^c = G .

5Matrix representation of FMG

Two types of matrix representations of a fuzzy mixed graph are described below. One is the adjacency matrix, and another is the incidence matrix.

6Isomorphism on FMG

Definition 6.1. Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then a homomorphism from G to G′ is a mapping f : V → V′ such that

Definition 6.2 Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then G and G′ are said to be isomorphic if there exists a bijective mapping f : V → V′ such that

If G and G′ are isomorphic, then we write G ≅ G′.

Remark 6.3. An isomorphism on fuzzy mixed graphs preserves both the weights of vertices and edges.

Definition 6.4 Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then aweak isomorphism from G to G′ is a bijective mapping f : V → V′ such that

Remark 6.5 A weak isomorphism on fuzzy mixed graphs preserves only the weights of vertices.

Definition 6.6 Let G = (V, E₁, E₂, μ₁, μ₂, σ, δ) and G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) be two fuzzy mixed graphs. Then a co-weak isomorphism from G to G′ is a bijective mapping f : V → V′ such that

Remark 6.7. A co-weak isomorphism on fuzzy mixed graph preserves only the weights of edges.

Theorem 6.8. If any two fuzzy mixed graphs are isomorphic, then their order and size are the same.

Proof. Let f be an isomorphism from G = (V, E₁, E₂, μ₁, μ₂, σ, δ) to G′=(V′,E1′,E2′,μ1′,μ2′,σ′,δ′) . Then the order of a graph G by Definition 6.2 = orderofG′ .

Again, since ∑a,b∈Vμ1(a,b)=∑a,b∈Vμ1′(f(a),f(b)) , ∑a,b∈Vμ2(a,b→)=∑a,b∈Vμ2′(f(a),f(b)→) and ∑a,b∈Vδ(a,b→)=∑a,b∈Vδ′(f(a),f(b))→ , by Definition 6.2.