All Graphs with a Failed Zero Forcing Number of Two

Abstract

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 in S. The forcing rule is: 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. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. In this paper, we investigate the largest size of a set S that does not force all of the vertices in a graph to be in S. This quantity is known as the failed zero forcing number of a graph and will be denoted by $F\left(G\right)$. We present new results involving this parameter. In particular, we completely characterize all graphs G where $F\left(G\right)=2$, solving a problem posed in 2015 by Fetcie, Jacob, and Saavedra.

1. Introduction

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 in S. The forcing rule is: 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. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied [1]. In this paper, we investigate the largest size of a set S that does not force all of the vertices in a graph to be in S. This quantity is known as the failed zero forcing number of a graph and will be denoted by $F\left(G\right)$ [2,3]. Shitov [4], proved that determining the failed zero forcing number of a graph is NP-complete. Independently, a closely related property called the zero blocking number of a graph was introduced in 2020 by Beaudouin-Lafona, Crawford, Chen, Karst, Nielsen, and Sakai Troxell [5] and Karst, Shen, and Vu [6]. The zero blocking number of a graph G equals $\left|V\right(G\left)\right|-F\left(G\right)$.

We will use $K_n$, $P_n$, $C_n$, to denote the complete graph, path, and cycle on n vertices, respectively. The complete bipartite graph with r vertices in one part and t in the other part will be denoted $K_{r,t}$. The disjoint union of graphs G and H will be denoted by $G+H$. Following the terminology of [7], we will refer to an induced $K_{1,2}$ as a “cherry”. A vertex v is a cut-vertex of a graph G if $G-v$ has more components than G. We will refer to a subgraph that contains a cut-vertex v of degree 3 that is adjacent to vertices u and w, which are adjacent to each other and have degree 2, as a pendant $K_3$.

Throughout the paper, we will use colorings to describe our failed zero forcing sets where the vertex in S will be colored blue (or referred to as filled) and the vertices not in S will be colored white (or referred to as uncolored). A vertex will be called true blue if it is colored blue and all of its neighbors are colored blue. A vertex that is not a true blue vertex will be referred to as non true blue.

Failed zero forcing numbers were introduced by Fetcie, Jacob, and Saavedra [2] where they established numerous results. In particular they proved that for any connected graph $0\le F\left(G\right)\le n-2$ and gave a characterization of all graphs G where $F\left(G\right)\in \{0,1,n-2,n-1\}$. They showed that the only graphs where $F\left(G\right)=0$ are either $K_1$ or $K_2$ and the only graphs where $F\left(G\right)=1$ are $2K_1$, $P_3$, $K_3$, or $P_4$. It was also shown that $F\left(G\right)=n-1$ if and only if G contains an isolated vertex. In addition, $F\left(G\right)=n-2$ if and only if G contains a module of order 2, where a module is defined as follows. A set X of vertices in $V\left(G\right)$ is a module if all vertices in X have the same set of neighbors among vertices not in X. They gave examples of some graphs where $F\left(G\right)=2$ and posed the problem of characterizing all graphs with this property. We provide a complete solution to this problem in Section 2.

2. Graphs with a Failed Zero Forcing Number of 2

We provide a characterization of all graphs with a failed zero forcing number of 2. We first examined all graphs with between 3 and 6 vertices and identified all graphs with $F\left(G\right)=2$. These 15 graphs are shown in Figure 1i–xv with larger vertices indicating the failed zero forcing set of size 2. Later we show that no other graphs exist. We will show that if G has at least 7 vertices then $F\left(G\right)\ge 3$.

It is not difficult to verify that each of these graphs has a failed zero forcing number of 2. For the sake of completeness, we include the details. For each graph, the larger vertices give a lower bound for the failed zero forcing number of 2. For the disconnected graphs (i)–(iii), the upper bound for $F\left(G\right)=2$ follows since coloring any three vertices blue forces all of the vertices to be colored blue. For the five connected graphs with four vertices (iv)–(viii) the upper bound follows since $F\left(G\right)\le n-2$. For the two paths (ix) and (xv), the coloring of any three vertices blue will result in either a vertex of degree 1 being colored blue or two adjacent vertices colored blue, both of which will force all of the vertices in the graph to be blue. For the graph of $C_5$ coloring any three vertices blue will mean that two adjacent vertices were colored blue, which will force the remaining vertices in the graph. For the house graph (x) note that coloring any three of the vertices in the graph blue will either include two vertices of the triangle or three vertices in the $C_4$ both of which will force all vertices in the graph to be blue. For the gem fan graph (xii) with five vertices, coloring three vertices blue will either include the vertex of degree four and two other vertices, or three vertices of degree two or three, both of which will force all vertices in the graph to be blue. For the graph consisting of a triangle and two pendant edges (xiii) note that coloring any three vertices blue will either include the three vertices of degree greater than 1, one vertex of degree 1, and two vertices of degree greater than 1, or two vertices of degree 1, all of which will force all vertices to be colored blue. Finally for the triangle with three pendant edges (xiv), coloring any three vertices blue will either include all three vertices of degree greater than 1, or at least one vertex of degree 1 and two other vertices that are either degree 1 or greater than 1, all of which will force all vertices to be blue.

We examined all connected graphs on six vertices [8] and found that all but two graphs have a failed zero forcing number of at least 3. The two graphs the corona $K_3$ and $P_6$ (graphs (xiv) and (xv) in Figure 1) have a failed zero forcing number of 2. Adding an additional vertex v and any number of edges between v and other vertices of the graph results in a graph with a failed zero forcing number of 3 (This is verified later in Section 2.2). The above suggests that any graph with 7 or more vertices has a failed zero forcing number of at least 3, which we will prove.

The following theorem guarantees that our list of 15 graphs with $F\left(G\right)=2$ is complete.

Theorem 1.

Let G be a graph with at least 7 vertices. Then $F\left(G\right)\ge 3$.

It is tempting to think that if you have a graph G where $F\left(G\right)=k$, then for any supergraph H of G we have $F\left(H\right)\ge k$. However, it can be the case that $F\left(H\right)<F\left(G\right)$ and in fact we can construct graphs where $F\left(G\right)-F\left(H\right)$ is arbitrarily large. In Figure 2 we give an example of a graph G where $F\left(G\right)=5$ and a supergraph H of G where $F\left(H\right)=4$.

Theorem 2.

There exist graphs G with a supergraph H where $F\left(G\right)-F\left(H\right)$ is arbitrarily large.

Proof. 

Let G be a graph with vertices $v_1,v_2,\dots ,v_n$ with edges $\left\{v_i{v}_{i+1}\right|$$i=1,\dots ,n-2\}$ and $\left\{v_{n-2}{v}_n\right\}$. Here $F\left(G\right)=n-2$.

Now add the edge $v_1{v}_n$ to create a supergraph H. Since H is a cycle with a pendant vertex we can obtain a maximum-sized failed zero forcing set by selecting the pendant vertex and $⌊\frac{n}{2}⌋$ vertices along the cycle (including the neighbor of the pendant vertex). Hence $F\left(H\right)=⌊\frac{n}{2}⌋+1$. Since $F\left(G\right)-F\left(H\right)=n-2-\left(⌊\frac{n}{2}⌋+1\right)\ge \frac{n}{2}$ this difference can be made arbitrarily large, by choosing a graph with a sufficiently large number of vertices. □

We next present a series of lemmas that will be used to prove Theorem 1.

A characterization of disconnected graphs with a failed zero forcing number k was given by Fetcie, Jacob, and Saavedra [2].

Lemma 1.

Let G be a disconnected graph with $k\ge 2$ maximal connected components. Let $G_1,G_2,\dots ,G_k$ be the k maximal connected components of G. Then $F\left(G\right)=\underset{1\le i\le k}{max}$$\{F\left(G_i\right)+{\displaystyle \sum _{l\in \{1,2,\dots ,k\}-i}}\left|V(G_l\right|\}$.

This theorem can be applied to determine all disconnected graphs with a particular failed zero forcing number. We show the result for the case where $F\left(G\right)=2$.

Lemma 2.

For a disconnected graph G, $F\left(G\right)=2$ if and only if G equals $3K_1$, $K_2+K_1$, or $K_2+K_2$.

Proof. 

If G consists of three components the only possibility is for G to equal $3K_1$, since if any component contained $k>1$ vertices we would have $F\left(G\right)\ge k+1\ge 3$. If G has two components one component must contain exactly two vertices, and the other component must have a failed zero forcing number of 0 which are either $K_1$ or $K_2$. We note that if G contains a component with more than 2 vertices then we could color the vertices in this component blue and vertices in other component white and obtain a failed zero forcing set with more than 2 vertices. □

Now that we have identified all disconnected graphs with $F\left(G\right)=2$, we next consider the case of connected graphs.

We will next show that every graph with at least 7 vertices has a failed zero forcing number of at least 3. The approach will be as follows. A sketch is shown in Figure 3.

We provide a sketch of the approach here. A complete proof appears in Section 2.2. We start with a connected graph with 9 or more vertices that does not contain a pendant V or a pendant $K_3$ and reduce it to a graph with 6 vertices by removing vertices and incident edges. We note we can maintain a connected graph by successively removing a leaf from a spanning tree of the graph. We will show in Lemmas 6 and 7 that the reduced graphs will not contain a pendant V or a pendant $K_3$. As a result when we consider various cases in reducing the graph we can ignore cases where we have a pendant V or a pendant $K_3$. If the resulting graph on six vertices does not have any true blue vertices, then we apply Lemma 3 add back vertices and edges to obtain the original graph which will have a failed zero forcing set of size at least 3. If the resulting graph on six vertices has at least one true blue vertex then we consider all possible extensions to supergraphs with 7 vertices. We show that all of these graphs have $F\left(G\right)\ge 3$. If these graphs on 7 vertices do not have any true blue vertices then we can apply Lemma 3 and extend the graph to the original graph which will a failed zero forcing set of size at least 3. If the extensions to graphs with 7 vertices have at least one true blue vertex then we consider all possible extensions to 8 vertices. By showing that all of these graphs do not have any true blue vertices, they can be extended back to the original graph showing that $F\left(G\right)\ge 3$.

In our next lemma we show that if a graph G can be extended to contain an additional vertex v and if the extended graph has a failed zero forcing set S where v is not in S then any number of edges can be added between v and vertices of G and S will still be a failed zero forcing set of any of these new graphs.

Lemma 3.

Let G be a connected graph with a set of S of blue vertices. If each vertex in S is adjacent to two vertices not in S, then for any supergraph H of G, we have that $F\left(H\right)\ge F\left(G\right)$.

Proof. 

We can add any number of vertices and edges G to create a supergraph H. Then color all of the vertices in $V\left(G\right)-V\left(H\right)$ white. Then since white vertices cannot force any other vertices and the blue vertices are still adjacent to two white vertices, no vertices in the graph will be forced. Hence $F\left(H\right)\ge F\left(G\right)$. □

Lemma 4.

If a connected graph G has a pendant $K_3$. Then $F\left(G\right)\ge n-2$.

Proof. 

We can color the two vertices of degree 2 in the $K_3$ white and all other vertices blue. Then each blue vertex will either be true blue or will be adjacent to two white vertices. Hence this is a failed zero forcing set of size $\left|V\right(G\left)\right|-2$. □

In the next three lemmas we identify families of graphs that have a failed zero forcing number of at least 3. These will be used to prove Theorem 1.

Lemma 5.

Let G be a graph with 5 or more vertices and contains a cut-vertex v such that $G-v$ has at least three components, at least two of which are paths. Then $F\left(G\right)\ge 3$.

Proof. 

We consider two cases.

Case (i) G has a cut-vertex v such that $G-v$ consists of three disjoint paths $P_i$, $P_j$, and $P_k$. Then either i, j, or k must be at least 2. Without loss of generality suppose $i\ge 2$. Then v along with the vertices of $P_i$ form a failed zero forcing set of at least 3. To see this note that v will be adjacent to two white vertices, and all other vertices in the graph can be colored blue.

Case (ii) G is a graph with 5 or more vertices and has a cut-vertex v such that $G-v$ consists of a subgraph H with at least two vertices and two disjoint paths. Then we color v and all vertices in H blue, and the remaining vertices white. This creates a failed zero forcing set of at least 3. Note that all of the blue vertices in this coloring all vertices in H are true blue and v is adjacent to two white vertices. □

A pendant V is a subgraph containing a cut-vertex v of degree at least 3 whose removal results in at least two paths in different components. In our next two lemmas, we prove that if a graph G does not contain a pendant V or a pendant $K_3$ then it can be reduced to a subgraph $G^{\prime }$ by removing vertices and edges, so that $G^{\prime }$ does not contain a pendant V or a pendant $K_3$.

Lemma 6

(pendant V). Let G be a connected graph with at least five vertices that does not contain a pendant V. Then $\left|V\left(G\right)\right|-5$ vertices of G can be successively removed (along with incident edges) to create a graph that does not have a pendant V.

Proof. 

We will show that if a graph G does not have a pendant V, then there is some vertex we can remove from G so that the resulting graph does not have a pendant V. Let G be a graph that is not a cycle and does not have a pendant V subgraph. We will show that there is always some vertex v whose removal does not leave a subgraph with a pendant V. We use $\delta \left(G\right)$ to denote the smallest degree of a vertex in a graph G. We can assume that $\delta \left(G\right)\ge 2$ since we could remove a vertex of degree 1 and not create a pendant V subgraph. Since $\delta \left(G\right)\ge 2$, G must contain a cycle C that has no pendant paths. Since $G\ne C$ the cycle C must contain a vertex w with degree at least 3. Removing a vertex on C that has degree 2 is adjacent to w will not leave a pendant V since the part of the graph in $G-C$ will not contain a pendant V. □

Lemma 7

(pendant $K_3$). Let G be a connected graph with at least five vertices that does not contain a pendant $K_3$. Then $\left|V\left(G\right)\right|-5$ vertices of G can be successively removed (along with incident edges) to create a graph $G^{\prime }$ that does not have a pendant $K_3$.

Proof. 

We will show that if G does not contain a pendant $K_3$, there is always some vertex we can remove so that the resulting graph does not contain a pendant $K_3$. Let G be a graph without a pendant $K_3$, but $G-v$ contains a pendant $K_3$ with vertices a, b, c, and d where a and b are adjacent, and b, c, and d are all mutually adjacent, and c and d are not adjacent to a. Furthermore assume that b, c, and d are not adjacent to any other vertices. Since G has at least 5 vertices we can assume that either $d\left(a\right)\ge 2$ or $d\left(v\right)\ge 2$. We will consider cases (i)–(iv) and show in each case that a different vertex can be removed from G that will not result in a pendant $K_3$. It may be helpful to refer to Figure 4.

Case (i): v is adjacent to a, b, c, and d. Removing d leaves an induced $K_4-e$ (a complete graph on 4 vertices with one edge removed) on vertices a, v, b, and c.

Case (ii): v is adjacent to a, b, and c only. Then removing b results in a path on vertices a, v, c, and d.

Case (iii): v is adjacent to c and d only. Then removing c results in a path on vertices v, d, b, and a.

Case (iv): v is adjacent to c only. Then removing d results in a path on vertices v, c, b, and a.

Case (v): v is adjacent to d only. Then removing c results in a path on vertices v, d, b, and a. □

2.1. Graphs with Six Vertices: Exception Cases

We will consider the 112 connected graphs with six vertices. We will refer to the table and numbering found in [8]. For convenience, we explicitly show each graph in each of the individual cases.

Out of 112 different graphs, there were 16 cases where there does not exist three blue vertices, none of which are true blue. We will refer to these as our exception cases. We will show that each of the exception cases with six vertices can either be extended to graphs with seven, eight, or nine vertices where there are three blue vertices with none of which are true blue, or the extension includes a pendant V, which would be ruled out by Lemma 6. In each of the cases below when identifying the three blue vertices, none of which are true blue, it can be assumed that all other vertices can be colored white.

This will not only show that they have a failed zero forcing number of at least 3, but they can be extended indefinitely by adding vertices and edges and the resulting supergraph will also have a failed zero forcing number of at least 3.

These graphs are the exceptions: 54, 58, 59, 60, 76, 77, 80, 85, 86, 87, 96, 98, 102, 103, 105, and 112, each of which we will present individually. Graph 54: Please refer to Figure 5.

We begin by extending graph 54 by one vertex v and connecting it to each vertex in G. Notice there will be no case where v is adjacent to $v_2$ or $v_5$. This is because connecting a vertex to either one will create a cherry structure and that case is covered by our cherry lemma. Our goal with extending is to find no true blue vertex within the graph. It is also important to notice that in each case, we are able to find a failed zero forcing number of three.

If v is adjacent to $v_1$, then $v_1,v_3,$ and $v_4$ can be colored blue.

If v is adjacent to $v_3$, then $v_2,v_3,$ and $v_5$ can be colored blue. If v is adjacent to $v_4$, then $v_2,v_4,$ and $v_5$ can be colored blue. If v is adjacent to $v_6$, then $v_3,v_4,$ and $v_6$ can be colored blue.

If v is adjacent to $v_2$ only then G contains a pendant cherry and is removed from consideration by Lemma 6.

If v is adjacent to $v_5$ only then G contains a pendant cherry and is removed from consideration by Lemma 6.

If v is adjacent to $v_2$ and $v_5$ then $v,v_3,$ and $v_4$ can be colored blue.

Since all cases can be extended indefinitely, this implies that graph 54 can be extended indefinitely without being forced with $F\left(G\right)\ge 3$. Graph 58: Please refer to Figure 6.

Let $v_1$ be the vertex of degree 1 and let $v_2$ be the neighbor of $v_1$; $v_4$ is the vertex of degree 3 that is adjacent to $v_2$, $v_3$, and $v_5$. Let $v_5$ be the vertex of degree 3 that is adjacent to $v_6$; vertices $v_6$ and $v_3$ both have degree 2. We consider extending the graph by adding a new vertex v.

If v is adjacent to $v_1$ then $v_1,v_4,$ and $v_5$ can be colored blue.

If v is adjacent to $v_3$ then $v_2,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_6$ then $v_2,v_4,$ and $v_6$ can be colored blue.

If v is adjacent to $v_4$ and $v_5$ then $v_2,v_4,$ and $v_5$ can be colored blue.

In all of the above cases, we are left without any true blue vertices and thus we can extend these graphs indefinitely with $F\left(G\right)\ge 3$.

If v is adjacent to $v_2$ only then the graph contains a cherry and is removed from consideration by Lemma 6.

The only problem cases is where v is adjacent to $v_4$ or $v_5$ (but not both). Here we can find a failed zero forcing set S of size 3 by selecting $v_1$, $v_2$, and $v_4$, however we may not be able to extend S to larger graphs. Without loss of generality assume that v is adjacent to $v_4$. We consider adding a new vertex u with possible neighbors. We note that u cannot have degree 1 and be adjacent to $v_2$ or $v_4$ since this would create a cherry and this case would be ruled out by Lemma 6. If u is adjacent to both $v_2$ or $v_4$ then we can color u, $v_3$, and $v_5$ blue. If u is adjacent to v then we could color v, $v_3$, and $v_5$ blue. If u is adjacent to $v_1$ then we could color $v_1$, $v_3$, and $v_5$ blue. If u is adjacent to $v_3$ then we could color $v_2,$$v_4$, and $v_5$ blue. If u is adjacent to $v_5$ then we could color $v_2,$$v_4$, and $v_5$ blue. If u is adjacent to $v_6$ then we could color $v_3,$$v_5$, and $v_6$ blue. Graph 59: Please refer to Figure 7.

Let $v_1$ be the vertex of degree 1, $v_4$ be the vertex of degree 4 that is adjacent to $v_1$, $v_3$ be the vertex of degree 2 that is adjacent to $v_4$, $v_2$ be the other vertex of degree 4, $v_5$ be the vertex of degree 3 that is adjacent to $v_2$ and $v_4$, and $v_6$ be the vertex of degree 2 that is adjacent to $v_2$ and $v_5$. Graph 59 follows with the case of graph 58. We can extend along any vertex without any true blue vertices with the only exception being when a new vertex is adjacent to vertex $v_3$. Similarly to graph 58 however, upon any additional extension, there are no issues arising when all the vertices are reshuffled.

For the sake of completeness we include the details. We consider adding a new vertex v and possible neighbors of v. The vertex v cannot have degree 1 and be adjacent to $v_4$ since this would create a cherry. In each case of the remaining cases we can find a coloring with 3 blue vertices, none of which are true blue vertices, and all of the remaining vertices including v will be colored white. If v is adjacent to $v_1$, then $v_1,$$v_3$, and $v_5$ can be colored blue. If v is adjacent to $v_3$, then $v_3,$$v_4$, and $v_6$ can be colored blue. If v is adjacent to $v_5$ then $v_2,$$v_4,$ and $v_5$ can be colored blue. If v is adjacent to $v_6$, then $v_2$, $v_4,$ and $v_6$ can be colored blue. The only problem case is if v is adjacent to $v_2$. Here we can find a failed zero forcing set S of size 3 with vertices $v_1$, $v_4$, and $v_6$, but we many not be able to extend this graph. Here we consider adding another vertex u. The vertex u cannot have degree 1 and be adjacent to either $v_2$ or $v_4$ since this would create a cherry and we can remove it from consideration by Lemma 2.6. If u is adjacent to v, then we color v, $v_3$, and $v_5$ blue. If u is adjacent to $v_1$, then we color $v_1$, $v_3$, and $v_5$ blue. If u is adjacent to $v_3$, then we color $v_2$, $v_3$, and $v_5$ blue. If u is adjacent to $v_5$, then we color $v_2$, $v_4$, and $v_5$ blue. If u is adjacent to $v_6$, then we color $v_2$, $v_4$, and $v_6$ blue. If u is adjacent to both $v_2$ and $v_4$ then we color u, $v_3$, and $v_5$ blue. Graph 60: Please refer to Figure 8.

Graph 60 has at least one true blue vertex but all extensions along graph 60 result in $F\left(G\right)\ge 3$ and no true blue vertices. Let $v_1$ be the vertex of degree 1, $v_3$ be the neighbor of $v_1$, $v_2$ be the vertex of degree 4, $v_4$ be the vertex of degree 3 that is adjacent to $v_2$ and $v_3$, $v_5$ be the vertex of degree 3 adjacent to $v_4$, and let $v_6$ be the vertex of degree 2. We consider adding another vertex v and possible neighbors of v. First if v has degree 1 then it cannot be adjacent to $v_3$ since this would create a cherry. In each of the remaining cases we can find a coloring with 3 blue vertices, none of which are true blue vertices, and all of the remaining vertices including v will be colored white. If v is adjacent to $v_1$ then we can color $v_1$, $v_4$, and $v_6$ blue, if v is adjacent to $v_2$ then $v_2$, $v_3$, and $v_5$ can be colored blue. If v is adjacent to $v_4$ then $v_3$, $v_4,$ and $v_6$ can be colored blue and if v is adjacent to $v_5$ then $v_2$, $v_3,$ and $v_5$ can be colored blue, and if v is adjacent to $v_6$ then $v_2$, $v_3,$ and $v_6$ can be colored blue. Graph 76: Please refer to Figure 9.

We will show that all but two extensions of G to a graph with 7 vertices will have no true blue vertex of degree 1. Let v denote the new vertex. Note that extensions that would result in a cherry are neglected as those cases are resolved by Lemma 6. We have the following cases

If v is adjacent to $v_1$ only, we color $v_1$, $v_3$, and $v_4$ blue and v, $v_2$, $v_5$ and $v_6$ white.

We consider cases of adding a new vertex v.

If v is adjacent to $v_1$, we color $v_1$, $v_3$, and $v_4$ blue.

If v is adjacent to $v_6$, we color $v_3$, $v_4$, and $v_6$ blue.

If v is adjacent to $v_2$ or $v_5$ only, then this case can be removed by Lemma 6.

If v is adjacent to both $v_2$ and $v_5$ only, then color v, $v_3$, and $v_4$ blue.

The only problem cases is where v is adjacent to $v_4$ or $v_5$.

Without loss of generality, we assume v is adjacent to $v_4$. Then we consider adding another vertex u.

If u is adjacent to v then color v, $v_2$, and $v_3$ blue.

If u is adjacent to $v_1$ then color $v_1$, $v_3$, and $v_4$ blue.

If u is adjacent to $v_6$ then color $v_3$, $v_4$, and $v_6$ blue.

If u is adjacent to $v_3$ then color $v_3$, $v_4$, and $v_5$ blue.

If u is adjacent to $v_2$, $v_4$, or $v_5$ only then this case can be removed by Lemma 6.

If u is adjacent to $v_2$, $v_4$, and $v_5$ then we can color $v_2$, $v_4$, and $v_5$ blue.

If u is adjacent to $v_2$ and $v_4$ only then we can color $v_2$, $v_4$, and $v_5$ blue.

If u is adjacent to $v_2$ and $v_5$ only then we can color u, $v_3$, and $v_4$ blue.

If u is adjacent to $v_4$ and $v_5$ only then we can color $v_2$, $v_4$, and $v_5$ blue.

Since in each of these extensions we have three blue vertices none of which are true blue, we can extend these graphs indefinitely. Graph 77: Please refer to Figure 10. Suppose we add a new vertex called v.

If v is adjacent to $v_2$ or $v_5$ only then we can remove this case by Lemma 6. Our goal with extending is to find no true blue vertex. If we do have a true blue, we must then extend further.

If v is adjacent to $v_6$, then $v_2,v_4,$ and $v_6$ can be colored blue.

If v is adjacent to $v_3$, then $v_2,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_1$, then $v_1,v_3,$ and $v_5$ can be colored blue.

There are two cases in which we cannot not obtain three non-true blue vertices. The first is when v is adjacent to $v_4$ and the second is when v is adjacent to both $v_2$ and $v_5$.

Case 1. If v is adjacent to $v_4$, then $v_2,v_4,$ and v can be filled. For this case, we must extend further since there is a true blue vertex. Suppose we add a second vertex called u.

If u is adjacent to v then $v,v_2$, and $v_5$ can be colored blue.

If u is adjacent to $v_1$ then $v_1,v_4$, and $v_5$ can be colored blue.

If u is adjacent to $v_3$ then $v_3,v_4$, and $v_5$ can be colored blue.

If u is adjacent to $v_6$ then $v_2,v_4$, and $v_6$ can be colored blue.

If u is adjacent to $v_2$, $v_4$ or $v_5$ only then we can remove this case by Lemma 6.

If u is adjacent to $v_2$ and $v_4$ then $u,v_3$, and $v_5$ can be colored blue.

If u is adjacent to $v_2$ and $v_5$ then $v_2,v_4$, and $v_5$ can be colored blue.

If u is adjacent to $v_4$ and $v_5$ then $v_2,v_4$, and $v_5$ ccan be colored blue.

Case 2. If v is adjacent to both $v_2$ and $v_5$ then we consider adding another vertex w.

If w is adjacent to v then $v_1,v_2$, and $v_4$ can be colored blue.

If w is adjacent to $v_1$ then $v,v_1$, and $v_4$ can be colored blue.

If w is adjacent to $v_3$ then $v_2,v_4$, and $v_5$ can be colored blue.

If w is adjacent to $v_4$ then $v_2,v_4$, and $v_5$ can be colored blue.

If w is adjacent to $v_6$ then $v_1,v_4$, and $v_6$ can be colored blue.

The cases where w is adjacent to $v_2$ or $v_5$ only can be removed from consideration by Lemma 6.

If w is adjacent to $v_2$ and $v_5$ then $v,v_1$, and $v_4$ can be colored blue.

Thus, we can extend all cases indefinitely without ever forcing G. Since each case is extendable, then graph 77 is extendable.

Notice there is no case where v is adjacent to $v_2$ or $v_5$. This is because connecting a vertex to either one would create a cherry structure and that case is covered elsewhere. It is also important to notice that in each case, we are able to find a failed zero forcing number of three.

Every blue vertex has two white neighbors, so we can add any number of edges or vertices to any of these graphs without forcing G. This is because the three blue vertices will always be adjacent to two white neighbors and cannot force any other vertex. Thus, $F\left(G\right)\ge 3$ for graph 77.

Graph 80: Please refer to Figure 11. It will be helpful to refer to Figure 11. Let the vertex on the far left be $v_1$. Let the vertex adjacent to $v_1$ be $v_2$. Let the top vertex adjacent to $v_2$ be $v_3$ and the bottom be $v_4$. Let the vertex that is adjacent to both $v_3$ and $v_4$ on the right be $v_5$. Furthermore, finally, let the vertex on the far right side be $v_6$. We begin by extending graph 80 by one vertex, v and connecting v to every vertex in G. We can rule out the case where v is adjacent to $v_2$ or $v_5$ only by Lemma 6. If v is adjacent to both $v_2$ and $v_5$ then then we can color vertices v, $v_3$, and $v_4$ blue and all other vertices white. This is because connecting a vertex to either would create a cherry structure and that case is covered elsewhere.

If v is adjacent to $v_6$, then $v_3,v_4,$ and $v_6$ can be colored blue.

If v is adjacent to $v_4$, then $v_2,v_4,$ and $v_5$ can be colored blue.

If v is adjacent to $v_3$, then $v_2,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_1$, then $v_1,$$v_3$, and $v_4$ can be colored blue.

In all cases, there are no true blue vertices. Thus, all cases are extendable and this implies graph 80 can be extended indefinitely. It is also important to notice that in each case, we are able to find a failed zero forcing number of three. Graph 85: Please refer to Figure 12.

We will show that all but two extensions of G to a graph with 7 vertices have no true blue vertex of degree 1. Let v denote the new vertex. Note that extensions that would result in a cherry are neglected as those cases are resolved by Lemma 6. We consider the following cases.

If v is adjacent to $v_6$ only, we color $v_2$, $v_6$, and $v_4$ blue.

If v is adjacent to $v_1$ only, we color $v_1$, $v_3$, and $v_6$ blue.

If v is adjacent to $v_3$ only, then $v_2$, $v_3$, and $v_5$ can be colored blue.

If v is adjacent to $v_2$ only then this case can be removed by Lemma 2.6.

The only problems are where v is adjacent to $v_4$ or $v_5$.

First, we consider the case where v is adjacent to $v_4$.

Then we add another vertex u.

If u is adjacent to $v_2$ or $v_4$ only then this case can be removed by Lemma 2.6.

If u is adjacent to $v_2$ and $v_4$, then u, $v_3$, and $v_5$ can be colored blue.

If u is adjacent to v, then v, $v_3$, and $v_6$ can be colored blue.

If u is adjacent to $v_1$, then $v_1$, $v_5$, and $v_6$ can be colored blue.

If u is adjacent to $v_3$, then $v_3$, $v_4$, and $v_6$ can be colored blue.

If u is adjacent to $v_5$, then $v_2$, $v_4$, and $v_5$ can be colored blue.

If u is adjacent to $v_6$, then $v_2$, $v_4$, and $v_6$ can be colored blue.

First, we consider the case where v is adjacent to $v_5$.

Then we add another vertex w.

If w is adjacent to v, then v, $v_3$, and $v_6$ can be colored blue.

If w is adjacent to $v_1$, then $v_1$, $v_4$, and $v_6$ can be colored blue.

If w is adjacent to $v_3$, then $v_2$, $v_3$, and $v_5$ can be colored blue.

If w is adjacent to $v_4$, then $v_2$, $v_4$, and $v_6$ can be colored blue.

If w is adjacent to $v_6$, then $v_3$, $v_5$, and $v_6$ can be colored blue.

If w is adjacent to $v_2$ or $v_5$ only then this case can be removed by Lemma 2.6.

If w is adjacent to $v_2$ and $v_5$, then u, $v_3$, and $v_6$ can be colored blue. Graph 86: Please refer to Figure 13.

We will show that all extensions of G to a graph with 7 vertices have no true blue vertices of degree 1. Let v be the new vertex. Let $v_1$ be the vertex of degree 1, $v_2$ be the vertex of degree 2 that is adjacent to $v_1$, $v_3$ be the vertex of degree 3 that is adjacent to and on the left of $v_2$, $v_4$ be the vertex of degree 2 that is adjacent to $v_3$, $v_5$ be the vertex of degree 2 that is adjacent to $v_4$, and $v_6$ be the vertex of degree 3 that is adjacent to $v_5$. We have the following cases.

If v is adjacent to $v_1$ only, we color $v_1$, $v_3$, and $v_6$ blue.

If v is adjacent to $v_2$ only, the resulting graph contains a cherry. So we color v, $v_1$ white, and color the remaining vertices blue.

If v is adjacent to $v_3$ only, we color $v_2$, $v_3$, and $v_5$ blue.

If v is adjacent to $v_4$ only, we color $v_2$, $v_4$, and $v_6$ blue.

The remaining cases of connecting v to G are analogous to one of the previous four. Furthermore, note that in each case where the resulting graph does not contain a cherry, we can always color v white and add edges between v and any subset of the remaining vertices without affecting the number of blue vertices. Graph 87: Please refer to Figure 14.

All but one of the single vertex extensions of G is either a cherry or suitable for extension by Lemma 3. Let $v_1$ be the only vertex of degree one that is adjacent to $v_2$; $v_2$ is adjacent to $v_3$ and $v_6$; $v_3$ will be adjacent to $v_2$ and $v_5$ and $v_4$ will be adjacent to $v_5$ and $v_6$.

If v is adjacent to $v_1$, we can fill in $v_1$, $v_3$, and $v_6$.

If v is adjacent to $v_2$, it creates a cherry and this case can be discarded.

If v is adjacent to $v_3$, we can fill in $v_2$, $v_3$, and $v_4$.

If v is adjacent to $v_4$, we can fill in $v_3$, $v_4$, and $v_6$.

If v is adjacent to $v_6$, we can fill in $v_2$, $v_5$, and $v_6$.

If v is adjacent to $v_5$, we must have a true blue vertex and thus this graph must be extended further. We can then add in an additional vertex, u.

If u is adjacent to $v_1$, we can fill in $v_1$, $v_3$, and $v_6$.

If u is adjacent to $v_2$, it again creates a cherry and we can discard this case.

If u is adjacent to $v_3$, we can fill in $v_2$, $v_3$, and $v_4$.

If u is adjacent to $v_4$, we can fill in $v_2$, $v_4$, and $v_5$.

If u is adjacent to $v_5$, we get another cherry and thus another discarded case.

If u is adjacent to $v_6$, we can fill in $v_2$, $v_5$, and $v_6$.

If u is adjacent to v, then we can fill v, $v_2$, and $v_4$.

In every case, we see a suitable coloring for extension by Lemma 3. Thus, we may extend graph 87 to a super-graph H, and by Lemma 3, $F\left(H\right)\ge F\left(G\right)\ge 3$. Graph 96: Please refer to Figure 15.

We will show that any extension of G to a graph with 7 vertices will have at most one true blue vertex. Let the vertices of the triangle be $v_1,v_2,$ and $v_3$ which are adjacent to vertices of degree 1, $v_4,v_5,$ and $v_6$, respectively.

Consider the addition of a new vertex v. We first consider if v is adjacent to $v_4,v_5,$ or $v_6$. Without loss of generality assume v is adjacent to $v_4$. Then we color $v_2,v_3,$ and $v_4$ blue and $v,v_1,v_5,$ and $v_6$ white. If v is adjacent to one of the vertices $v_1,v_2,$ or $v_3$ only then we apply Lemma 6. If v is adjacent to all of the vertices $v_1,v_2,$ and $v_3$ then we can color $v_1,v_2,$ and $v_3$ blue. The only case that is a problem is where v is adjacent to exactly two of the vertices $v_1,v_2,$ and $v_3$. Without loss of generality we assume that v is adjacent to $v_1$ and $v_2$.

Here we add another vertex u.

If u is adjacent to $v_4$, $v_5$, and $v_6$ then these cases are similar to the previous cases involving v,

If u is adjacent to v then we can color v, $v_2$, and $v_3$ blue.

If u is adjacent to exactly one of $v_1$, $v_2$, and $v_3$ then this case can be removed by Lemma 6.

If u is adjacent to $v_1$ and $v_2$ only then we can color u, v, and $v_3$ blue.

If u is adjacent to $v_1$ and $v_3$ only then we can color $v_1$, $v_2$, and $v_3$ blue.

If u is adjacent to $v_2$ and $v_3$ only then we can color $v_1$, $v_2$, and $v_3$ blue.

If u is adjacent to $v_1$, $v_2$, and $v_3$ then we can color $v_1$, $v_2$, and $v_3$ blue. Graph 98: Please refer to Figure 16.

We begin by extending graph 98 by one vertex, v and connecting v to every vertex in G.

If v is adjacent to $v_1$, then $v_1,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_3$, then $v_2,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_6$, then $v_2,v_4,$ and $v_6$ can be colored blue.

The case where v is adjacent to $v_2$, $v_4$, or $v_5$ only can be removed by Lemma 6.

If v is adjacent to $v_2$ and $v_4$, then $v_1,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_2$ and $v_5$, then $v_2,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_4$ and $v_5$, then $v_2,v_4,$ and $v_5$ can be colored blue.

We can see in all cases there are no true blue vertices. Thus, all cases are extendable and this implies graph 98 can be extended indefinitely. It is also important to notice that in each case, we are able to find a failed zero forcing set of size three. Graph 102: Please refer to Figure 17.

We begin by extending graph 102 by one vertex, v and connecting v to every vertex in G. Due to the symmetry of the graph, we can ignore the case where v is adjacent to $v_5$. Notice there will be no case where v is adjacent to $v_3$ or $v_4$. This is because connecting a vertex to either one will create a cherry structure, and this is covered by Lemma 6.

We have to consider the case where v is adjacent to both $v_3$ and $v_4$. In this case, we have to add a new vertex u.

If u is adjacent to v, then $v,v_1$, and $v_3$ can be colored blue.

If u is adjacent to $v_1$, then $v_1,v_3$, and $v_4$ can be colored blue.

If u is adjacent to $v_2$, then $v_2,v_3,$ and $v_4$ can be colored blue. If u is adjacent to $v_5$, then $v,v_1,$ and $v_5$ can be colored blue. If u is adjacent to $v_6$, then $v,v_1,$ and $v_6$ can be colored blue. If u is adjacent to $v_3$ or $v_4$ only then this can be removed by Lemma 6.

If u is adjacent to $v_3$ and $v_4$ then $u,v,$ and $v_1$ can be colored blue.

If v is adjacent to $v_1$, then $v_1,v_3,$ and $v_5$ can be colored blue. Due to the symmetry of the graph, this case is the same as when v is adjacent to $v_2$. So it can be ignored. However, this case has a true blue and so it must be extended. Suppose we add a new vertex u.

If u is adjacent to $v_6$, then $v_1,v_3,$ and $v_6$ can be filled.

If u is adjacent to $v_2$, then $u,v_1,$ and $v_3$ can be filled. Here vertex u is true blue, so we must extend further. Suppose we add another vertex called w.

If w is adjacent to $v_6$, then $v_2,v_3,$ and $v_6$ can be filled.

The only problem case left is if w is adjacent to $v_2$ only. This would create a $C_4$ with a pendant edge at each vertex.

Here we can add another vertex x.

If x is adjacent to v, then $v,v_3,$ and $v_4$ can be colored blue.

If x is adjacent to w, then $w,v_3,$ and $v_4$ can be colored blue. If x is adjacent to $v_5$, then $v_1,v_2,$ and $v_5$ can be colored blue.

If x is adjacent to $v_6$, then $v_1,v_2,$ and $v_6$ can be colored blue.

If x is adjacent to $v_1$, $v_2$, $v_3$, and $v_4$ only then this case can be removed by Lemma 6.

If x is adjacent to $v_1$ and $v_2$, then $x,v_3,$ and $v_4$ can be colored blue.

If x is adjacent to $v_1$ and $v_3$, then $x,v_2,$ and $v_4$ can be colored blue.

If x is adjacent to $v_2$ and $v_4$, then $x,v_1,$ and $v_3$ can be colored blue.

If x is adjacent to $v_3$ and $v_4$, then $x,v_1,$ and $v_2$ can be colored blue.

Notice there are no true blue vertices and that $F\left(G\right)\ge 3$ in all cases. Since there are no true blue vertices, then this case is now extendable. Since each case is extendable, then graph 102 can be extended indefinitely without being forced.

Graph 103: Please refer to Figure 18. We begin by extending graph 103 by one vertex, v, and connecting v to every vertex in G. Notice there will be no case where v is adjacent to $v_5$ or $v_2$. This is because connecting a vertex to either would create a cherry structure and that case is covered by the cherry lemma. It is also important to notice that in each case and sub-case, we are able to find a failed zero forcing number of three. Our goal with extending is to find no true blue vertex within the graph. Due to the symmetry of the graph, we can ignore the cases where v is adjacent to $v_4$ and $v_1$.

If v is adjacent to $v_6$, then $v_3,v_4,$ and $v_6$ can be colored blue.

If v is adjacent to $v_3$, then this reverts to the extension of Graph 102 where the added vertex v is adjacent to $v_1$.

Since there are no more true blue vertices, then this case is resolved and can be extended indefinitely. Since each case is extendable, this implies that graph 103 can also be extended indefinitely without being forced. Graph 105: Please refer to Figure 19.

We begin by extending graph 105 by one vertex, v and connecting v to every vertex in G. Notice there will be no case where v is adjacent to $v_2$. This is because adding an extension to $v_2$ would create a cherry structure and this case is covered by the cherry lemma. It is also important to notice that in each case, we are able to find a failed zero forcing number of three. Our goal with extending is to find no true blue vertex within the graph.

If v is adjacent to $v_1$, then $v_1,v_3,$ and $v_6$ can be colored blue.

If v is adjacent to $v_6$, then $v_2,v_4,$ and $v_6$ can be colored blue.

If v is adjacent to $v_3$, then $v_2,v_3,$ and $v_5$ can be colored blue.

If v is adjacent to $v_5$, then $v_1,v_2,$ and $v_5$ can be colored blue.

If v is adjacent to $v_4$, then $v_1,v_2,$ and $v_4$ can be filled.

Notice the last two cases have a true blue vertex. Without loss of generality assume that v is adjacent to $v_4$.

Suppose we add a new vertex u.

If u is adjacent to $v_2$ or $v_4$ only then this case can be removed by Lemma 6.

If u is adjacent to v, then $v,v_2,$ and $v_3$ can be colored blue.

If u is adjacent to $v_1$, then $v,v_4,$ and $v_6$ can be colored blue.

If u is adjacent to $v_3$, then $v_2,v_3,$ and $v_5$ can be colored blue.

If u is adjacent to $v_2$ and $v_4$, then $v,v_3,$ and $v_6$ can be colored blue.

If u is adjacent to $v_5$, then $v_2,v_4,$ and $v_5$ can be colored blue.

If u is adjacent to $v_6$, then $v_2,v_4,$ and $v_6$ can be colored blue.

Since there are no more true blue vertices in these sub-cases, then this case is resolved and can be extended indefinitely. Since each case is extendable, this implies that graph 105 can be extended indefinitely without being forced and $F\left(G\right)\ge 3$.

Graph 112: Please refer to Figure 20.

$P_6$: Any extension of $P_6$ to a graph with 7 vertices will have at most one true blue vertex.

We consider adding a vertex v to this graph. If v is adjacent to $v_1$ then we can color vertex v white and color vertices $v_1,v_3,$ and $v_5$ blue to create a failed zero forcing set of size 3. If v is adjacent to $v_6$ then we can color vertex v white and color vertices $v_2,v_4,$ and $v_6$ blue to create a failed zero forcing set of size 3. If v is not adjacent to either $v_1$ or $v_6$ then v must be adjacent to one or more of the vertices $v_2,v_3,v_4,$ or $v_5$. We consider different cases, each showing that we can create a failed zero forcing set of size 3 with at most one true blue vertex. We consider a series of different cases.

If v is adjacent to only one of the vertices $v_2$, $v_3$, $v_4$, or $v_5$ then this creates a pendant V which can be removed from consideration by Lemma 6.

If v is adjacent to $v_2$ and $v_3$ only then we color $v_2,v_3,$ and $v_5$ blue.

If v is adjacent to $v_2$ and $v_4$ only then we color $v_2,v_3,$ and $v_4$ blue.

If v is adjacent to $v_2$ and $v_5$ only then we color $v,v_2$ and $v_5$ blue.

If v is adjacent to $v_3$ and $v_4$ only then we color $v,v_2,$ and $v_5$ blue.

If v is adjacent to $v_2,v_3,$ and $v_4$ only then we color $v_2,v_3$, and $v_5$ blue.

If v is adjacent to $v_2,v_3,$ and $v_5$ only then we color $v,v_2,$ and $v_4$ blue.

If v is adjacent to $v_2,v_3,v_4$ and $v_5$ only, then we color $v_2,v_3$, and $v_5$ blue.

The only problem case is where v is adjacent to both $v_2$ and $v_5$. In this case we add a new vertex u.

If u is adjacent to v then we color $v_1,v_2,$ and $v_4$ blue.

If u is adjacent to $v_1$ then we color $v_1,v_3,$ and $v_5$ blue.

If u is adjacent to $v_3$ then we color $v_2,v_3,$ and $v_5$ blue.

If u is adjacent to $v_4$ then we color $v_2,v_4,$ and $v_5$ blue.

If u is adjacent to $v_6$ then we color $v_2,v_4,$ and $v_6$ blue.

If u is adjacent to $v_2$ or $v_5$ only then this case can be removed from consideration by Lemma 6.

If u is adjacent to $v_2$ and $v_5$ then we color u, v, and $v_3$ blue.

2.2. Proof of the Main Theorems

We now prove Theorem 1. Let G be a graph with at least 7 vertices. Then $F\left(G\right)\ge 3$.

Proof. 

The graphs with six vertices fall into three different groups (i) graphs where $S\subseteq V\left(G\right)$ has at least three blue vertices, none of which are true blue, (ii) graphs where $S\subseteq V\left(G\right)$ has three blue vertices, but one is true blue (which we will call exceptions), and (iii) graphs that contain a pendant V or a pendant triangle. The strategy is as follows. We start with a graph H with at least 8 vertices and remove vertices (along with incident edges) to obtain a reduced graph G with 6 vertices. We note we can maintain a connected graph by successively removing a leaf from a spanning tree of the graph. If G is in group (i) then $F\left(G\right)\ge 3$, and since each blue vertex has two white neighbors we can extend G by Lemma 3 by adding vertices and edges to obtain the original graph H, so that $F\left(H\right)\ge 3$. If G is in group (ii) then $F\left(G\right)\ge 3$, but since G contains a true blue vertex it may not be able to be extended to obtain H. These are the exception cases. Here we consider all extensions of G to graphs with 7, 8, or 9 vertices so that there can be three blue vertices, none of which are true blue. Then we can extend G by Lemma 3 by adding vertices and edges (if necessary) to obtain the original graph H, so that $F\left(H\right)\ge 3$. If G is in group (iii) then it contains a pendant V or a pendant triangle. By Lemmas 6 and 7 if every reduction of G results in a graph G with a pendant triangle or pendant V then H must have had a pendant triangle or pendant V. By Lemmas 4 and 5, $F\left(H\right)\ge 3$. This shows that any graph with at least 8 vertices has a failed zero forcing number of at least 3. However, examining the exception cases from Section 2.1, we note that any extension of graphs with six vertices to seven vertices still have a failed zero forcing number of at least 3. Hence any graph with at least 7 vertices has a failed zero forcing number of at least 3. □

We have now proved our main theorem that gives us a characterization of all graphs with $F\left(G\right)=2$.

Theorem 3.

The graphs with $F\left(G\right)=2$ are precisely those shown in Figure 1.

3. Conclusions

In this paper, we have investigated failed zero forcing sets, which not only provided new theoretical results but also have practical implications. Applications of zero forcing lie in the area of social networks in which a person knows a particular piece of information and if they share it with all but one of their friends, in the interest of unity, they share the information with their remaining friend. For failed zero forcing we are seeking the largest number of people that could know a piece of information so that it does not spread across the entire network. This is also relevant in the spreading of disease in a pandemic where we seek the maximum number of people that can be infected, yet the infection does not spread to the entire population.

We have completely characterized all graphs with a failed zero forcing number of 2. We pose the following problem.

Problem 1.

Characterize all graphs with a failed zero forcing number of 3.

Our investigations into this problem revealed a much larger number of graphs with a failed zero forcing number of 3 and the methods used in this paper will require investigation of a much larger number of exception cases.

We also showed that all graphs with at least 7 vertices have a failed zero forcing number of 3. As an extension of this result, we pose the following problem.

Problem 2.

Determine the smallest n such that all graphs with at least n vertices have a failed zero forcing number of size k.