You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

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

Abstract

In the recent phenomenon of social networks, both online and offline, two nodes may be connected, but they may not follow each other. Thus there are two separate links to be given to capture the notion. Directed links are given if the nodes follow each other, and undirected links represent the regular connections (without following). Thus, this network may have both types of relationships/ links simultaneously. This type of network can be represented by mixed graphs. But, uncertainties in following and connectedness exist in complex systems. To capture the uncertainties, fuzzy mixed graphs are introduced in this article. Some operations, completeness, and regularity and few other properties of fuzzy mixed graphs are explained. Representation of fuzzy mixed graphs as matrix and isomorphism theorems on fuzzy mixed graphs are developed. A network of COVID19 affected areas in India are assumed, and central regions are identified as per the proposed theory.

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 = E1 ∪ E2 where E1 ⊂ V × V is a set of unordered pairs of vertices, i.e., E1 = {(u, v) |u, v ∈ V}, called a set of undirected edges and E2V×V is a set of ordered pair of vertices E2={(a,b)|a,bV} , called a set of directed edges. Then G=(V,E1,E2) 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).

Table 1

Contributions of authors

YearAuthors nameContribution
1970N. V. Lambin and V. S TanaevIntroduction of mixed graph.
1973KaufmannFuzziness to graph theory.
1975RosenfeldModification to fuzzy graph definition.
1994J.N. Mordeson and C.S PengOperations on fuzzy graphs.
1996J. N. Mordeson and P. S. NairFuzzy digraphs and finite state machines.
2016S. Samanta and B. SarkarIntroduced generalized fuzzy graph.
2016C. Adiga et al.Studied on adjacency matrix of mixed graphs.
2020C. Yang and Y. LeeMixed graphs and Facebook network.
2020S. Samanta et al.Introduced a special type of mixed graph, called a semi-directed graph.
This paperK. Das et al.Introduction of fuzzy mixed graph and properties.

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:

  • The fuzzy mixed graphs are introduced as a generalization of mixed graphs.

  • Operations on fuzzy mixed graphs are studied.

  • Adjacency matrices, incidence matrices of fuzzy mixed graphs are presented.

  • Isomorphism with properties of fuzzy mixed graphs is improved.

  • A numerical example of a fuzzy mixed graph in a network of COVID19 affected regions in India has been shown.

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

(1)
μ(x,y)σ(x)σ(y)forall(x,y)V×V,
where σ indicates membership value of vertices, μ indicates the membership value of edges.

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

μ1(x,y)σ(x)σ(y)forall(x,y)E1V×V,
μ2(x,y)σ(x)σ(y)forall(x,y)E2V×V,
δ(x,y)|σ(x)-σ(y)|forall(x,y)E2V×V
where σ indicates membership value of vertex, μ1 indicates membership value of undirected edge, μ2 indicates membership value of directed edge and δ indicates a measure of directedness of directed edge.
  • Note that the measure of directedness is one kind of measure of domination/direction. If two equal powerful nodes are connected, then they may not influence/direct each other. If a low powerful node is connected to a highly powerful node, then the later node can dominate the first one by their power difference. This motivates us to define the measure of directedness as δ(x,y)|σ(x)-σ(y)| for all (x,y)E2V×V .

  • Note that every undirected edge is represented by the value μ1 ∈ [0, 1] only and every directed edge is represented by the value (μ2, δ).

  • The comparison of existing fuzzy graphs and fuzzy mixed graphs is described as follows.

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.

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(orek),vk+1 with μ1 (ei) >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, E1, E2, μ1, μ2, σ, δ) is defined by

FMD(v)=viN(v)μ1(vi,v)+vjN+(v)μ2(v,vJ)[1+δ(v,vJ)]-vkN-(v)μ2(vk,v)[1+δ(vk,vJ)]
where N (u) denotes the neighbourhood of u, N (u) ={ v| (u, v) ∈ E1 }. N+ (u) denotes the out-neighbourhood of u, N+(u)={v|(u,v)E2}. N- (u) denotes the in-neighbourhood of u, N-(u)={v|(v,u)E2} .

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, E1, E2, μ1, μ2, σ, δ) 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 VV,E1E1,E2E2 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.

A z mixed subgraph.

Definition 2.9. Let G = (V, E1, E2, μ1, μ2, σ, δ) be a fuzzy mixed graph. Then the order of Gis∑vVσ (v) and size of G is (a,bVμ1(a,b),a,bVμ2(a,b),a,bVδ(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, E1, E2, μ1, μ2, σ, δ) and G=(V,E1,E2,μ1,μ2,σ,δ) be two fuzzy mixed graphs. Then the Cartesian product G × G′ of GandG′. is defined as

G×G=(X,Y1,Y2,μ1×μ1,μ2×μ2,σ×σ,δ×δ)

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

Y1={(x,u)(x,v):xV,uvE1}{(u,y)(v,y):uvE1,yV}
Y2={(x,u)(x,v):xV,uvE2}{(u,y)(v,y):uvE2,yV}and
(σ×σ)(v,v)=min{σ(v),σ(v)}forall(v,v)X
(μ1×μ1)(x,u)(x,v)=min{σ(x),μ1(uv)}forallxV,uvE1
(μ1×μ1)(u,y)(v,y)=min{μ1(uv),σ(y)}forallxV,uvE2
(μ2×μ2)(x,u)(x,v)=min{σ(x),μ2(uv)}forallxV,uvE2
(μ2×μ2)(u,y)(v,y)=min{μ2(uv),σ(y)}foralluvE2,yV
(δ×δ)(x,u)(x,v)=|σ(x)-μ2(uv)|forallxV,uvE2
(δ×δ)(u,y)(v,y)=|μ2(uv)-σ(y)|foralluvE2,yV

Theorem 3.2. Let G = (V, E1, E2, μ1, μ2, σ, δ) 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(uv)}

min{σ(x),min{σ(u),σ(v)}
=min{min{σ(x),σ(u)},min{σ(x),σ(v)}
=min{(σ×σ)(x,u),(σ×σ)(x,v)}

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

(μ2×μ2)(x,u)(x,v)min{(σ×σ)(x,u),(σ×σ)(x,v)}
(μ2×μ2)(u,y)(v,y)min{(σ×σ)(u,y),(σ×σ)(v,y)}

Aain,

(δ×δ)(x,u)(x,v)=|σ(x)-μ2(uv)|
=|(σ×σ)(x,u)-(σ×σ)(x,v)|

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

This completes the proof.

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

(σσ)(x)=σ(x)ifxV-V
(σσ)(x)=σ(x)ifxV-V
(σσ)(x)=max{σ(x),σ(x)}ifxVV
(μ1μ1)(x,y)=μ1(x,y)if(x,y)E1-E1
(μ1μ1)(x,y)=μ1(x,y)if(x,y)E1-E1
(μ1μ1)(x,y)=max{μ1(x,y),μ1(x,y)}if(x,y)E1E1
(μ2μ2)(x,y)=μ2(x,y)if(x,y)E2-E2
(μ2μ2)(x,y)=μ2(x,y)if(x,y)E2-E2
(μ2μ2)(x,y)=max{μ2(x,y),μ2(x,y)}if(x,y)E2E2
(δ1δ)(x,y)δ(x,y)if(x,y)E2-E2
(δδ)(x,y)δ(x,y)if(x,y)E2-E2
(δδ)(x,y)=min{δ(x,y),δ(x,y)}if(x,y)E2E2

Theorem 3.4. Let G = (V, E1, E2, μ1, μ2, σ, δ) 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

(μ1μ1)(x,y)min{max{σ(x),σ(x)},max{σ(y),σ(y)}}
=min{(σσ)(x),(σσ)(y)}ifx,yVV

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

Case-III: Let (x,y)E1E1 .

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

max{min{σ(x),σ(y)},min{σ(x),σ(y)}}
min{max{σ(x),σ(x)},max{σ(y),σ(y)}}
=min{(σσ)(x),(σσ)(y)}

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

(μ2μ2)(x,y)min{(σσ)(x),(σσ)(y)}

Now, (δδ)(x,y)=δ(x,y)|σ(x)-σ(y)|

|(σσ)(x)-(σσ)(y)|

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

(μ2μ2)(x,y)min{(σσ)(x),(σσ)(y)}

Now (δδ)(x,y)=δ(x,y)|σ(x)-σ(y)|

|(σσ)(x)-(σσ)(y)|

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

(μ2μ2)(x,y)min{(σσ)(x),(σσ)(y)}

Now (δδ)(x,y)=min{δ(x,y),δ(x,y)}min{|σ(x)-σ(y)|,|σ(x)-σ(y)|}

|max{σ(x),σ(x)}-max{σ(y),σ(y)}|=|(σσ)(x)-(σσ)(y)|

This completes the proof.

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

G+G=(VV,E1E1E1*,E2E2E2*,μ1+μ1,μ2+μ2,σ+σ,δ+δ) such that

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

(μ1+μ1)(x,y)=(μ1μ1)(x,y)forall(x,y)E1E1
(μ1+μ1)(x,y)=min{σ(x),σ(y)}forall(x,y)E1*
μ2+μ2(x,y)=(μ2μ2)forall(x,y)E2E2
(μ2+μ2)(x,y)=min{σ(x),σ(y)}forall(x,y)E2
δ+δ(x,y)=(δδ)(x,y)forall(x,y)E2E2
(δ+δ)(x,y)=min{σ(x),σ(y)}forall(x,y)E2*
where E1*andE2* are the set of all edges joining vertices of VandV′ where V∩ V′ = ∅.

Theorem 3.6. Let G = (V, E1, E2, μ1, μ2, σ, δ) 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)E1E1 , 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)}

min{(σσ)(x),(σσ)(y)}=min{(σ+σ)(x),(σ+σ)(y)}

Case-II: Let (x,y) E2E2 , 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)E2E2 , 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, E1, E2, μ1, μ2, σ, δ) and

μ1(x,y)=σ(x)σ(y)forall(x,y)E1V×Vμ2(x,y)=σ(x)σ(y)forall(x,y)E2V×Vδ(x,y)=|σ(x)-σ(y)|forall(x,y)E2V×V

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.

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, E1, E2, μ1, μ2, σ, δ) be a FMG and G=(V,E,E,μ1,μ2,σ,δ) be a corresponding complete fuzzy mixed graph. The complement of G is denoted as Gc and defined as Gc=(V,E1C,E2C,μ1c,μ2c,σc,δc) where E1CE1=E and E2CE2=E such that

σc(x)=σ(x)forallxVμ1c(x,y)={σ(x)σ(y)}-μ1(x,y)forall(x,y)E1Cμ2c(x,y)={σ(x)σ(y)}-μ2(x,y)forall(x,y)E2Cδc(x,y)=|σ(x)-σ(y)|-δ(x,y)forall(x,y)E2C.

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 Gc of G is shown below in Fig. 5.

Fig. 4

A fuzzy mixed graph G

A fuzzy mixed graph G
Fig. 5

Complement Gcof G.

Complement Gcof 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 (Gcc = 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 (Gcc = 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.

5.1Adjacency matrix

To find adjacency matrix of FMG, we define adjacency value ad (vi, vj) of vertex vi with vertex vj where

ad(vi,vj)=(μ1(vi,vj),μ2(vj,vi)[1+δ(vj,vi)],μ2(vi,vj)[1+δ(vi,vj)])

The adjacency matrix is n × n square matrix whose elements are

aij={ad(vi,vj),ifthereisanedgebetweenviandvj(0,0,0),ifthereisnoedgebetweeviand;vj

Now the adjacency matrix of a fuzzy mixed graph (Fig. 1) is given below.

abcd
a(0,0,0)(0.4,0,0)(0.7,0,0)(0.6,0.6,0)
b(0.4,0,0)(0,0,0)(0.5,0,0.72)(0,0,0)
c(0.7,0,0)(0.5,0.72,0)(0,0,0)(0.3,0.6,0.66)
d(0.6,0,0.6)(0,0,0)(0.3,0.66,0.6)(0,0,0)

Observations:

  • i. Non-zero entries of the matrix (at least one component of the entry is non zero) indicate, there are some connections between the corresponding vertices. The connections may be undirected or directed.

  • ii. Zero entries (all components are zero) indicate that there does not exist any edge between the corresponding vertices.

An associated term adjacency number adn (vi, vj) is defined as follows.

adn(vi,vj)=μ1(vi,vj)+μ2(vj,vi)[1+δ(vj,vi)]-μ2(vi,vj)[1+δ(vi,vj)]

5.2Incidence matrix

We define incidence value In (u, v) of the edge ( (u,v),(v,u),(u,v) )) to the vertex u from v as

In(u,v)=(μ1(u,v),μ2(v,u)[1+δ(v,u)],μ2(u,v)[1+δ(u,v)])
aij={In(u,v),ifanedgeincidenttoufromv(0,0,0)ifanedgenotincidenttoufromv

Then the incidence matrix of a fuzzy mixed graph (Fig. 1) is shown below.

(a,b)(b,c)(a,c)(c,d)(a,d)
a(0.4,0,0)(0,0,0)(0.7,0,0)(0,0,0)(0.6,0,0.6)
b(0.4,0,0)(0.5,0.72,0)(0,0,0)(0,0,0)(0,0,0)
c(0,0,0)(0.5,0,0.72)(0.7,0,0)(0.3,0.66,0.6)(0,0,0)
d(0,0,0)(0,0,0)(0,0,0)(0.3,0.6,0.66)(0.6,0.6,0)

Observations:

i Non-zero entries of the matrix (at least one component of the entry is non zero) indicate, there are some connections between the corresponding vertex and edge.

ii Zero entries (all components are zero) indicate that there does not exist any connection between the corresponding vertex and edge.

6Isomorphism on FMG

Definition 6.1. Let G = (V, E1, E2, μ1, μ2, σ, δ) 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

σ(x)σ(f(x))forallxV
μ1(x,y)μ1(f(x),f(y))forallx,yV
μ2(x,y)μ2(f(x),f(y))forallx,yV
δ(x,y)δ(f(x),f(y))forallx,yV

Definition 6.2 Let G = (V, E1, E2, μ1, μ2, σ, δ) 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

σ(a)=σ(f(a))forallaV
μ1(a,b)=μ1(f(a),f(b))forallx,yV
μ2(a,b)=μ2(f(a),f(b))forallx,yV
δ(a,b)=δ(f(a),f(b))forallx,yV.

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, E1, E2, μ1, μ2, σ, δ) 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

σ(a)=σ(f(a))forallaV

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

Definition 6.6 Let G = (V, E1, E2, μ1, μ2, σ, δ) 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

μ1(a,b)=μ1(f(a),f(b))forallx,yVμ1(a,b)=μ2(f(a),f(b))forallx,yVδ(a,b)=δ(f(a),f(b))forallx,yV

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, E1, E2, μ1, μ2, σ, δ) to G=(V,E1,E2,μ1,μ2,σ,δ) . Then the order of a graph G by Definition 6.2 = orderofG′ .

Again, since a,bVμ1(a,b)=a,bVμ1(f(a),f(b)) , a,bVμ2(a,b)=a,bVμ2(f(a),f(b)) and a,bVδ(a,b)=a,bVδ(f(a),f(b)) , by Definition 6.2.

Therefore the size of G is equal to the size of G′.

Theorem 6.9 If any two fuzzy mixed graphs are isomorphic, then fuzzy mixed degrees of their vertices are the same.

Proof. Let f be an isomorphism from G = (V, E1, E2, μ1, μ2, σ, δ) to G=(V,E1,E2,μ1,μ2,σ,δ) . Then the fuzzy mixed degree of a vertex vk ∈ V,

FMD(vk)=vjɛN(vk)μ1(vj,vk)+vjN+(vk)μ2(vk,vj)[1+δ(vk,vj)]-vjN-(vk)μ2(vj,vk)[1+δ(vj,vk)]=f(vj)N(f(vk))μ1(f(vj),f(vk))+fvjN+(f(vk))μ2(f(vk),f(vj))[1+δ(f(vk),f(vj))]-f(vj)N-(f(vk))μ2(f(vj),f(vk))[1+δ(f(vj),f(vk))]

FMD′ (f (vk)) which is the fuzzy mixed degree f (vk) ∈ V′.

This completes the proof.

Theorem 6.10 Two fuzzy mixed graphs are isomorphic if and only if their complements are isomorphic.

Proof. Let G = (V, E1, E2, μ1, μ2, σ, δ) and G=(V,E1,E2,μ1,μ2,σ,δ) be two fuzzy mixed graphs.

Assume G ≅ G′. Then there exists a bijective mapping f : V → Vsuch that

σ(a)=σ(f(a))forallaV
μ1(a,b)=μ1(f(a),f(b))foralla,bV
μ1(a,b)=μ2(f(a),f(b))foralla,bV
δ(a,b)=δ(f(a),f(b))foralla,bV

Now, μ1c(a,b)={σ(a)σ(b)}-μ1(a,b)

={σ(f(a))σ(f(b))}-μ1(f(a),f(b))
=μ1c(f(a),f(b))foralla,bV

Similarly, μ2c(a,b)=μ2c(f(a),f(b)) and δc(x,y)=δc(f(x),f(y)) foralla, b, ∈ V. Thus Gc ≅ Gc. Conversely, let Gc ≅ Gc. Then there exists a mapping h : V → V′ such that

σ(a)=σ(h(a))forallaV
μ1c(a,b)=μ1c(h(a),h(b)),

for all a, b ∈ V

μ2c(a,b)=μ2c(h(a),h(b))foralla,bV
δc(a,b)=δc(h(a),h(b))foralla,bV

Now, μ1c(a,b)=μ1c(f(a),f(b)) implies

{σ(a)σ(b)}-μ1(a,b)={σ(h(a))σ(h(b))}-μ1(h(a),h(b))

Therefore, μ1 (a, b) = μ1′ (h (a) , h (b)) for all a, b ∈ V, since σ (a) = σ′ (h (a)) .

Similarly, μ2(a,b)=μ2(h(a),h(b))foralla,bV δ(a,b)=δ(h(a),h(b))foralla,bV Thus G ≅ G′. This completes the proof.

7Application to the identification of COVID19 affected central regions in India

To identify the central regions through the fuzzy mixed graph, a network of COVID19 affected regions in India are assumed. The data has been shown in Table 2. The node membership values are assumed proportional to the number of affected people in the region. For this case, the membership values are the normalized value of the number of affected people.

Table 2

Collected data of COVID19 in India from official website website https://www.mohfw.gov.in/ dated 12.06.2020

Sr. NoStates (INDIA)Number of COVID19 affected PeopleNode membership values values
1Maharashtra940411
2Tamil Nadu368410.39
3Delhi328100.35
4Telangana41110.04
5Kerala21610.02
6Rajasthan116000.12
7Uttar Pradesh116100.12
8Andhra Pradesh52690.06
9Madhya Pradesh100490.11
10Karnataka60410.06
11Gujarat215210.23
12Haryana55790.06
13Jammu and Kashmir45070.05
14West Bengal93280.1
15Punjab28050.03
16Odisha32500.03
17Bihar57100.06
18Uttarakhand15620.02
19Assam30920.03

The links between any two regions are based on the data collected from www.covid19india.org dated 12th June 2020. The membership values for the links are assumed as per the availability of data of mutual relation between the countries. The default case of the link membership values is the minimum of end vertex membership values. The edge membership values of directed edges are shown as the adjacency matrix in Table 3. Along with this, the measure of directedness has been shown in the same table. Also, the corresponding adjacency number is calculated. The membership values of undirected edges are shown in Table 4.

Table 3

Directed edge membership values of the network in Fig. 6

Directed EdgesMembership valuesMeasure of directednessAdjacency number
(3,2)0.350.040.36
(3,7)0.120.230.15
(3,9)0.110.240.14
(3,13)0.050.30.07
(3,14)0.10.250.13
(3,15)0.030.320.04
(3,17)0.060.290.08
(3,18)0.020.330.03
(3,19)0.030.320.04
(5,2)0.020.370.03
(5,8)0.20.040.21
(5,10)0.020.040.02
(6,1)0.120.880.23
(6,11)0.120.110.13
(10,1)0.060.840.11
(1,7)0.120.880.23
(1,17)0.060.940.12
(1,16)0.030.970.06
(1,14)0.10.90.19
(2,7)0.120.270.15
(2,17)0.060.330.08
(2,16)0.030.360.04
(2,14)0.10.290.13
(11,7)0.120.110.13
(11,17)0.060.170.07
(11,16)0.030.20.0s4
(11,14)0.10.130.11
(1,3)0.350.650.58
(1,6)0.120.880.23
(1,15)0.030.970.06
(1,11)0.230.770.41
(1,5)0.020.980.04
(1,9)0.110.890.21
Table 4

Undirected edge membership values of Fig. 6

Undirected edgesMembership valuesAdjacency number
(u, v)μ1 (u, v)
(3,6)0.320.32
(4,9)0.220.22
(4,16)0.040.04
(7,9)0.220.22
(9,14)0.10.1

To measure central regions of COVID19 affected states, a fuzzy mixed graph is considered with the above-mentioned data. The corresponding fuzzy mixed graphs have been shown in Fig. 6. Centrality measurement is essential in networks. There are lots of centrality measure [41] available in networks, including degree centrality. But degree centrality does not capture the notion of uncertainty and measure of directedness. Degree centrality only counts the direct effects of a directed link. For mixed graphs, degree centrality counts the out-directed links and the undirected links. This study introduces another measure of centrality, namely Fuzzy mixed degree centrality. Fuzzy mixed degree centrality is sum of the adjacency numbers of its adjacent edges. Based on this study, fuzzy mixed degree centrality is equivalent to degree centrality and captures uncertainty perfectly. The Fuzzy mixed degree centralities of all nodes have been shown in Table 5.

Fig. 6

COVID19 affected network in India.

COVID19 affected network in India.
Table 5

Fuzzy mixed degree centrality of selected vertices

Sr. No.States (region)Degree CentralityFuzzy Mixed Degree Centrality
1Maharashtra101.79
2Tamil Nadu40.01
3Delhi100.58
4Telengana20.07
5Kerala30.22
6Rajasthan30.25
7Uttar Pradesh1–0.48
8Andhra Pradesh0–0.21
9Madhya Pradesh3–0.21
10Karnataka10.09
11Gujarat4–0.19
12Haryana00
13Jammu and Kashmir0–0.07
14West Bengal1–0.46
15Punjab0–0.1
16Odisha1–0.11
17Bihar0–0.35
18Uttarakhand0–0.03
19Assam0–0.04

7.1Algorithm

Calculation of fuzzy mixed degree centrality is summarized below.

Step 1: Construct a fuzzy mixed graph where both directed edges and undirected edges present in the network. For the mentioned case, the node membership values are assumed proportional to the number of affected people in the region. For this case, the membership values are the normalized value of the number of affected people. The membership values for the links are assumed as per the availability of data of mutual relation between the countries. The default case of the link membership values is the minimum of end vertex membership values.

Step 2: Adjacency numbers are calculated for each edge. Then fuzzy mixed degree centrality of any vertex is the sum of all the adjacency numbers of all adjacent edges (directed and undirected). Alternatively, the fuzzy mixed degree centrality is calculated by the following formula.

FMD(v)=viɛN(v)μ1(vi,v)+vjN+(v)μ2(v,vj)[1+δ(v,vj)]-vkN-(v)μ2(vk,v)[1+δ(vk,v)]

Notations have their usual meanings.

7.2Result and comparative analysis

In Fig. 7, it is seen that the fuzzy mixed degree may be negative. The values are normalized in this case. Thus the values range between –1 to +1. Higher the values indicate higher the chances to spread COVID19 to others. Similarly, lower fuzzy mixed degree centrality indicates fewer chances to spread the COVID19 to other states. Along with this, degree centrality is shown. For node 1, both the centrality indicates the same. For node 3, the degree centrality is high, but the fuzzy mixed degree centrality is low. This is because the crisp data do not represent the amount of connectedness.

Fig. 7

Comparision of degree centrality and fuzzy mixed degree centrality (on the normalized data).

Comparision of degree centrality and fuzzy mixed degree centrality (on the normalized data).

8Conclusions

This study captured the notion of ‘measure of directedness’ for the first time in the literature. This is the main advantage of this study from previous. How fast the information can be transferred is deduced from this measure of directedness. Several basic properties have been developed. These theories are the backbone of a new branch of fuzzy graph theory, namely as fuzzy mixed graph theory.

Thus this study will be very helpful for future research to introduce the most of fuzzy mixed graph theory topics, i.e. interval-valued fuzzy mixed graphs, generalized fuzzy mixed graphs, fuzzy mixed planar graphs etc. and applicable in many real problems in science and engineering.

References

[1] 

Lambin N.V. and Tanaev V.S. , On a circuit-free orientation of mixed graphs, Dokladi Akademii Navuk BSSR 14 (1970), 780–781.

[2] 

Sotskov Y.N. and Tanaev V.S. , A chromatic polynomial of a mixed graph, Vestsi Akademii Navuk BSSR Seryya Fizika-Matematychnykh Navuk 6 (1976), 20–23.

[3] 

Liu J. and Li X. , Hermitian-adjacency matrices and Hermitian energies of mixed graphs, Linear Algebra Appl 466 (2015), 182–207.

[4] 

Adiga C. , Rakshith B.R. and So W. , On the mixed adjacency matrix of a mixed graph, Linear Algebra and its Applications 495 (2016), 223–241.

[5] 

Mohammed A.M. , Mixed Graph Representation and Mixed Graph Isomorphism, Journal of Science 30(1) (2017), 303–310.

[6] 

Yang C. and Lee Y. , Interactants and activities on Facebook, Instagram, and Twitter: Associations between social media use and social adjustment to college, Applied Developmental Science 24(1) (2020), 62–78.

[7] 

Samanta S. , Muhiudin G. , Alanazi A.M. and Das K. , A mathematical approach on representations of competitions: Competition cluster hypergraphs, Mathematical Problems in Engineering (2020), https://doi.org/10.1155/2020/2517415.

[8] 

Zadeh L.A. , Fuzzy sets, Information Control 8 (1965), 338–353.

[9] 

Zadeh L.A. , Similarity relations and fuzzy orderings, Information Sciences 3(2) (1971), 177–200.

[10] 

Kauffman A. , Introduction a laTheorie des Sous-emsembles Flous, Paris: Masson et Cie Editeurs, (1973).

[11] 

Rosenfeld A. , Fuzzy graphs, Fuzzy Sets and their Applications (L.A. Zadeh, K.S. Fu, M. Shimura, Eds.), Academic Press, New York, (1975), 77–95.

[12] 

Mordeson J.N. and Peng C.S. , Operations on fuzzy graphs, Information Sciences 79 (1994), 159–170.

[13] 

Mordeson J.N. and Nair P.S. , Successor and source of (fuzzy) finite state machines and (fuzzy) directed graphs, Information Sciences 95(1-2) (1996), 113–124.

[14] 

Bhutani K.R. , On automorphism of fuzzy graphs, Pattern Recognition Letter 9 (1989), 159–162.

[15] 

Akram M. and Dudek W.A. , Interval valued fuzzy graphs, Computers and Mathematics with Applications 61 (2011), 289–299.

[16] 

Akram M. , Bipolar fuzzy graphs, Information Sciences (2011). doi:10.1016/j.ins.2011.07.037

[17] 

Poulik S. and Ghorai G. , Detour g-interior and g-boundary nodes in bipolar fuzzy graph with applications, Hacettepe Journal of Mathematics and Statistics 49(1) (2020), 106–119.

[18] 

Poulik S. and Ghorai G. , Certain indices of graphs under bipolar fuzzy environment with applications, Soft Computing 24(7) (2020), 5119–5131.

[19] 

Sarwar M. and Akram M. , Bipolar fuzzy circuits with applications, Journal of Intrelligent and Fuzzy Systems 34(1) (2018), 547–558.

[20] 

Samanta S. and Pal M. , Fuzzy planar graphs, IEEE Transaction on Fuzzy Systems (2015). Doi: 528.10.1109/TFUZZ.2014.2387875

[21] 

Samanta S. and Pal M. , Fuzzy k-competition graphs and p-competition fuzzy graphs, Fuzzy Information and Engineering 5 (2013), 191–204.

[22] 

Samanta S. , Sarkar B. , Shin D. and Pal M. , Completeness and regularity of generalized fuzzy graphs, Springer Plus 5 (2016).

[23] 

Samanta S. and Sarkar B. , Representation of competitions by generalized fuzzy graphs, International Journal of Computational Intelligence System 11 (2018), 1005–1015.

[24] 

Sitara M. , Akram M. and Bhatti M.Y. , Fuzzy graph structures with applications, Mathematics 7(1) (2019), 63.

[25] 

Akram M. , Sitara M. and Saied A.M. , Residue product of fuzzy graph structures, Journal of Multiple-Valued Logic and Soft Computing 34 (2020), 365–399.

[26] 

Akram M. and Sitara M. , Certain fuzzy graph structures, Journal of Applied Mathematics and Computing 61 (2019), 25–56.

[27] 

Sarwar M. and Akram M. , Certain algorithms for modelling uncertain data using fuzzy tensor product Bezier surfaces, Mathematics 6(3) (2018), 42.

[28] 

Sarwar M. , Akram M. and Alshehri N.O. , A new method to decision-making with fuzzy competition hypergraphs, Symmetry 10(9) (2018), 404.

[29] 

M. Akram, M. Sarwar, and R.A. Borzooei, A novel decision making approach based on hypergraphs in intuitionistic fuzzy environment, Journal of Intelligent and Fuzzy Systems 35(2) (2018), 1905–1922.

[30] 

M. Sarwar, Decision-making approaches based on color spectrum and D-TOPSIS method under rough environment, Computational and Applied Mathematics (2020), DOI: 10.1007/s40314-020-01284-7.

[31] 

M. Sarwar, M. Akram and U. Ali, Double dominating energy of m-polar fuzzy graphs, Journal of Intelligent and Fuzzy Systems 38(2) (2020), 1997–2008.

[32] 

Akram M. , Sarwar M. and Dudek W.A. , Graphs for the analysis of bipolar fuzzy information, Studies in Fuzziness and Soft Computing, 2020, Springer, DOI10.1007/978-981-15-8756-6.

[33] 

Naseem U. , Musial K. , Eklund P. and Prasad M. , Biomedical Named-Entity Recognition by Hierarchically Fusing BioBERT Representations and Deep Contextual-Level Word-Embedding, International Joint Conference on Neural Networks (2000), 1–8.

[34] 

Naseem U. , Razzak I. , Eklund P. and Musial K. , Towards Improved Deep Contextual Embedding for the identification of Irony and Sarcasm, International Joint Conference on Neural Networks (2020), 1–7.

[35] 

Naseem U. , Razzak I. , Musial K. and Imran M. , Transformer based deep intelligent contextual embedding for twitter sentiment analysis, Future Generation Computer Systems 113 (2020), 58–69.

[36] 

Khan S.K. , Farasat M. , Naseem U. and Ali F. , Performance Evaluation of Next-Generation Wireless (5G) UAV Relay, Wireless Personal Communications (2020), 1–16.

[37] 

Naseem U. , Khan S.K. , Razzak I. and Hameed I.A. , Hybrid words representation for airlines sentiment analysis, Australasian Joint Conference on Artificial Intelligence (2019), 381–392.

[38] 

Khan S.K. , Farasat M. , Naseem U. and Ali F. , Link-level Performance Modelling for Next-Generation UAV Relay with Millimetre-Wave Simultaneously in Access and Backhaul, Indian Journal of Science and Technology 12(39) (2019), 1–9.

[39] 

S.K. Khan, A. Al-Hourani, and K.G. Chavez, Performance evaluation of amplify-and-forward UAV relay in millimeter-wave, in 2020 27th International Conference on Telecommunications (ICT), 2020, pp. 1–5.

[40] 

S.K. Khan, Performance evaluation of next generation wireless UAV relay with millimeter-wave in access and backhaul, Master Thesis, School of Engineering, RMIT University, Melbourne, Australia, 2019.

[41] 

Das K. , Samanta S. and Pal M. , Study on centrality measures in social networks: A survey, Social Network Analysis and Mining 8(13) (2018), 1–11.