Zero forcing number of fuzzy graphs with application

Abstract

We introduce and study forcing number for fuzzy graphs. Also, we compute zero forcing numbers for some classes of graphs and extend this concept to fuzzy graphs. In this regard we obtain upper bounds for zero forcing of some classes of fuzzy graphs. We will proceed to obtain a new algorithm to computing zero forcing set and finding a formula for zero forcing number, and by some examples we illustrate these notions. Finally, we introduce some applications of fuzzy zero forcing in medical treatments.

Keywords

Fuzzy graph zero forcing number path cover number block graph multipartite graphs

1 Introduction

Let G^* be a graph with all vertices initially colored either black or white. If u is a black vertex of G^* and u has exactly one neighbor that is white, say v, then we change the color of v to black; this rule is called the color change rule. In this case we say “u forces v” which is denoted by u → v. The procedure of coloring a graph using the color rule is called the zero forcing process. This parameter was first introduced and defined at the workshop “Spectra of Families of Matrices described by Graphs, Digraphs, and Sign Patterns”, which was held at the American Institute of Mathematics on October, 2006 [1].

The zero forcing process is the same as graph infection used by physicists to study control of quantum systems and the zero forcing number Z (G^*) is becoming a graph parameter of interest in its own right [8]. The zero forcing number is a useful tool for determining the minimum rank of structured families of graphs and small graphs, and is motivated by simple observations about null vectors of matrices [2, 3]. In [16] some results for characterizations of graphs with very high or very low zero forcing numbers were given and the zero forcing number of a graph according to the cut-vertex reduction was given. Also, an algorithm to computing the zero forcing number of a unicyclic graph was introduced. It is also shown that the zero forcing number of a unicyclic graph is equal to the path cover number of the graph. In [9] some results related to path edge spread and cut-edge reduction for zero forcing number were obtained and it is shown zero forcing number equals path cover number for any cactus, and zero forcing numberis equals to the maximum nullity for a restricted family of cacti. In [11] zero forcing number for corona was computed and some bounds for the lexicographic product of graphs were given.

Recently, zero forcing polynomial of a graph G^* of order n, as the polynomial $Z (G^{*}; x) = \sum_{i = 1}^{n} z (G^{*}; i) x^{i}$ , where z (G^* ; i) is the number of zero forcing sets of G^* of size i, introduced and studied in [6]. Also, they characterized the extremal coefficients of Z (G^* ; x), derived closed form expressions for the zero forcing polynomials of several families of graphs, and exploreed various structural properties of Z (G^* ; x), including multiplicatively, unimodality and uniqueness.

As it is well known fuzzy graphs are a very rich topics of applied mathematics, computer science, social sciences, medical sciences, engineering, etc. The notion of fuzzy graphs was introduced by A. Rosenfield in 1975 [15]. The operations union, join, cartesian product, and composition on two fuzzy graphs were defined by J. N. Mordeson and Peng [13]. Lately, determined the degree of vertices in the new fuzzy graphs obtained from two fuzzy graphs using the operations cartesian, tensor, normal product, and composition on two fuzzy graphs. Lately, Borzooei and co-authors studied on fuzzy labbeling graphs [5] and Zhan and coauthor study on the new parameter for fuzzy graphs [18, 19].

The purpose of this paper is to study of forcing number for fuzzy graphs, as a generalization of forcing number of graphs. In this regard, we compute zero forcing numbers for some classes of graphs and extend these results for fuzzy graphs. We will proceed to obtain upper bound for zero forcing numbers of some classes of fuzzy graphs. As the most important achievement, we give a new algorithm to obtaining zero forcing set and obtain a formula to computing zero forcing numbers. Finally, we introduce some applications of fuzzy zero forcings in medical treatments. Therefore, the paper has been organized into four sections as the following:

In Section 2, briefly, some notions and results of graph theory, which we need to develop our paper, were introduced. In Section 3, zero forcing number for some classes of graphs was computed and zero forcing number has been extended to fuzzy graphs. Also, upper bounds of zero forcing numbers for some class of graphs was obtained and a new algorithm to computing zero forcing sets and a formula to obtaining the zero forcing numbers were given. Finally, in Section 4, some applications of zero forcing numbers for fuzzy graphs in medical treatments are introduced.

2 Preliminaries

A graph G^* = (V, E) consists of a vertex set V and an edge set E of two-element subsets of V. The order of G^* is denoted by n = |V|. Two vertices v, w ∈ V are adjacent, or neighbors, if {v, w} ∈ E; we will write v ∼ w if v and w are adjacent. The neighborhood of v ∈ V is the set of all vertices which are adjacent to v, denoted by N (v ; G^*); the degree of v ∈ V is defined as d (v ; G^*) = |N (v ; G^*) |. The closed neighborhood of v is the set N [v ; G^*] = N (v ; G^*) ∪ {v}. The minimum degree and maximum degree of G^* are denoted by δ (G^*) and ▵ (G^*), respectively.

A block graph or clique tree is a type of undirected graph in which every biconnected component (or block) is a clique. A block-cycle graph is a graph in which every block is either an edge or a cycle. A block cycle graph with only one cycle is a unicyclic graph.

A path cover of a graph G^* is a set of vertex disjoint induced paths that cover all the vertices of G^*. The path cover number of a graph G^*, P (G^*), is the minimum size of a path cover. In general, path cover number is a lower bound for zero forcing number [12]. A hamiltonian path(or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.

The notion of a zero forcing set, as well as the associated zero forcing number, of a simple graph for a numerous families of graphsintroduced and studied in [1]. Assume that each vertex of a graph G^* has one of two colors, black and white for the convention. Let S denote the (initial) set of black vertices of G^*. The color-change rule converts the 1 color of a vertex from white to black if the white vertex u₂ is the only white neighbor of a black vertex u₁; we say that u₁ forces u₂, which we denote by u₁ → u₂. And a sequence, u₁ → u₂ → . . . → u_i → u_i+1 → . . . → u_t, obtained through iterative applications of the color-change rule is called a forcing chain. Note that, at each step of the color change, there may be two or more vertices capable of forcing the same vertex. The set S is said to be a zero forcing set of G^* if all vertices of G^* will be turned black after finitely many applications of the color-change rule. The zero forcing number of G^*, denoted by Z (G^*), is the minimum of |S| over all zero forcing sets S ⊆ V (G^*) .

Furthermore, the paths in any minimal path covering of G^* are precisely, the forcing chains in a minimal zero forcing process initiated by an appropriate selection of the end-points of the paths in this collection.

Theorem 2.1. [3] For any graph G^*, P (G^*) ≤ Z (G^*) .

Theorem 2.2. [2] For any tree T, P (T) = Z (T).

Theorem 2.3. [16] Let G^* be an unicyclic graph, then Z (G^*) = P (G^*).

Theorem 2.4. [3] If G^* is a connected graph of order greater than one, then $⋂_{Z \in ZFS (G^{*})} Z = \emptyset,$ where ZFS (G^*) is the set of all minimum zero forcing sets of G^*.

In the graph theory, the girth g of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (i.e. it is an acyclic graph), its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

A fuzzy graph G = (σ, μ) on graph G^* = (V, E) is a pair of functions σ : V → [0, 1] and μ : V × V → [0, 1] such that μ (uv) ≤ σ (u) ∧ σ (v), for all u, v ∈ V and σ (u) ∧ σ (v) indicates the minimum among σ (u) and σ (v) (see [10]). The degree of a vertex v defined by d (v) = ∑_u≠vμ (v, u), and the order of G is defined to be O (G) = ∑_u∈vσ (v). The size of G is defined to be S (G) = ∑_u≠vμ (u, v). Complement of a fuzzy graph has been defined by J. Mordeson [14]. Complement of fuzzy graph G = (σ, μ) as a fuzzy graph G^c = (σ^c, μ^c) where σ^c (v) = σ (v) and μ^c (u, v) =1 - μ (u, v) .

3 Zero forcing number for some classes of fuzzy graphs

In recent years many researcher work on zero forcing sets. Bozeman in [7] studied connections to zero forcing: Tree covers and power domination. Borzooei and et al considered on fuzzification of zero forcing process in [4]. In this section, we introduce the concept of fuzzy zero forcing number and compute for fuzzy block graphs and m-parties fuzzy graphs and obtain an upper bound of zero forcing numbers for fuzzy graphs with girth g and the connected fuzzy graphs. In the end we present a new algorithm to computing zero forcing sets, and give the formula to obtain zero forcing numbers.

Definition 3.1. Let G = (σ, μ) be a fuzzy graph on G^*. Let S = { S_i } _i∈I be the family of all zero forcing sets of G^*. Then the zero forcing number of fuzzy graph G is define as follows: $Z (G) = \underset{S_{i}, i \in I}{⋀} (\sum_{v_{i} \in S_{i}} σ (v_{i})) .$

Example 3.2. In Fig. 1, S = {{a, b} , {b, c} , {a, c} , {a, d} , {b, d} , {b, e} , {a, e}}, is the family of all zero forcing sets of G^*. The set {a, d} has minimum zero forcing number and Z (G) =0.1 + 0.2 = 0.3 .

Fig. 1

Fuzzy graph of C5.

Let G^* be a connected block graph. Define cut tree of G^*, denoted by T (V_T, E_T), by V_T = {B₁, …, B_i, v₁, …, v_j}. By B_i = {v ∈ V|νisnotacut - vertex} denotes ablock, and cut vertices are subscription of blocks in graph. It should be noted that a block-vertex in the cut tree can be empty. Also, define a root vertex among of {v₁, …, v_j}, such that the cut vertices has maximum degree.

Let T be a tree rooted of graph G^* at v₁ and v is a vertex of T. Then the level number of v, denoted by l (v), is the length of the unique v₁ - v path in T. If a vertex u of T is adjacent to v and l (u) > l (v), then u is called a child of v and v is the parent of u. A vertex w is a descendant of v and v is an ancestor of w (if the level numbers of the vertices on the v - w path are monotonically increasly)(for more details see [17]). Let C (v) be the set of descendants of v, and define C [v] = C (v) ∪ {v}. Then the maximal subtree of T rooted at v is the subtree of T induced by C [v] and is denoted by T_v.

Example 3.3. In Fig. 2, a block graph and corresponding refined cut tree T is shown by a root vertex with block-vertices: $\begin{matrix} B_{2} = B_{4} = B_{5} = B_{7} = B_{8} = B_{10} = B_{12} = \emptyset, \\ B_{1} = {v_{10}}, B_{3} = {v_{15}}, B_{6} = {v_{4}}, \\ B_{9} = {v_{13}} B_{11} = {v_{20}}, B_{13} = {v_{1}, v_{2}}, \\ B_{14} = {v_{5}, v_{9}}, B_{15} = {v_{23}, v_{24}}, \\ B_{16} = {v_{18}} B_{17} = {v_{22}}, B_{18} = {v_{25}, v_{26}} . \end{matrix}$

Fig. 2

(a) A block graph with one root. (b) Cut tree of G.

In Fig. 6, a block graph with five blocks: $\begin{matrix} B_{1} = {a, b, d}, B_{2} = {c, e}, B_{3} = {d, e}, \\ B_{4} = {d, g, h}, B_{5} = {e, f, i, j} . \end{matrix}$ The corresponding cut tree of G^* is $\begin{matrix} B_{1} = {a, b}, B_{2} = {C}, B_{3} = \emptyset, B_{4} = {g, h}, \\ B_{5} = {f, i, j} . \end{matrix}$

At this state we are ready to finding zero forcing number for block fuzzy graphs.

Theorem 3.4. Let G = (σ, μ) be a fuzzy graph on block graph G^*. Then $Z (G) = \sum_{P_{j} = v_{j_{1}} - v_{j_{n_{j}}}, j \in J} (σ (v_{j_{1}}) \land σ (v_{j_{n_{j}}})),$ such that v_{j
₁} and v_{j
_n} are the first vertex and last vertex in any path P_j, where P = { P_j } _j∈J is the set of all paths covering of G^*.

Proof. By Theorem 2.1, for any graph G^*, we have P (G^*) ≤ Z (G^*). Assume that P (G^*) < Z (G^*). Then by cut tree of G^* instead of G^*, there is a vertices set S = {v₁, v₂, . . . , v_t}, such that it is not involved in the set of first-points or end-points in any path of path covering of G^*. Then any v_i can be in one of these cases:

v_i is in a pendent block:

v_i is in the edge uv_i, that u is in an end-point of P and u is only connected to v_i, so connection u to v_i does not change the path cover number of the graph, and the paths in path cover P are the forcing chains of the forcing process initiated by the first-points of the paths in P. Therefore, the zero forcing process will be continued by using v_i to force u, or assume v_i is an end point of P since u is only neighbor of v_i it can be colored by u and need not be primitive black vertex, which is a contradiction.

Assume that v_i of B is a pendant cycle. Then since at least two paths are needed to cover the vertices of a cycle, we get that v_i is in one of two paths and it can be forced by one of neighbors and need not be primitive black vertex, which is a contradiction.

v_i is in an inner block.

Assume v_i is in inner edge uv_i. Then there is a path P in path covering of G, such that P contains v_i. Thus, the zero forcing process will be continued by using v_i to force u, and so v_i can be colored by one of neighbors and need not be primitive black vertex, which is a contradiction.

Let v_i be in an inner cycle and u, w be two neighbors of v_i, since any cycle will be covered by two paths, then u, w can be colored by first vertex in two paths of P. So the zero forcing process will be continued by using v_i to force u, or w and need not be primitive black vertex. Hence, in two cases, members of zero forcing set are first or last vertex in path covering of G. Then $Z (G) = \sum_{P_{j} = v_{j_{1}} - v_{j_{n_{j}}}, j \in J} (σ (v_{j_{1}}) \land σ (v_{j_{n_{j}}})) .$ □

Theorem 3.5. Let G^* be a finite graph of order n, size m and G = (σ, μ) be a fuzzy graph on G^*. If G^* is a Hamiltonian cycle, then Z (G^*) can be counted as follows: $Z (G^{*}) = {\begin{matrix} n - 2 \\ n - 3 \\ n - 4 \\ ⋮ \\ n - (n - 2) \end{matrix} \begin{matrix} n (n - 1) - 2 c_{1} \leq D (G^{*}) \leq n (n - 1) - 2 \\ n (n - 1) - 2 (c_{1} + c_{2}) \leq D (G^{*}) \leq n (n - 1) - 2 c_{1} \\ n (n - 1) - 2 (c_{1} + c_{2} + c_{3}) \leq D (G^{*}) \leq n (n - 1) - 2 (c_{1} + c_{2}) \\ ⋮ \\ n (n - 1) - 2 (c_{1} + \dots + c_{n - 3}) \leq D (G^{*}) \leq n (n - 1) - 2 (c_{1} + c_{2} + \dots + c_{n - 4}) \end{matrix}$ where, c_i are summand in a specific partitions of $\frac{n (n - 3)}{2}$ and D (G^*) express for sum of degrees in graph.

Proof. In a complete graph K_n, every vertex has n - 1 degrees that two edges are in cycle and the rest of edges are inner edges. So, there are $\frac{n (n - 3)}{2}$ inner edges. In this regards, every graph that has a

Hamiltonian cycle is a subgraph of K_n. Then we have the relation $Z (C_{n}) \leq Z (G^{*}) \leq Z (K_{n}) .$ Thus, to computing of Z (G^*) in this class of graphs, we find a relationship between deleting edge and changing of Z (G^*) in comparison with Z (K_n).

Let u₁ ∈ V (G). Then we delete n - 3 inner edges connected to u₁, respectively. Thus, we observe that in zero forcing set, only one vertex decrease and zero forcing number change to Z (G^*) = n - 2 .

We continue this process by deleting every inner edge for one of neighbors of u₁. In this case, we delete (n - 2) inner edges and zero forcing number change to Z (G^*) = n - 3. By continuing this method for other vertices until another neighbor of u₁, we delete all of inner edges, then in each time zero forcing number, one vertex decreases.

Given that there are $\frac{n (n - 3)}{2}$ inner edges and by deleting c_i edges, zero forcing set is fix, we show this changes in zero forcing number by this specific partition of $\frac{n (n - 3)}{2}$ as below: $\begin{matrix} \underset{c_{1}}{\underset{︸}{(n - 3)}} + \underset{c_{2}}{\underset{︸}{(n - 2)}} + \underset{c_{3}}{\underset{︸}{(n - 4)}} + \dots + \underset{c_{n} - 4}{\underset{︸}{(3)}} + \underset{c_{n} - 3}{\underset{︸}{(2)}} \\ = \frac{n (n - 3)}{2} . \end{matrix}$ Note that, edge deletion in any case that 1 ≤ m ≤ c_i, causes no any change in zero forcing set. It is clear that by deleting c₁ edges of complete graph K_n, we have Z (G^*) = Z (K_n) -1. Then any class of subgraphs of K_n, such that that sum of degrees D (G^*) are located in these span, its zero forcing number is computed as follows: $Z (G^{*}) = {\begin{matrix} n - 2 \\ n - 3 \\ n - 4 \\ ⋮ \\ n - (n - 2) \end{matrix} \begin{matrix} n (n - 1) - 2 c_{1} \leq D (G^{*}) \leq n (n - 1) - 2 \\ n (n - 1) - 2 (c_{1} + c_{2}) \leq D (G^{*}) \leq n (n - 1) - 2 c_{1} \\ n (n - 1) - 2 (c_{1} + c_{2} + c_{3}) \leq D (G^{*}) \leq n (n - 1) - 2 (c_{1} + c_{2}) \\ ⋮ \\ n (n - 1) - 2 (c_{1} + c_{2} + \dots + c_{n - 3}) \leq D (G^{*}) \leq n (n - 1) - 2 (c_{1} + c_{2} + \dots + c_{n - 4}) \end{matrix}$ □ Example 3.6. The corresponding zero forcing numbers for inducing subgraphs of K₇ by deleting edges in c_i (1 ≤ i ≤ 4) groups computing by Theorem 3.5 is shown in Table 1.

Table 1

Zero forcing set for subgraphs of K₇ by deleting c_i groups of edges

Lemma 3.7. Let G^* be a bipartite graph K_n,n. Then Z (G^*) =2 (n - 1) .

Proof. Suppose black vertex u₁ is in part one of biparties graph K_n,n and u₁ adjoin by n white vertices in other part of graph. Then by attention to zero forcing process, one vertex in second part of vertices must be white and rest of them must be black. Thus vertices in part two are black. On the other side, n - 1 vertices in part one have n degrees.

Hence, by zero forcing law, one vertex, in this part, can be white, so Z (G^*) =2 (n - 1) .□

For more understanding the following results, first see Fig. 3.

Fig. 3

Zero forcing set for k_n,n.

Theorem 3.8. Let G^* be a bipartite graph K_n,n and G = (σ, μ) be a fuzzy graph on G^*. Then Z (G) =2O (G) - (σ (u) + σ (υ)), where u, v ∈ V with maximum values in G.

Proof. By Lemma 3.7, the proof is clear.□

Lemma 3.9. Let G^* be a m-partite graph K_n,n,...,n. Then Z (G^*) = mn - 2.

Proof. Let black vertex u₁₁ be in the first partition of vertex of graph. Then u₁₁ has (m - 1) n neighbors and so by zero forcing law, (m - 1) n - 1 vertices must be black and one vertex must be white that can be black by u₁₁. So, we find mn - n black vertices in zero forcing set. Suppose u_nm is white and colored by u₁₁. Thus u_nm is connected to (n - 1) vertices of first partition. By zero forcing law, one vertex can be white and the rest of them must be black. Then we find n - 2 black vertices for zero forcing set, and so Z (G^*) = (mn - n) + (n - 2) = mn - 2, as desired.□

For more understanding the following results, first see Fig. 4.

Fig. 4

Zero forcing set for k_n,n,...,n.

Theorem 3.10. Let G^* be a m-partite and G = (σ, μ) be a fuzzy graph on G^*. Then $Z (G) = mO (G) - (σ (u) + σ (υ)),$ where u, v ∈ V with maximum values in G.

Proof. By Lemma 3.9, the proof is clear.□

Lemma 3.11. Let G^* be an m-partite graph and G^* = K_{α₁,α₂,...,α_n}. Then $Z (G^{*}) = \sum_{i = 1}^{n} α_{i} - 2$ .

Proof. Suppose black vertex u₁₁ is in first part of graph G^* and it is adjoin by $\sum_{i = 2}^{n} α_{i} - α_{1}$ vertices. Then by zero forcing law, $\sum_{i = 2}^{n} α_{i} - α_{1} - 1$ vertices are black and one vertex is white. We show this vertex by u_mn in end part of G^*. On the other hands, one obtains that u_mn adjoin to all of vertices α₁ to α_n-1, and every vertex in α₂ to α_n-1 is black, so by zero forcing law, there exists just one vertex that can be white in α₁ and the rest of them must be black. Hence $Z (G^{*}) = \sum_{i = 1}^{n} α_{i} - 2 .$ □

For more understanding the following results, first see Fig. 5.

Fig. 5

Zero forcing set for K_{α₁,α₂,...,α_n}.

Theorem 3.12. If G = (σ, μ) is a m-partite graph K_{α₁,α₂,...,α_n} by n vertices and order O (G) on a crisp graph G^*, then $Z (G) = mO (G) - (σ (v) - σ (u)),$ such that u, v are vertices with maximum values.

Proof. By Lemma 3.9, the proof is clear.□

Theorem 3.13. Let G = (σ, μ) be a fuzzy graph on G^* with girth g and order O (G). Then $Z (G) \leq O (G) - g - 2 .$

Proof. Let G be a graph with girth g and C be the set of vertices realizing the girth of G, that induce a cycle. We color the cycle by 2 vertices, so every vertex in neighbors of C can be in zero forcing set in G ∖ C and every vertex of cycle are inactive for zero forcing set of G. On the other hand, for any vertex σ (v) ≤1, Then Z (G) ≤ O (G) - g - 2.□

Theorem 3.14. Let G^* be a fuzzy graph on G^* = (V, E), and $\bar{G} = (σ, \bar{μ})$ be a complement of G. If |V| ≥ 4 and $G, \bar{G}$ are connected fuzzy graphs, then Z (G) ≤ O (G) -3.

Proof. Let G and $\bar{G}$ be connected graphs. Since G and $\bar{G}$ are connected, then any vertex has at most n - 2 neighbors.

Let G has a vertex u₁ with n - 2 neighbors exactly. Suppose V (G) = V₁ ∪ V₂ and V₁ ={ u₁, u₂ } and V₂ ={ v_i|1 ≤ i ≤ n - 2 } and N_G (u₁) = V₂. If for (1 ≤ j ≤ n - 2) , u₂v_j ∈ E (G), then G has a bipartite fuzzy subgraph K_2,n-2, which is a contradiction, thatb G and $\bar{G}$ are connected. Then thereexist 1 ≤ j ≤ n - 2, u₂v_j ∉ E (G). Suppose that N_G (u₂)∩ V₂ = { v_i|1 ≤ i ≤ k } for some k < n - 2. If v_iv_j ∈ E (G) , 1 ≤ i ≤ k, k + 1 ≤ j ≤ n - 2, then G has a bipartite subgraph K_k,n-k. Thus $\bar{G}$ is disconnected. Hence, there are v_x and v_y, such that v_xv_y ∉ E (G), where 1 ≤ x ≤ k and k + 1 ≤ y ≤ n - 2. We rename v_xv_y = v_kv_n-2 ∉ E (G), then V (G)∖ { u₁, v_k, v_n-2 } is a zero forcing set for G and u₂ → v_k → u₁ → v_n-2 is a forcing chain. On the other hands, for any vertex σ (v) ≤1, one obtains that Z (G) ≤ O (G) -3.

Suppose every vertex in G has at most n - a neighbors for 3 ≤ a ≤ n - 2, then V = V₁ ∪ V₂, such that V₁ ={ u_i|1 ≤ i ≤ a }, and V₂ ={ v_i|1 ≤ j ≤ n - a } and N_G (u₁) = V₂. Since G and $\bar{G}$ are connected, we get that G has not a subgraph K_n,n-a. Thus there is 1 ≤ i ≤ a, 1 ≤ j ≤ n - a, such that u_iv_j ∉ E (G). Again, suppose v_k ∈ V₂ (G) and u_α and u_β in V₁, thus u_αv_k ∈ E (G) and u_βv_k ∉ E (G). Then V (G)∖ { u_α, u_β, v_k } is a zero forcing set for G and u₁ → v_k → u_α and v → u_β are two forcing chains, note that since G is connected, then there is some v ∈ V (G) and u_βv ∈ E (G). Therefore, Z (G) ≤ O (G) -3.□

In the above, some bounds for zero forcing numbers was given and the relations between Z (G) and $Z (\bar{G})$ , for some classes of graphs was obtained. In the following a new algorithm to obtaining zero forcing sets is presented. Also, a formula to computing zero forcing numbers for any connected graph is given.

Theorem 3.15. If G is a connected desired graph with order n, then Z (G) = n - k, that is k is a number of forces in zero forcing coloring process.

Proof. Suppose δ ≥ 2, if v₁ is one of some vertices with minimum degrees in graph (if δ = 1, then we choose v₁ with dv₁ ≥ 2). By zero forcing low, v₁ only can color a white vertex and δ - 1 vertex must be black.

So S₁ ={ N [v₁] ∖ v₁′ } is defined and v₁′ is a desired vertex in neighborhood, that becomes colored by force (v₁ → v₁′).

In second step, let v₂ be a vertex in S₁ with minimum degrees between all vertices of S₁.

By zero forcing low, v₂ only can color a white vertex and other neighbors must be black. We name this vertex by v₂′. So, S₂ is defined as follows: $S_{2} = {N [v_{1}] ∖ {v_{1}}^{'}} \cup {(N (v_{2}) ∖ (N (v_{2}) \cap S_{1})) ∖ {v_{2}}^{'}}$ and force v₂ → v₂′ and v₂′ is a desired vertex in neighborhood of v₂ is created. By continue this method: $\begin{matrix} S_{k} = {N [v_{1}] ∖ {v_{1}}^{'}} \cup {(N (v_{2}) ∖ (N (v_{2}) \cap S_{1})) ∖ {v_{2}}^{'}} \\ \cup \dots \cup {(N (v_{k}) ∖ (N (v_{k}) \cap S_{k - 1})) ∖ {v_{k}}^{'}} \end{matrix}$ If S_i = S_i+1, then we can choose v_i+2 in V (G) ∖ S_i+1 to continue forces in graph.

It is clear that with every choice v_i ∈ S_i, force v_i → v_i′ is created, that is v_i′ can productive for new next force. It continue to create S_i, until every vertex in G is in S_i, or colored by a force. Thus n = |S| + k, and hence k is numbers of forces in coloring process. Therefore, |S| = n - k, as desired.□

Example 3.16. Suppose G is the graph in Fig. (6), and A = [a_ij] is adjacency matrix of G. We can choice zero forcing set by above theorem.

Fig. 6

(a) A block fuzzy graph with two root vertices. (b) The cut tree of G.

For this graph, vertices with d_v ≥ 2 are {a, b, g, h}. So without diminishing the generalities of the problem, we choice v₁ = a. So, one vertex in neighbor must be white and other vertices must be black at first. Suppose b is black, then S₁ = {a, b} and v₁ = a → d = v₁′. In adjacency matrix every vertex that is in S₁, it is shown by [v], every vertex that colored by forces it is shown by (v), and draw a line every entry that involved with {a, b, d}. Thus one has:

In the next step, because we don not any vertex with minimum degree and all of adjancey vertices are black, then in V (G) ∖ S₁, we choice a vertrex by d_v ≥ 2. It is clear that {g, h} are vertices by this condition without diminishing the generatities of the problem, we choice v₂ = g and {d, h} are neighbors of g, such that d is black by force (a → d). Thus g can be in S₂ and one has the force g → h.

Now in adjancey matrix draw a line in every entry involve by {g, h}. Then below forces are created as follows:

In next step, we choice a vertex with minimum degree that not located in S₂ or previous forces.

{f, i, g} are vertices with this condition. We choice f and {e, i, g} are neighbor vertices of f that e is black by force (d → e), so it is enough that i be black and (f → j). By draw a line in every entry that involve with {f, i}, we will have S₃ and forces sequence as follows:

So |S| = 5 and k = 5.

Example 3.17. Let G = (σ, μ) be a fuzzy graph as Fig. 6, and A = {a, b, g, f, j}, B = {h, d, a, i, j} be two zero forcing sets of G^*. Since ∑_v∈Aσ (v) =1.4, and ∑_v∈Bσ (v) =1.7, we get Z (G) =1.4 .

4 Applications of zero forcing for some fuzzy graphs

As it is well known fuzzy graphs introduced by Azriel Rosenfeld in 1975 [15]. Fuzzy-graph structures has been used to highlight the most controversial issue between any two node in a particular period and can also tell the severity level of the issue at that time with the help of the membership function.

A network graph can be thought as a finite set of network nodes connected by path links, which are called as edges, when a network is modeled in the form of graph. Networks analysis plays an important role in social science, as a method to presenting data about complex individual relationships and networks in graphs form. The networks simulation and analysis starts to play an important role in a wide variety of disciplines, ranging from economics to molecular and population biology. In addition, networks are used for some debatable issues. At the following, we introduce two applications of zero forcing numbers for fuzzy graphs in medicine.

Intelligent capsule in cancer treatment

Intelligent capsule is made to help cancer patients. This technological product features a coating of sensitive sensors and by receiving electromagnetic signals automatically releases the medicine in body. This capsule releases the drug to the body by receiving information such as time and amount of use. This intelligent system also records data information through sensors which help doctor and patient to know better about the actual time and date of drug use. Doctors can keep track of the treatment process with real information about drug use and follow a more appropriate therapeutic prescription.

Production of intelligent polymeric micelles based on Nano-aurous materials for cancer diagnosis and treatment by chemo-laser therapy. One of the innovative ideas in the field of cancer treatment is the simultaneous use of chemo-laser therapy to decellularize cancer cells with reduced side effects. In this method, to achieve this goal, the ph-sensitive polymers are first controlled by polymerization. The synthesis and this intelligent polymer are placed on Nano-sphere and Nano-bars, then the drug loading is done. This drug system is sensitive to environmental factors and is able to control from outside of the body using lasers, drug entry will be done with the least harm to healthy cells. In two above mentioned methods of treatment, since this capsules containing the medicine are designed in way that they are only capable of moving through one adjacent route, if all the points which are involved in cancers tumors are shown by fuzzy graph vertexes. Therefore one set with the least vertexes will be detected which by shining the laser or electromagnet ray on capsule on that point involved points will be covered unless it makes the least harms to the healthy tissues. It means that is enough to consider the degree of membership of each vertex in the corresponding cancer tumors graph with extend of injury in realizing the drug capsule in releasing the drug capsule at that point to healthy tissues. Therefore, we have achieved that point by finding fuzzy zero forcing.

Example 4.1. For instance, if we consider the graph of dots involving cancer tumors, in figure below (Fig. 7). There are various zero forcing sets that can be liberated by external mobility at that point. The fact that we are looking for the least damage to healthy tissues, we just to choose the set {a, b, g} to get the least harm. $Z (G) = \land \sum_{v_{i} \in S} σ (v_{i}) = 0.1 + 0.1 + 0.2 = 0.4 .$

Fig. 7

Corresponding fuzzy graph for network cancer tumor.

5 Conclusion

The concept of zero forcing number for a crisp graph was generalized to fuzzy graphs. The zero forcing numbers for fuzzy block graphs and fuzzy graphs with Hamiltonian cycles and likewise for three classes of multipartite fuzzy graphs were computed. Also, the upper bound of zero forcing of connected fuzzy graphs with girth g was computed; and a formula for zero forcing numbers of connected graphs were obtained. Finally, two applications for fuzzy zero forcing numbers of fuzzy graphs in medical treatment was given.

References

AIM Minimum Rank - Special Graphs Work Group ( Barioli

, Barrett

, Butler

, Cioaba

, Cvetkovic

, Fallat

, Godsil

, Haemers

, Hogben

, Mikkelson

, Narayan

, Pryporova

, Sciriha

, So

, Stevanovic

, van der Holst

, Meulen

K.V.

, Wehe

A.W.

), Zero forcing sets and the minimum rank of graphs, Linear Algebra and its Applications 428(7) (2008), 1628–1648.

Barioli

, Barrett

, Butler

, Cioab̆a

S.M.

, Cvetkovíc

, Fallat

S.M.

, Godsil

, Haemers

, Hogben

, Mikkelson

, Narayan

, Pryporova

, Sciriha

, So

, Stevanovác

, van der Holst

, Vander Meulen

and Wangsness

, Zero forcing sets and the minimum rank of graphs, Linear Algebra and its Applications 428(7) (2008), 1628–1648.

Barioli

, Barrett

, Fallat

S.M.

, Hall

H.T.

, Hogben

, Shader

, Driessche

P.V.

and Holst

, Zero forcing parameters and minimum rank problems, Linear Algebra and its Applications 433(2) (2010), 401–411.

Borzooei

R.A.

and Sheikh Hoseini

, Golmohammadian

, Montazeri

and Mohseni Takallo

, Fuzzification of zero forcing process, New Mathematics and Natural Computation(to appear)

Borzooei

R.A.

, Rashmanlou

, Samanta

and Pal

, A study on fuzzy labbeling graphs, Journal of Intelligent & Fuzzy Systems 30 (2016), 3349–3355.

Boyer

, Brimkov

, English

, Ferrero

, Keller

, Kirschk

, Phillips

and Reinhart

, The zero forcing polynomial of a graph, Discrete Applied Mathematics 258 (2019), 35–48.

Bozeman

, Connections to zero forcing: Tree covers and power domination, Lowa State University, Ph.D thesis (2018).

Burgarth

and Giovannetti

, Full control by locally induced relaxation, Phys Rev Lett 99 (2007), 100–501.

Catral

, Cepek

, Hogben

, Huhnuh

, Lazebnik

, Peters

and Young

, Zero forcing number, maximum nullity, and path cover number of subdivided graphs, Electronic Journal of Linear Algebra 23 (2012), 906–922.

10.

Chenette

N.L.

, Droms

S.V.

, Hogben

, Mikkelson

and Pryporova

, Minimum rank of a tree over an Arbitrary Field, Electronic Journal of Linear Algebra, A Publication of the International Linear Algebra Society 16 (2007), 183–186.

11.

Javaid

, Irshad

, Batool

and Raza

, On the zero forcing number of corona and lexicographic product of graphs, arXiv:1607.04071v1 [math.CO] 14 Jul (2016).

12.

Hogben

, Minimum rank problems, Linear Algebra and its Applications 432 (2010), 1961–1974.

13.

Mordeson

J.N.

and Chang-Shyh

, Operations on fuzzy graphs, Information Sciences 79(3-4) (1994), 159–170.

14.

Mordeson

J.N.

, Mathew

and Malik

D.S.

, Fuzzy graph theory with applications to human trafficking, Springer (2018).

15.

Rosenfeld

, Fuzzy graphs, In L.A. Zadeh, K.S. Fu, K. Tanaka and M. Shirmura (Eds), Fuzzy set and their applications to cognitive and decision processes, Academic Press, New York, (1975), 77–95.

16.

Row

D.D.

, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra and its Applications 436 (2012), 4423–4432.

17.

, Kang

, Shan

and Zhao

, Power domination in block graphs, Theoretical Computer Science 359 (2006), 299–305.

18.

Zhan

, Malik

H.M.

and Akram

, Novel decision-making algorithms based on intuitionistic fuzzy rough environment, International Journal of Machine Learning and Cybernetics 10 (2019), 1459–1485.

19.

Zhan

, Akram

and Sitara

, Novel decision-making method based on bipolar neutrosophic information, Soft Computing 23 (2019), 9955–9977.