An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of k

Abstract

For a given a graph G, the zero forcing number of G, $Z\left(G\right)$, is the smallest cardinality of any set S of vertices on which repeated applications of the forcing rule results in all vertices being included in S. The forcing rule is as follows: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. The failed zero forcing number of a graph was introduced by Fetcie, Jacob, and Saavedra and was defined as the cardinality of the largest set of vertices which fails to force all vertices in the graph. In 2021, Gomez et al. proved that there were exactly 15 graphs with a failed zero forcing number of two, but their proof was complicated, requiring the analysis of many graph families. We present an “inverse” approach where we start with a set of vertices S and then see which graphs have S as a maximum-sized failed zero forcing set. This results in not only a shorter proof but characterizes which graphs have a particular failed zero forcing set. In our proof, we characterize the graphs which have a failed zero forcing set S where $\left|S\right|=2$, meaning considering all simple graphs of order two as induced subgraphs. This approach also has greater potential for characterizing graphs where $F\left(G\right)>2$ since many general arguments on the structure of graphs are developed in this type of analysis and are applicable for failed zero forcing sets of any size.

1. Introduction

Given a graph G, the zero forcing number of G, denoted by $Z\left(G\right)$, is the smallest cardinality of any initial set S of vertices on which iterated applications of the forcing rule results in every vertex being in S. The forcing rule is: if a vertex v is in S, and all but one neighbor u of v is in S, then u is added to S in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied, and they are cited in the survey by Fallat et al. [1]. In this paper, we investigate sets of vertices that do not force the rest of the vertices in the graph. Given a graph G, a stalled set $S\subseteq V\left(G\right)$ is a set of vertices upon which no vertex can be added to S by repeated applications of the forcing rule. A stalled set A where $A\ne V\left(G\right)$ is called a failed zero forcing set or an FZFS. We investigate the maximum size of a failed zero forcing set S in a graph. This quantity is known as the failed zero forcing number of a graph, denoted by $F\left(G\right)$. In 2015, Fetcie, Jacob, and Saavedra [2] introduced the failed zero forcing number of a graph, where they presented many results including a classification of all graphs with $F\left(G\right)=1$. In 2021, Gomez, Rubi, Terrazas, and Narayan provided a characterization of all graphs with $F\left(G\right)=2$. Shitov [3], proved that the problem of determining the failed zero forcing number of a given graph was NP-complete. Recently, Ufferman and Swanson [4] presented lower and upper bounds for $F\left(G\right)$. Independently, the zero blocking number of a graph which equals $\left|V\right(G\left)\right|-F\left(G\right)$ was introduced in 2020 by Beaudouin-Lafona, Crawford, Chen, Karst, Nielsen, and Sakai Troxell [5] and Karst, Shen, and Vu [6].

There are two natural problems that arise when investigating failed zero forcing sets:

• Given a graph G, determine $F\left(G\right)$.
• Given a set of vertices S, which graphs have S as a failed zero forcing set?

The first problem has been well studied with results appearing in [2,4,5,6,7]. The second “inverse” type problem has only been investigated where the failed zero forcing set is a single vertex. Fetcie, Jacob, and Saavedra [2] showed that the only graphs that have a failed zero forcing set consisting of a single vertex are two isolated vertices, a complete graph on three vertices, or paths on three or four vertices. We note that the problem involving two or more vertices could be particularly useful in solving the larger problem of characterizing graphs with a prescribed failed zero forcing number. In this paper, we show how this approach can be used to provide a shorter proof of the characterization of all graphs with a failed zero forcing number of two.

We next introduce notation that is used in this paper. We use $d\left(v\right)$ to denote the degree of a vertex v. The notations $K_n$, $P_n$, $C_n$ denote the complete graph, path, and cycle on n vertices, respectively. The discrete (or empty) graph with n vertices and no edges is denoted by $D_n$. The notation $G+H$ denotes the disjoint union of two graphs. We use $G\vee H$ to denote the join of two graphs, where $V(G\vee H)=V\left(G\right)\cup V\left(H\right)$ and $E(G\vee H)=E\left(G\right)\cup E\left(H\right)\cup \left\{uv\right|u\in V\left(G\right)$ and $v\in V\left(H\right)\}$. We use the following notation for the fan graph, $F_{r,s}=D_r\vee P_s$. Given two graphs F and K, we say $G_1$ is a 1-sum of F and K at vertex v if $G_1$ is obtained by merging the vertex v of F with the vertex v of K and no edge joins a vertex of $V\left(F\right)-v$ with a vertex of $V\left(K\right)-v$. A graph G is said to have a pendant graph H if G can be constructed as the 1-sum of H and some graph K. We use the term cherry to refer to an induced subgraph on vertices $\{v,x,y\}$ where $d\left(v\right)=2$, $d\left(x\right)=1$, and $d\left(y\right)=1$, and the cherry is pendant with respect to the middle vertex,

We refer to the vertices in a stalled set as “blue”and vertices not in a stalled set as “white”. Note that a stalled set S may be stalled because some vertices cannot be added to S or because every vertex of the graph is in S. As mentioned before, the former is called a failed zero forcing set and a stalled set where $S=V\left(G\right)$ we call a zero forcing set.

Definition 1

(Failed Zero Forcing Number). Given a graph G, the failed zero forcing number, denoted $F\left(G\right)$, is the maximum cardinality of a set $S\subseteq V\left(G\right)$, such that repeated applications of the forcing rule terminates with $S\ne V\left(G\right)$.

In 2021, Gomez, Rubi, Terrazas, and Narayan [7] identified the 15 graphs with a failed zero forcing number of two. These are shown in Figure 1.

However, their proof was complicated, involving the analysis of many graph families. As a result their methods were not practical for characterizing graphs with $F\left(G\right)>2$.

We present a shorter proof, using an “inverse” approach which shows all graphs that have a failed zero forcing set S as some simple graph of order $\left|S\right|=2$ (two isolated vertices, two adjacent vertices, graphs which have both as induced subgraphs). This approach also has more potential for extending to cases where $F\left(G\right)>2$. We investigate connected graphs with $F\left(G\right)=2$ in Section 2 and disconnected graphs with $F\left(G\right)=2$ in Section 3.

We next state a result from Ufferman and Swanson [4] as our first lemma.

Lemma 1

(Ufferman and Swanson). For any graph G, $\left|V\right(G\left)\right|\le 2F\left(G\right)+2$.

2. Connected Graphs with a Failed Zero Forcing Number of Two

We begin by restating a theorem of Gomez, Rubi, Terrazas, and Narayan [7].

Theorem 1

(Gomez et al. [7]). The connected graphs in Figure 1 are exactly the 15 connected graphs with $F\left(G\right)=2$, the last 12 of which are connected.

Proof. 

We now begin to prove that exactly 12 connected graphs G have $F\left(G\right)=2$ using a different approach than that of Gomez, Rubi, Terrazas, and Narayan [7]. By Lemma 1, all of these graphs have at most six vertices.

Let x and y be the two vertices in S. We consider various cases using the notation $i/j$ where x is adjacent to i white vertices and y is adjacent to j white vertices. We also include a designated overlap corresponding to the number of neighbors x and y have in common.

We first note in the case of 0/0, x and y would be the only vertices in the graph, and for this type of graph $F\left(G\right)\le 1$.

In the cases 1/✳ where “✳” represents any positive integer for which the set of blue vertices is not a stalled set.

We note in all of the following cases where x is adjacent to zero white vertices, x and y must be adjacent for the graph to be connected.

• Case 1: 0/3+

Let x be adjacent to zero white vertices and let y be adjacent to at least three white vertices including $u,v$, and w. Suppose one of the vertices $u,v,w$ has degree one. Without loss of generality, assume $d\left(u\right)=1$. Then, $\{x,y,u\}$ is an FZFS of size three.

We handle the cases where $\left|V\right(G\left)\right|=5$ and $\left|V\right(G\left)\right|=6$ separately.

First, assume $\left|V\right(G\left)\right|=5$. Suppose all of the vertices $u,v,w$ have degrees larger than one. Then, it must mean one of the vertices $u,v,$ or w are has degree three and can be added to vertices to x and y to create an FZFS of size three.

Next, assume $\left|V\right(G\left)\right|=6$. Here, we include a new vertex z.

First, we consider if y is adjacent to $x,u,v,w$, and z. Again, if any of the vertices $u,v,w,$ or z has degree one, then it could be added to x and y to form an FZFS of size three. So we proceed under the assumption that $u,v,w$, and z all have degree at least two. In the case where they all have degree two, y would be part of two pendant triangles, which implies that $F\left(G\right)\ge 4$. If one of the vertices $u,v,w$, or z has degree three, then it could be added to x and y to create an FZFS of size three.

The last case is where z is adjacent to u,v, or w. If z is adjacent to u and $d\left(z\right)=1$, then $\{u,x,y,z\}$ form an FZFS of size four. If $d\left(z\right)=2$, then $\{x,y,z\}$ is an FZFS of size three.

• Case 2: 0/2

Let x be adjacent to zero white vertices and y be adjacent to two white vertices w and z.

If y is not contained in a cycle, then $G-y$ has three components. If w and z each have degree one, then we have the graph shown in Figure 2, which is the same as graph (viii) in Figure 1. If w or z have a degree larger than one, then we could take all of the vertices in a largest component of $G-y$ and add y to form a failed zero forcing set of size at least three. If y is contained in a cycle of length at least four, then there is some vertex that has degree at least two and has distance at least two from y. This can be added to x and y to form a failed zero forcing set with size at least three.

If y is contained in a cycle of length three, then w and z are adjacent. This graph would have a failed zero forcing number of two and is shown in Figure 3, which is graph (vi) in Figure 1.

Next, from this graph, we consider if $d\left(w\right)\ge 3$ or $d\left(z\right)\ge 3$.

If $d\left(w\right)\ge 4$, then w would be adjacent to two white vertices $w_1$ and $w_2$. If both $w_1$ and $w_2$ have degree one, then the graph contains a cherry and $F\left(G\right)\ge 3$ (See Figure 4). Next, we consider if at least one of $w_1$ and $w_2$ has a degree greater than or equal to two. Assume that $d\left(w_1\right)\ge 2$. Then, $w_1,x$, and y form a stalled set of size three.

We next consider when w has degree three and z has degree two. Then, if w is adjacent to a vertex $w_1$, then it would form a graph shown in Figure 5, which is graph (xiii) in Figure 1.

We note that no other vertices can be adjacent to $w_1$ since $d\left(w_1\right)>1$ would imply that $x,y$, and $w_1$ would be a stalled set of size three.

However, it is possible for another vertex to be adjacent to z. For this case we consider when both w and z have degree three. Then, if w is adjacent to a vertex $w_1$, then it would form the graph in Figure 6 which is graph (xiv) in Figure 1.

We note that no other vertices can be adjacent to $z_1$. This is similar to the previous case involving $w_1$.

• Case 3: 2/2 overlap on zero (x and y are nonadjacent)

We consider different possibilities of adding edges to the graphs in Figure 7. Edges are added between vertices in the set $\{u,v,w,z\}$. We note we must add at least one edge between a vertex on the left side and a vertex on the right side for the graph to be connected.

• If there is only one edge between a white vertex on the left side and a white vertex on the right side and no other edges are added, then the graph is $P_6$.
• If there are two edges between the left side and the right side, then there are two vertices of degree at least two that are both adjacent to either x or y. Then, these two vertices can be added to S and their common neighbor can be removed to create an FZFS of size three.

• Case 4: 2/2 overlap on zero (x and y are adjacent)

We consider different possibilities of adding edges to the graphs in Figure 8. Edges are added between vertices in the set $u,v,w,z$. If no edges are added, the graph has a cherry and $F\left(G\right)=4$.

• If there is only a single edge between vertices on the left side and vertices on the right side, then the graph is a $C_4$ with pendant edges on adjacent vertices. A FZFS of size three can be formed by taking a vertex of degree one, its neighbor, and a vertex that has degree two and has distance three from the chosen vertex of degree one.
• If there are two or more edges from vertices on the left side and vertices on the right side, then there is a pair of vertices of degree at least two that are both either adjacent to x or y. The pair of vertices can then be added to S and we can remove their common neighbor from S to create an FZFS of size three.

We next consider cases where x and y share exactly one neighbor. Here, if x or y is adjacent to four white vertices, and the other is adjacent to two white vertices; then, the graph would have more than six vertices. Hence, there is no 4/2 overlap on one case.

• Case 5: 3/2 overlap on one case (where x and y are adjacent or nonadjacent)

Here, we consider cases where x is adjacent to three white vertices and y is adjacent to two white vertices, and x and y have exactly one white neighboring vertex in common. The cases where x and y are adjacent or nonadjacent proceed in the same way. Since the maximum number of vertices in a graph with $F\left(G\right)=2$ is six, no other vertices can be added. We consider adding edges between any of the white vertices $u,v,w$, and z. We show in each of the 64 cases $F\left(G\right)\ge 3$. Note in each case, we added edges to the graph in Figure 9.

• First, we note that if v is adjacent to two or three of the other white vertices, then v could be added to x and y to form a failed zero forcing set of size three. The same is true for u. This accounts for 44 of the cases.
• If no edges are added between vertices $u,v,w$, and z, or if only the edge $wz$ is added, then we can apply the cherry lemma and $F\left(G\right)=4$.
• If $vu$ or the edge set $\{uv,wz\}$ are added with no other edges, then we have a pendant $K_3$, and $F\left(G\right)=4$.
• If $uw$ or the edge set $\{uz,wz\}$ is added with no other edges, then $\{v,x,y\}$ forms an FZFS of size three.
• If the edge set $\{uz,vz\}$ or $\{uz,vz,wz\}$ with no other edges, then $\{u,v,y\}$ is an FZFS of size three.
• If the edge set $\{wz,vz\}$ or $vz$ or $vw$ are added with no other edges, then $\{u,x,y\}$ is an FZFS of size three.
• If the edges $vw$ and $uz$ are added with no other edges, then $\{u,v,y\}$ is an FZFS of size three.
• If the edge set $\{vw,uz,wz\}$ or $\{uw,vz,wz\}$ is added with no other edges, then $\{u,v,y\}$ is an FZFS of size three.
• If $uz$ or the edge set $\{uw,wz\}$ is added with no other edges, then $\{v,x,y\}$ is an FZFS of size three.
• If $vw$ is added with no other edges, then $\{u,x,y\}$ is an FZFS of size three.
• If the edge set $\{uw,vw\}$ or the edge set $\{uw,vw,wz\}$ is added with no other edges, then $\{u,w,y\}$ is an FZFS of size three.
• If the edge set $\{uw,wz\}$ is added with no other edges, then $\{v,x,y\}$ is an FZFS of size three.

None of these cases result in a graph with $F\left(G\right)=2$.

• Case 6: 2/2 overlap on one (where x and y are adjacent)

Let x and y be the only vertices in the colored set S and $N\left(x\right)\cap N\left(y\right)=\left\{z\right\}$, and let x and y each be adjacent to exactly one other uncolored vertex, q and w, respectively. This graph is shown in Figure 10.

Note that graphs in this case have a minimum of five vertices due to the structural constraints of the case and a maximum of six vertices due to Lemma 1.

We first consider the case where x and y are adjacent. For graphs with five vertices, we must consider adding any combination of edges in the set $\{qz,qw,wz\}$. We break these into six cases, covering the remaining two using the symmetry between edges $qz$ and $zw$.

• Case (i) $qz\in E\left(G\right)\wedge qw\notin E\left(G\right)\wedge zw\notin E\left(G\right)$, then $\{q,y,w\}$ is an FZFS of size three.
• Case (ii) $qz\in E\left(G\right)\wedge qw\notin E\left(G\right)\wedge zw\in E\left(G\right)$. Then, we obtain a fan graph (xi) in Figure 1 with $F\left(G\right)=2$.
• Case (iii) $qz\in E\left(G\right)\wedge qw\in E\left(G\right)\wedge zw\notin E\left(G\right)$, then $\{z,x,w\}$ is an FZFS of size three.
• Case (iv) $qz\in E\left(G\right)\wedge qw\in E\left(G\right)\wedge zw\in E\left(G\right)$, then $\{z,q,y\}$ is an FZFS of size three.
• Case (v) $qz\notin E\left(G\right)\wedge qw\in E\left(G\right)\wedge zw\notin E\left(G\right)$. This is the house graph with $F\left(G\right)=2$ and is shown in Figure 11.
• Case (vi) $qz\notin E\left(G\right)\wedge qw\notin E\left(G\right)\wedge zw\notin E\left(G\right)$. This graph is the first graph shown in Figure 11 and has $F\left(G\right)=2$.

For graphs with six vertices, we consider various cases involving adding a vertex v and edges to the graph shown in Figure 10.

• If v is adjacent to two white vertices, then $\{v,x,y\}$ form an FZFS of size three.
• If $vz\in E\left(G\right)$ and $d\left(z\right)>3$, an FZFS can always be formed by the set $\{v,z,x\}$
• If $vz$ is the only edge added, then we have the graph (xiv) in Figure 1.
• If $vz$ and $qw$ are the only edges added, then $\{q,v,z\}$ forms an FZFS of size three.
• If $vq$ is the only edge added, then $\{q,v,x\}$ is an FZFS of size three.
• If $qv$ and $qw$ are the only edges added, then $\{q,v,y\}$ is an FZFS of size three.
• If $qv$ and $wz$ are the only edges added, then $\{q,v,x\}$ is an FZFS of size three.

FZF sets of size three from the five-vertex case can be used in with six vertices in some of these cases. We next consider the cases where x and y are not adjacent.

• Case 7: 2/2 overlap on one case (where x and y are non-adjacent)

We first consider graphs on five vertices. We look at the different possibilities for adding edges to $P_5$.

• Case (i) $qz\in E\left(G\right)\wedge qw\notin E\left(G\right)\wedge zw\notin E\left(G\right)$, G has a pendant triangle and $F\left(G\right)\ge 3$.
• Case (ii) $qz\in E\left(G\right)\wedge qw\notin E\left(G\right)\wedge zw\in E\left(G\right)$, G has a pendant triangle and $F\left(G\right)\ge 3$.
• Case (iii) $qz\in E\left(G\right)\wedge qw\in E\left(G\right)\wedge zw\notin E\left(G\right)$. This is the house graph.
• Case (iv) $qz\in E\left(G\right)\wedge qw\in E\left(G\right)\wedge zw\in E\left(G\right)$. This is the fan graph $F_{1,4}$, which is graph (xi) in Figure 1.
• Case (v) $qz\notin E\left(G\right)\wedge qw\in E\left(G\right)\wedge zw\notin E\left(G\right)$. This is $C_5$ (xii) in Figure 1.
• Case (vi) $qz\notin E\left(G\right)\wedge qw\notin E\left(G\right)\wedge zw\notin E\left(G\right)$. This is $P_5$ (ix) in Figure 1.

The graphs that were obtained above are shown in Figure 12.

Next, we consider graphs with six vertices. We can cover all 2/2 with one overlap cases by starting with $P_5$ on vertices $q,x,z,y$ and w, where x and y are in S and we add a new vertex v.

We first note that for the graph to be connected, v must be adjacent to at least one white vertex. If it is adjacent to two white vertices, then $\{v,x,y\}$ is an FZFS of size three.

Next, we consider different cases for adding edges to the graph shown in Figure 13. We note that some cases can be removed since the graph has a horizontal symmetry. We consider two sets of cases (i) $vq$ (or $vw$), and (ii) $vz$ is added to the graph shown in Figure 13.

We first add $vq$ (which is symmetric to adding $vw$). Then, we consider cases for adding other edges between vertices $q,x,$ and w. Since there are three different edges to add, there are $2^3=8$ cases.

• If no other edges are added, then the graph is $P_6$ which is graph (xv) in Figure 1.
• If the edge $qz$ is added, then $\{w,y,z\}$ is an FZFS of size three.
• If the edge $zw$ is added, then $\{q,v,z\}$ is an FZFS of size three.
• If the edge $qw$ is added, then $\{q,v,x\}$ is an FZFS of size three.
• If the edges $qz$ and $zw$ are added, then $\{q,v,z\}$ is an FZFS of size three.
• If the edges $qz$ and $qw$ are added, then $\{q,v,y\}$ is an FZFS of size three.
• If the edges $zw$ and $qw$ are added, then $\{q,v,z\}$ is an FZFS of size three.
• If the edges $qz$, $zw$, and $qw$ are added, then $\{q,v,z\}$ is an FZFS of size three.

Next, we add $vz$ to the graph in Figure 13. Then, we consider cases for adding other edges between vertices $q,x,$ and w. Since there are three different edges to add, there are $2^3=8$ cases. However, adding the edge $qz$ is the same as adding $zw$ so we can eliminate two cases.

• If no other edges are added, then $\{q,x,z\}$ is an FZFS of size three.
• If the edge $qz$ is added, then $\{q,x,z\}$ is an FZFS of size three.
• If the edge $qw$ is added, then $\{v,w,z\}$ is an FZFS of size three.
• If the edges $qz$ and $zw$ are added, then $\{q,v,z\}$ is an FZFS of size three.
• If the edges $qz$ and $qw$ are added, then $\{q,v,z\}$ is an FZFS of size three.
• If the edges $qz$, $zw$, and $qw$ are added, then $\{q,v,z\}$ is an FZFS of size three.

This completes the 2/2 overlap on one nonadjacent case.

We note a special graph (shown in Figure 14) arises from this case. It is the only graph with six vertices with 2/2 overlap on one and $F\left(G\right)=2$. It is the only graph on six or fewer vertices that meets the $2F\left(G\right)+2$ order bound from Lemma 1 that is not a path.

We next consider the case where x and y share two neighbors.

• Case 8: 4/2 overlap on two (both adjacent or non-adjacent)

Here, x is adjacent to four white vertices and y is adjacent to two white vertices, and x and y have two neighbors in common.

We consider the possible ways to add edges to the graph shown in Figure 15.

• If $d\left(u\right)=1$ and $d\left(v\right)=1$, then the graph contains a cherry and $F\left(G\right)=4$.
• If $d\left(u\right)=1$ and $d\left(v\right)>1$, then $\{u,x,y\}$ is an FZFS of size three. (The case where $d\left(u\right)>1$ and $d\left(v\right)=1$ is similar.)
• If $uv$ is an edge of G and no other edges are added, then G contains a pendant triangle.
• If $uw$ and $vz$ are added, then $\{u,v,y\}$ forms an FZFS of size three (The cases where $uz$ and $vw$, $uz$ and $vz$, or $uw$ and $vw$ are added are similar. For all other cases, u can simply be added to $\{x,y\}$).

• Case 9: 3/2 overlap on two case (where x and y are adjacent or non-adjacent)

It maybe helpful to refer to Figure 16. We first consider graphs with five vertices (vertices $v,w,x,y,$ and z). Let x be adjacent to $v,w$, and z, and let y be adjacent to v and w. We consider adding edges between vertices $v,w,z$.

If $wz$ is the only edge added to this graph, then $\{v,x,y\}$ forms an FZFS of size three. If $vw$ or $vz$ (but not both) is added to the graph, then we have graph (x) in Figure 1, if x and y are not adjacent. If x and y are adjacent, then it is graph (xi) in Figure 1.

If $vw$ and $vz$ are added, then $\{v,x,y\}$ form an FZFS of size three. Assuming x and y are nonadjacent, if $vw$ and $wz$ are added, then we have graph (xi) in Figure 1. If x and y are adjacent then $\{v,y,z\}$ form an FZFS of size three.

Next, we consider graphs with six vertices. Here, we add a new vertex u. We must have $d\left(u\right)>0$ for G to be connected. If $d\left(u\right)\ge 2$, then u could be added to x and y to form an FZFS of size three. Hence, the remaining cases are where $d\left(u\right)=1$.

We first consider adding the edge $uw$ which is the same as adding the edge $uz$. In this case, $\{v,w,z\}$ is an FZFS of size three. We next consider adding the edge $uv$. We consider various cases.

• If no other edges are added, then $\{u,v,x\}$ form an FZFS of size three.
• If $vw$ is added, then $\{u,v,z\}$ is an FZFS of size three.
• If $vz$ is added, then $\{u,v,z\}$ is an FZFS of size three.
• If $wz$ is added, then $\{u,v,z\}$ is an FZFS of size three.
• If any of the following edges sets $\{vw,wz\}$, $\{vz,wz\}$, or $\{vw,vz,wz\}$ is added, then $\{u,v,z\}$ is an FZFS of size three.
• If $\{vw,vz\}$ is added, then $\{u,v,x\}$ is an FZFS of size three.

• Case 10: 2/2 overlap on two (where x and y are adjacent or non-adjacent)

Let x and y be the only vertices in S and both x and y are adjacent to both u and v.

We first consider graphs with four vertices. The two graphs shown in Figure 17 are graphs (iv) and (v) in Figure 1.

We next consider graphs with five vertices. We consider adding a vertex v that is adjacent to u (the case where v is adjacent to w is similar). If $d\left(v\right)=1$, then $\{u,v,w\}$ is an FZFS of size three. If $d\left(v\right)=2$, then v is also adjacent to w. Here, $\{v,x,y\}$ is an FZFS of size three.

Next, we consider the case of six vertices where we add vertices v and z. We first note that if both v and z are adjacent to either u or w, then we have either a cherry or a pendant cherry and $F\left(G\right)\ge 3$.

We then consider adding edges $uv$ and $wz$. If v is not adjacent to z, then $\{u,v,w\}$ is an FZFS of size three. If v and z are adjacent, $\{v,x,y\}$ is an FZFS of size three.

Finally, we consider the case where either v and z are part of a $P_3$ or $K_3$ with either u and w. Without loss of generality, we consider the case involving u. Then, the vertices $\{u,v,w\}$ form an FZFS of size three.

We note that the presence of edges $xy$ or $uw$ does not change the result.

• Case 11: 3/3 overlap on two (where x and y are adjacent or nonadjacent)

It maybe helpful to refer to Figure 18. Let x be adjacent to $v,w,$ and z, and let y be adjacent to $u,v,$ and w.

• Case (i) If $d\left(u\right)=1$ or $d\left(z\right)=1$, then either u or z could be added to x and y to form an FZFS of size three.
• Case (ii) If $uz$ is an edge of $E\left(G\right)$, then $\{w,x,y\}$ is an FZFS of size three.
• Case (iii) If $uv$ and $vz$ are in $E\left(G\right)$, then $\{v,x,y\}$ is an FZFS of size three.
• Case (iv) If $uw$ and $vz$ are in $E\left(G\right)$, then $\{u,v,x\}$ is an FZFS of size three.

• Case 12: 3+/3+ overlap on three or more vertices (where x and y are adjacent or non-adjacent)

If x and y are both adjacent to three white vertices, then these three vertices form an FZFS of size three.

This completes the proof. □

We conclude this section with an observation regarding graphs with different failed zero forcing sets of size two.

Corollary 1.

The graphs (iv), (x), and (xi) in Figure 1 are the only graphs that have failed zero forcing sets of both $2K_1$ and $K_2$.

3. Disconnected Graphs

Failed zero forcing numbers for disconnected graphs were first studied by Fetcie, Jacob, and Saavedra [2] where they proved the following theorem.

Theorem 2

(Fetcie, Jacob, and Saavedra). Let G be a disconnected graph with k maximal components, $G_1,G_2,\dots ,G_k$.

Then, $F\left(G\right)=\underset{k}{\max }\left(F\left(G_k\right)+{\displaystyle \sum _{l\ne k}}\left|V\left(G_l\right)\right|\right)$

Next, we present an analog to Lemma 1 with the addition of a lower bound.

Theorem 3.

If G is a disconnected graph, then $F\left(G\right)+1\le \left|V\right(G\left)\right|\le 2F\left(G\right)$.

Proof. 

Assume G has at least two components. The lower bound follows, since $\left|V\right(G\left)\right|\le F\left(G\right)$ would imply that $V\left(G\right)$ is a failed zero forcing set, which is impossible. For the upper bound, we let $F\left(G\right)=k$ and begin with two observations. First, by Theorem 2, no part can contain more than $F\left(G\right)$ vertices. The second observation is that the graph cannot contain more than $F\left(G\right)$ components. If not, by the same formula there will be a failed zero forcing set with at least one vertex in each of the parts, and hence $F\left(G\right)>k$.

We note by the formula in Theorem 2, $F\left(G\right)>\underset{k}{\max }\left({\displaystyle \sum _{l\ne k}}\left|V\left(G_l\right)\right|\right)$. Thus, if G has k components, then $F\left(G\right)\ge \frac{k-1}{k}\left|V\left(G\right)\right|$. This implies that $\left|V\left(G\right)\right|\le \frac{k}{k-1}F\left(G\right)$. The largest bound is obtained with $k=2$. Hence, $\left|V\left(G\right)\right|\le 2F\left(G\right)$. In fact, $\left|V\right(G\left)\right|=2F\left(G\right)$ if and only if $G=2K_1$ or $G=2K_2$. □

Theorem 4.

The three disconnected graphs with a failed zero forcing number of two are $3K_1$,$K_2+K_1$, and $K_2+K_2$.

Proof. 

We consider possibilities for a disconnected graph G to have a failed zero forcing number of two. Each component of G has at most two vertices, since if G contained a component with more than two vertices, then $F\left(G\right)\ge 3$.

The graph G can have at most three components, because if G has more than three components, then we could color all of the vertices in all but one of the components and have $F\left(G\right)\ge 3$.

We proceed under the assumption that G has exactly three components. The only possible case is where $G=3K_1$. Here, two vertices could be colored blue, resulting in a failed zero forcing set of size two.

Next, assume that G has two components. If either component has more than two vertices, then $F\left(G\right)\ge 3$. If both components have one vertex, then $F\left(G\right)=1$. The only possibilities are where one component has two vertices and the other component has one vertex, or both components each have two vertices. These are graphs $K_2+K_1$ and $K_2+K_2$, which are graphs (i), (ii), and (iii) in Figure 1. □

4. Conclusions

As mentioned earlier, this inverse approach may be useful in characterizing graphs with a prescribed $F\left(G\right)$ or a particular graph. For example, if $\left|S\right|=3$, then the possibilities for the different failed zero forcing sets are the simple graphs of order three which include $3K_1$, $K_2+K_1$, $K_3$, and $P_3$. One could start with these four graphs and investigate supergraphs with less than or equal to eight vertices. While this problem will be considerably more complicated when $F\left(G\right)$ is large, there is the possibility of investigating subproblems where S is restricted to be a particular graph, such as a complete graph or a path.