1. Introduction
The concept of failed zero forcing lies at the intersection of graph theory and linear algebra with its application to minimum rank problems in linear algebra [
1]. For a given a graph
G, the zero forcing number of
G is denoted
, and is the smallest cardinality of any set
S of vertices of which iterations of the forcing rule result in all vertices in
G 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,
2,
3,
4,
5,
6,
7]. This area has applications to linear and quantum controllability for evolving on networks [
8]. These studies have included determination 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 is denoted by
[
9,
10,
11]. Shitov [
12], 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 [
13] and Karst, Shen, and Vu [
14]. The zero blocking number of a graph
G equals
. In 2010, researchers from the IMA-ISU research group [
2] introduced skew zero forcing where any vertex that has all but one of its neighbors colored will force the last remaining vertex to be forced. In 2016, Ansill, Jacob, Penzellna, and Saavedra [
15] introduced the failed skew zero forcing number, denoted
, which is the largest size of a set of vertices that does not skew force all of the vertices in the graph. It was noted in [
15] that the skew zero forcing number of a graph gives an upper bound on the maximum nullity of any skew-symmetric matrix associated with the graph.
We will use , , , to denote the complete graph, path, and cycle on n vertices, respectively. A vertex v is a cut-vertex of a graph G if has more components than G.
Throughout the paper we will use colorings to describe failed zero forcing sets where the vertex in S will be referred to as colored and the vertices not in S will be referred to as uncolored.
In 2016 Ansill, Jacob, Penzellna, and Saavedra [
15] characterized graphs with extreme values of
and
n. The characterization of graphs with
was surprisingly complex. We review this in the next section.
In this paper, we characterize all graphs with a failed skew zero forcing number of 1. In these graphs, there is a vertex which is a stalled set (meaning that this set of vertices does not force any other vertices), and any pair of vertices forces all vertices in the graph. Within this class of graphs there is an interesting subclass of graphs where there is a unique vertex v that is a failed skew zero forcing set of size 1 and all other vertices in the graph are zero forcing sets.
In 2015, Fetcie, Jacob, and Saavedra [
10], characterized all graphs with a failed zero forcing number of 1—which turned out to be only four graphs: a pair of isolated vertices;
;
; and
. It is surprising to see that the change of the forcing rule where vertices not in
S can also force other vertices results in an infinite number of graphs with a failed skew zero forcing number of 1.
Ansill, Jacob, Penzellna, and Saavedra [
15] presented new results involving failed skew zero forcing numbers of graphs. In particular they provided a characterization for graphs with failed skew zero forcing numbers of 0.
They described a family of graphs called doubly extended bouquet-dipoles which is defined below.
Definition 1. A graph G is a doubly extended bouquet-dipole if it consists of vertices u and v that are each on a nonempty set of odd cycles, where all other vertices on the cycles have degree two, and u and v are joined by a path of even order that alternates between single even order paths whose internal vertices all have degree two, and multiple even order paths whose internal vertices all have degree two.
We restate a theorem from Ansill, Jacob, Penzellna, and Savvedra [
15] which gives a characterization of all graphs with a failed skew zero forcing number of 0.
Theorem 1 ([
15]
). if and only if G is one of the following graphs. (i) An odd cycle, or a nonempty set of odd cycles whose intersection is a single vertex or (ii) A doubly extended bouquet-dipole. In this paper, we provide a characterization of all graphs with a failed skew zero forcing number of 1. To show a graph has one has to show that the set where is a failed zero forcing set and if then all of the vertices in the graph are forced. However to show a graph has it is more complex. We need to show that there is a vertex which is a stalled set, and that any pair of vertices forces all vertices in the graph.
2. Failed Skew Zero Forcing Numbers of Graphs
We begin by investigating the failed skew zero forcing numbers for disconnected graphs followed and small examples of connected graphs.
Theorem 2. The only disconnected graph with is .
Proof. Suppose G is disconnected and has more than two components or a component with more than one vertex. Then S contains all but one component or the component with two or more vertices. Now . Now let G have two components that both have one vertex; . Let . It is clear that this is the maximum stalling set of . Therefore, is the only disconnected graph for which . □
From here we will assume that all graphs are connected. We first show two small graphs that have a failed skew zero forcing number of 1.
Lemma 1. .
Proof. Let the external vertices be labeled and and the middle vertex be w. If , then S is skew stalled; . If , then without loss of generality there will be a vertex in S with one neighbor outside of S, so the whole graph will be skew forced. Therefore, , giving the desired conclusion that . □
Lemma 2. .
Proof. Without loss of generality, choose a vertex on . Then that vertex has three neighbors outside of S which implies it will not skew force. Then each neighbor outside of S has two neighbors outside of S which implies each neighbor will not skew force. Thus, . Now suppose . Then the vertices outside of S only have one uncolored neighbor which will be skew forced into S, and then any vertex in S will force the remaining vertex that is outside S. So, . Therefore, . □
Now we define a subgraph and a lemma that provides a lower bound for the failed skew zero forcing number of a graph.
Definition 2. An n-blocking is a subgraph whose external vertices have degree higher than 2 and internal vertices have degree 2. An example is given in Figure 1. When , we will call this subgraph a 1-blocking.
Lemma 3. (n-Blocking Lemma) If G has no vertices of degree 1 and contains k disjoint blockings of size then Proof. Let be the largest n-blocking on a graph, G with vertices , where and are the endvertices with degree larger than 2. Then define such that . Then each vertex in S has two neighbors outside S and will not skew force, and have degree higher than 2, so they have at least two neighbors outside S and will not skew force, and each inside the n-blocking has exactly 2 neighbors inside S. Since G has no vertices of degree 1, no vertex outside of the n-blocking will skew force either. So, S is skew stalled, and . □
Corollary 1. If G is an odd cycle with a chord that creates an odd cycle of length , then .
Notice that when , this family of graphs is defined by a 1-blocking. This useful result begins our notions of how to characterize all graphs with . The following three lemmas provide useful descriptions of graphs with , specifically surrounding their failed skew stalling sets.
It is possible for a graph where
and there is more than one vertex that is a stalling set. An example of a graph with two different vertices that are both stalling sets is shown in
Figure 2.
In our next lemma we show that it is not possible to have more than 2 different vertices that are each stalling sets.
Lemma 4. Unless , there cannot be more than 2 vertices that are each failed skew zero forcing sets of size 1 in a graph where .
Proof. We will assume that G is not . We then proceed by contradiction. Let G be a graph and where and are vertices that are each failed skew zero forcing sets of size 1. We consider two cases.
Case 1. There does not exist more than two vertices from the set that share a common neighbor. Without loss of generality consider three vertices , and where . Then forms a failed skew zero forcing set of size 2, which contradicts the assumption that .
Case 2. There exists vertices and that share a common neighbor v. Now since each of the vertices and are failed skew zero forcing sets of size 1, all of the neighbors of each , have degree 3 or more. If , , and then Suppose that , , and . Then there is a vertex x where but , and there is a vertex y where but . Hence each of the vertices and has two uncolored neighbors each of which has degree at least 3. Then forms a failed skew zero forcing set of size 3, which contradicts the assumption that .
□
Lemma 5. (Cut vertex lemma) Let G be a graph with a cut vertex v with , and all of the neighbors of v have degree at least 3. Let be the components of where . Then when and when .
Proof. If v is a cut vertex of degree greater than or equal to 2 and its removal divides the graph into two components, the vertex v along with the vertices in the component of larger size (or the same size if the two have equal size) form a failed zero forcing set. To see this note that each vertex in the graph has either 0 or 2 uncolored neighbors. If v is a cut vertex of degree whose removal divides the graph into more than two components we can take the vertices in the largest components and add v. Since each vertex in this set either has 0 or 2 uncolored neighbors, this set is a failed skew zero forcing set. Hence . □
Lemma 6. If and , v cannot have a neighbor of degree 2
Proof. If v has a neighbor, w, of degree 2, then w will skew force its neighbor, u, contradicting that S is skew stalled. So, v cannot have a neighbor of degree 2. □
Definition 3. An even multiple path has vertices u and v with 2 or more even paths connecting them and are buffered on both sides by an even path.
An example of an even multiple path can be seen in the middle of the first graph in
Figure 3. Next, we provide our main result, giving a full characterization of all graphs with
.
Theorem 3. if and only if G is or or G has all five of the following properties.
Exactly 1 disjoint 1-blocking, no more than 2 non-disjoint 1-blockings that share a vertex of degree 3, and no other n-blocking
All degree 2 vertices are in a 1-blocking, an even path with external vertices with higher degree than 2, and even multiple path, or an odd cycle with exactly one vertex of degree higher than 2
There are no pendant even cycles on G and no vertices of degree 1.
Outside of the 1-blocking, no vertex has more than one neighbor of degree 3.
All but one of the exterior vertices of the 1-blockings can have one neighbor that is not in an odd cycle or adjacent to another exterior of a 1-blocking through an even path.
Proof. We know for and by Lemmas 1 and 2. Suppose . We first show that if , then G contains 1 disjoint 1-blocking and no other disjoint n-blocking, satisfying the first criterion.
By the n-blocking lemma, since , if G contains an n-blocking, then , where is the size of each disjoint n-blocking. Hence G contains at most 1 n-blocking where .
To show that G contains at least one disjoint 1-blocking, recall that if is our maximum failed skew stalling set, that unless v is on a the neighbors of v must have degree greater than 2. It remains to confirm that v necessarily has degree 2 which will imply the existence of the 1-blocking.
Suppose . We know its neighbors must have degree higher than 2 since if a neighbor u has degree 1 then would be a stalled set, contradicting the assumption that .
Suppose v is a cut vertex of degree . By Lemma 5, the set S consisting of v and vertices in the largest subsets of is skew stalled.
Next suppose v is not a cut vertex. Since v has no neighbors of degree 2, v must be adjacent to a vertex u, which prevents the creation of a new n-blocking. Recall that . If u has no neighbor of degree 2, let . S is skew stalled with , contradicting the hypothesis that . If u has a neighbor of degree 2, that neighbor must either be part of an even path or an odd cycle. If that neighbor is on an even path, let and skew force along the even path until it skew stalls at the next vertex with degree higher than 2. If it is part of an odd cycle and has a neighbor with degree higher than 2, then S contains only u and the vertices of the cycle to which u belongs. Since u has two uncolored neighbors of degree higher than 2, S is skew stalled with , which contradicts the original hypothesis. Therefore, if , then it must be that .
We still have to consider the case when G has two distinct maximum skew stalling sets of cardinality 1, and . By Lemma 6, neither vertex can have a neighbor of degree 2. Their shared neighbor, u must have degree 3 or will be a skew stalling set.
Suppose first that and . If u is a cut vertex, then by the above lemma, , so u cannot be a cut vertex. If u is not a cut vertex, then its neighbor, x will have degree 2 or higher. If , then set and skew force along the even path until S skew stalls upon reaching some vertices with degree 3 or higher. If and the neighbor of x has degree 3 or higher, then set , which will stall and contradict the original statement of the theorem. So, x has at least one neighbor of degree 2. Then, since u is not a cut vertex, this neighbor may be on an even path or an odd cycle. If x only has a degree 2 neighbor on an odd cycle, then x must have some other degree 3 neighbor that connects to other parts of the graph, since u is not a cut vertex. In that case, S contains x and the vertices of that odd cycle. Otherwise, let and skew force along optional odd cycle and then the even path until it reaches a degree 3 vertex and skew stalls. Then , contradicting the original hypothesis.
Therefore, G contains at most and at least 1 disjoint 1-blocking; G contains exactly 1 disjoint 1 blocking and no other n-blocking if .
Furthermore, suppose there is a degree 2 vertex v in that is not in one of the specified structures of the second criterion. Then v would be in a separate n-blocking, contradicting the first criterion. G cannot have a pendant even cycle since this contradicts the second criteria. If G has a degree 1 vertex, it will skew force its neighbor. If that neighbor is not an element of a maximum failed skew forcing set, this contradicts that . If it is, then this vertex is not in a 1-blocking. For completeness, suppose that this vertex is a maximum skew stalling set. Therefore it cannot have a neighbor of degree 2. By Lemma 5, this would cause , contradicting that . Now suppose a vertex outside the 1-blocking has 2 neighbors of degree higher than 2. Then, this vertex will stall in S but color any neighbors of degree 2. These neighbors are either in an odd cycle or an even path. If they are in an odd cycle, they are all skew forced, but will not be able to spread skew forcing to the rest of the graph, as they only have one vertex of degree higher than 2. If they are on an even path, then skew forcing will stall before the next vertex of degree higher than 2. So, the fourth criterion holds. Finally, if all exterior vertices of 1-blockings have a neighbor that is not in an odd cycle or on an even path connected to another exterior vertex of a 1-blocking. Then if each exterior vertex of the 1-blocking is in S, they will skew force along their neighbors of degree 2, but, since these vertices are in neither an odd cycle nor a 1-blocking, they must be on an even path where skew forcing will stall before the next vertex of degree higher than 3 that is not an exterior vertex of the 1-blocking. Therefore, the theorem holds that if , it must have all of the criteria.
Suppose G satisfies all the conditions. Let v be the first vertex we place in S. Begin with v being the vertex of degree 2 in the 1-blocking. Each neighbor has degree higher than 2. Therefore, S is skew stalled and . Now, there are 5 cases for the different vertices we can start with for v.
(Case 1) Suppose v is the vertex on a nonempty collection of odd cycles with its degree higher than 2. This will skew force the whole collection of odd cycles into S. Then it will follow one of the following cases:
- -
Case 1(a): Let w be a degree 2 neighbor of v in S.
- ∗
Case 1(a) i: w is on a where it will continue to skew force along the path until the next vertex with degree higher than 2 is skew forced into S. Then refer to Case 2.
- ∗
Case 1(a) ii: w is the vertex of degree 2 in a 1-blocking. It will then skew force its neighbor with degree higher than 3, which is the intersection point of a nonempty collection of odd cycles which will be forced or the beginning of one or more even paths, which leads to Case 1(a).
- -
Case 1(b): Let w be a degree 3 neighbor of v.
- ∗
Case 1(b) i: w is the beginning of one or more even paths. Then skew forcing will continue along each path; this case naturally leads to case 1(a).
- ∗
Case 1(b) ii: w is a vertex in the 1-blocking with degree higher than 2. The vertex of degree 2 in the 1-blocking will skew force its neighbor which has degree higher than 2. Then, that vertex is the intersection of a nonempty collection of odd cycles which will now be skew forced, or the beginning of one or more even path(s), which leads to Case 1(a).
Since G does not have any pendant even cycles and no vertex with degree 1, eventually the skew forcing will reach some vertex, z, that is the beginning of a pendant. z cannot be Cases 1(a) or 1(b) since it then would imply the existence of a degree 1 vertex. Furthermore, z cannot be the vertex in Case 2(a) since that would create one or more pendant even cycle(s). So, z is the beginning of a pendant of a nonempty collection of odd cycles. Besides the degree 2 vertex of a 1-blocking, all neighbors of z will be in S. Then all degree 2 neighbors of z will skew force their neighbors and z will skew force that vertex in a 1-blocking if they are neighbors. Now, each vertex in S has at most one neighbor outside of S, so they will skew force their remaining neighbors. Finally, any degree 3 vertex with an edge incident to a nonempty set of odd cycles will skew force the connecting degree 3 vertex and thus skew force the entire set.
(Case 2) Now suppose v is a vertex of degree 2 on an odd cycle. Skew forcing will continue along the cycle until you hit the only vertex with degree higher than 2 on the cycle. At this point, the reader can refer back to the case where that vertex with degree higher than 2 is v.
(Case 3) Suppose v is the exterior point of a 1-blocking. Automatically, the other exterior vertex of the 1-blocking is skew forced. If v shares a common exterior of a 1-blocking with that vertex, that exterior vertex will also be skew forced. So, all exterior vertices of 1-blockings are in S, causing each even path between them to be skew forced. Since there is one exterior vertex with no neighbors besides vertices in an odd cycle or vertices that are connected via an even path to another exterior of a 1-blocking, that exterior vertex will now skew force the degree 2 vertex of the 1-blocking. If any other exterior vertex is adjacent to an even path or multiple even paths that do not lead to another exterior of a 1-blocking, then it will skew force two consecutive vertices along this path, that will end in a nonempty collection of odd cycles or a multiple path, which would lead back to Cases 1 or 2.
(Case 4) Suppose v has degree 2 on an even path. It will then skew force along the path until one of the degree 3 vertices mentioned above is skew forced.
(Case 5) Suppose there are two non-disjoint 1-blockings. Let x and y be the degree 2 vertices in these 1-blockings. Then if , their common vertex has degree 3 and therefore will skew force another vertex, leading to one of the above cases.
Since selecting any vertex other than the degree 2 vertex in a 1-blocking will cause the whole graph to become skew forced, and selecting two degree 2 vertices from a 1-blocking causes the whole graph to become skew forced, we know that . Therefore, . □
From this result, we obtain the following corollary.
Corollary 2. If , G is planar.
Proof. According to Theorem 3, if , then G can be comprised of even paths, even multiple paths, or nonempty odd cycles and one disjoint 1-blocking. Recall that a 1-blocking is an odd path with requirements on vertex degrees. All of these subgraphs are planar and by Theorem 3, they are joined by paths that can be reduced to edges using edge contraction(s). Since planar graphs with planar subgraphs that are joined by edges cannot result in an edge crossing, G must be planar. □
We note that this result cannot be extended as is not planar and .