# Another conjecture of TxGraffiti concerning
zero forcing and domination in graphs

1,2Randy Davila
1Research and Development
RelationalAI
Berkeley, CA 94704, USA
Email<EMAIL_ADDRESS>

2Department of Computational Applied
Mathematics & Operations Research
Rice University
Houston, TX 77005, USA
Email<EMAIL_ADDRESS>

###### Abstract

This paper proves a conjecture generated by the artificial intelligence
conjecturing program called _TxGraffiti_. More specifically, we show that if
$G$ is a connected, cubic, and claw-free graph, then $Z(G)\leq\gamma(G)+2$,
where $Z(G)$ and $\gamma(G)$ denote the zero forcing number and the domination
number of $G$, respectively. Furthermore, we provide a complete
characterization of graphs that achieve this bound. Notably, this bound
improves the known upper bounds for the zero forcing number of connected,
cubic, and claw-free graphs.

Keywords: Automated conjecturing; domination number; _TxGraffiti_ ; zero
forcing number.
AMS subject classification: 05C69

##  1 Introduction

Written by the author in 2017 and tailored towards graph theoretic
conjectures, _TxGraffiti_ is a machine learning and artificially intelligent
program for generating mathematical conjectures suitable for research by
professional mathematicians; now available as an interactive website online
[7]. The name TxGraffiti plays a homage to both the original conjecturing
program _GRAFFITI_ written by Fajtlowicz [13], and its successor program
_Graffiti.pc_ written by DeLaViña [12]. However, the design of TxGraffiti
remains distinct from both GRAFFITI and Graffiti.pc, so the conjectures of
TxGraffiti differ in many instances. One particularly interesting difference
is the ability of TxGraffiti to make particularly strong and interesting
conjectures on _domination_ and _zero forcing_ -related parameters for cubic
graphs. One such example is that if $G\neq K_{4}$ is a connected and cubic
graph, then $Z(G)\leq 2\gamma(G)$, where $Z(G)$ and $\gamma(G)$ denote the
_zero forcing number_ and _domination number_ of $G$, respectively, a
conjecture that was confirmed in [6, 10]. Notably, a similar conjecture of
TxGraffiti relating _total zero forcing_ and _total domination_ for cubic
graphs was also shown to be true in [6, 9]. A more recent conjecture on zero-
forcing made by TxGraffiti states that the zero forcing number is, at most,
the vertex cover number for claw-free graphs, which in turn was confirmed and
led to a larger body of work presented by Brimkov et al. [3]. For TxGraffiti
inspired results that do not concern the zero forcing number of a graph, see
[4], or see the surprising result given by Caro et al. [5], which states that
$\alpha(G)\leq\mu(G)$ for any regular graph $G$, where $\alpha(G)$ and
$\mu(G)$ denote the _independence number_ and _matching number_ of $G$,
respectively.

Though many conjectures of TxGraffiti are confirmed, many more remain open,
and even more remain _undiscovered_. The most well-known of these open
conjectures is likely _the $\alpha$-Z Conjecture_; namely, if $G\neq K_{4}$ is
a connected and cubic graph, then $Z(G)\leq\alpha(G)+1$; see the last page of
Davila’s dissertation [6]. The $\alpha$-Z conjecture has received a
considerable amount of attention with several partial results, including
$Z(G)\leq\alpha(G)+1$, whenever $G\neq K_{4}$ is connected, cubic, and claw-
free [6, 11]. Notably, this partial result was _not conjectured_ by
TxGraffiti, and so, by the design of TxGraffiti, there must exist a more
substantial upper bound for $Z(G)$ in cubic and claw-free graphs in terms of a
graph parameter other than $\alpha(G)$. Thus, we discovered the following
stronger conjecture when explicitly examining the conjectures of TxGraffiti
for connected, cubic, and claw-free graphs.

######  Conjecture 1 (TxGraffiti – confirmed).

If $G$ is a connected, cubic, and claw-free graph, then

$Z(G)\leq\gamma(G)+2,$

and this bound is sharp.

In this paper, we resolve Conjecture 1 in the affirmative, and in doing so,
also characterize graphs attaining equality in its statement. Notably, the
resulting theorem improves on both $Z(G)\leq\alpha(G)+1$ and $Z(G)\leq
2\gamma(G)$ (for $G\neq K_{4}$) whenever $G$ is a connected, cubic, and claw-
free graph.

###  1.1 Notation and Terminology

Throughout this paper, all graphs considered are simple, undirected, and
finite. Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. The
_order_ of $G$ is $n(G)=|V(G)|$. Two vertices $v,w\in V(G)$ are _neighbors_ ,
or _adjacent_ , if $vw\in E(G)$. The _open neighborhood_ of $v\in V(G)$, is
the set of neighbors of $v$, denoted $N_{G}(v)$. The closed neighborhood of
$S\subseteq V$ is $N_{G}[S]=\bigcup_{v\in S}N_{G}[v]$. The _degree_ of a
vertex $v\in V(G)$, denoted $d_{G}(v)$, is equal to $|N_{G}(v)|$. A _cubic
graph_ (also called a _3-regular graph_) is a graph for which every vertex
degree is three. The maximum and minimum degree of $G$ will be denoted
$\Delta(G)$ and $\delta(G)$, respectively. When there is no scope for
confusion, we will use the notation $n=n(G)$, $\delta=\delta(G)$, and
$\Delta=\Delta(G)$, to denote the order, minimum degree, and maximum degree,
respectively.

Two vertices in a graph $G$ are _independent_ if they are not neighbors. A set
of pairwise independent vertices in $G$ is an _independent set_ of $G$. The
number of vertices in a maximum independent set in $G$ is the _independence
number_ of $G$, denoted $\alpha(G)$. A _dominating set_ in $G$ is a subset
$X\subseteq V(G)$, so all vertices in $G$ are either in $X$ or adjacent with
at least one vertex in $X$. The _domination number_ of $G$, denoted by
$\gamma(G)$, is the cardinality of a minimum dominating set in $G$. If
$X\subseteq V(G)$ is a dominating and independent set, then $X$ is an
_independent dominating set_. The minimum cardinality of an independent
dominating set in $G$ is the _independent domination number_ of $G$, denoted
$i(G)$. For more on domination in graphs, see the comprehensive and well-
written text by Haynes, Hedetniemi, and Henning [17].

For a set of vertices $S\subseteq V(G)$, the subgraph induced by $S$ is
denoted by $G[S]$. If $v\in V(G)$, we denote the graph obtained by deleting
$v$ in $G$ by $G-v$. We denote the path, cycle, and complete graph on $n$
vertices by $P_{n}$, $C_{n}$, and $K_{4}$, respectively. A _triangle_ in $G$
is an induced subgraph of $G$ isomorphic to $K_{3}$, whereas a _diamond_ in
$G$ is a subgraph of $G$ isomorphic to $K_{4}$ with one edge missing. A graph
$G$ is _$F$ -free_ if $G$ does not contain $F$ as an induced subgraph. In
particular, if $G$ is $F$-free, where $F=K_{1,3}$, then $G$ is _claw-free_.
Claw-free graphs have been widely studied, and the survey by Flandrin,
Faudree, and Ryjáček [15] is the standard reference for the topic.

Let $S\subseteq V(G)$ be a set of initially “blue-colored” vertices, all
remaining vertices being “white-colored”. The _zero forcing process_ on $G$ is
defined as follows: At each discrete time step, if a blue-colored vertex has a
unique white-colored neighbor, then this blue-colored vertex _forces_ its
white-colored neighbor to become colored blue. The _open $z$-neighborhood_ of
$S$ in $G$, written $N_{G}^{z}(S)$, is the set of all initially white-colored
vertices that change color during the zero forcing process. The _closed
$z$-neighborhood_ of $S$ in $G$ is the set $N_{G}^{z}[S]=S\cup N_{G}^{z}(S)$.
A _valid- $z$-extension rule_ on $S$ is a mapping from $S$ to a new set
$S^{\prime}$, such that $|S|=|S^{\prime}|$ and $N_{G}^{z}[S]\subseteq
N_{G}^{z}[S^{\prime}]$; if in addition $N_{G}^{z}[S]\subset
N_{G}^{z}[S^{\prime}]$, then we say the rule is a _valid- $z$-proper-extension
rule_ on $S$. A set $X\subseteq V(G)$ is _$S$ -reachable_ when $X\subseteq
N_{G}^{z}[S]$. If $V(G)$ is $S$-reachable, and so, $V(G)=N_{G}^{z}[S]$, then
$S$ is a _zero forcing set_ of $G$. The minimum cardinality of a zero forcing
set in $G$ is the _zero forcing number_ of $G$. Zero forcing was introduced in
[1] in the context of linear algebra and has since gained much interest in
graph theory. For more information on zero forcing in graphs, we refer the
reader to the excellent monograph by Hogben, Lin, and Shader [14].

For notation and graph terminology not mentioned here, we refer the reader to
[17]. We also will use the standard notation $[k]=\\{1,\ldots,k\\}$.

##  2 Known Results and Lemmas

In this section, we introduce terminology, recall useful results, and prove
technical lemmas needed for the proof of Conjecture 1. To begin, recall the
following result of Allan and Laskar [2], which states that the independent
domination number equals the domination number for all claw-free graphs.

######  Theorem 2 (Allan and Laskar [2]).

If $G$ is a claw-free graph, then $i(G)=\gamma(G)$.

We will also need the following structural property of connected, cubic, and
claw-free graphs established by Henning and Löwenstein in [18].

######  Lemma 3 (Henning and Löwenstein [18]).

If $G\neq K_{4}$ is a connected, cubic, and claw-free graph, then the vertex
set $V(G)$ can be uniquely partitioned into sets, each of which induces a
triangle or diamond in $G$.

By Lemma 3, the vertex set $V(G)$ of a connected, cubic, and claw-free graph
$G\neq K_{4}$ can be uniquely partitioned into sets, each of which induces
either a triangle subgraph or a diamond subgraph of $G$. We refer to such a
partition of $G$ as a _triangle-diamond_ partition of $G$, abbreviated
$\Delta$-D-partition. Borrowing the terminology introduced in [18], we call
every triangle and diamond induced by our $\Delta$-D-partition a _unit_ of the
partition. A unit that is a triangle is called a _triangle-unit_ and a unit
that is a diamond is called a _diamond-unit_. Note that triangle-units do not
belong to any diamond-unit. Furthermore, we say that two units are adjacent if
an edge joins a vertex in one unit to a vertex in another and that a vertex is
adjacent to a unit whenever the vertex has a neighbor.

Figure 1: The diamond-necklace $N_{4}$ with a minimum zero forcing set shown
by blue colored vertices and a minimum dominating set shown by the red dashed
circles.

Henning and Löwenstein also introduced the notation and definition of a
_diamond-necklace_ , which is now restated. For $k\geq 2$ an integer, let
$N_{k}$ be the connected and cubic graph constructed as follows. Take $k$
disjoint copies $D_{1},D_{2},...,D_{k}$ of a diamond, where
$V(D_{i})=\\{a_{i},b_{i},c_{i},d_{i}\\}$ and where $a_{i}b_{i}$ is the missing
edge in $D_{i}$. Let $N_{k}$ be obtained from the disjoint union of these $k$
diamonds by adding the edges $\\{a_{i}b_{i+1}\>|\>i\in[k-1]\\}$ and adding the
edge $a_{k}b_{1}$. We call $N_{k}$ a _diamond-necklace_ with $k$ diamonds; see
Figure 1 for the diamond-necklace $N_{4}$. Let
$\mathcal{N}_{cubic}=\\{N_{k}\>|\>k\geq 2\\}$. The complete graph $K_{4}$ may
actually be thought of as a loop diamond-necklace, and so, we define
$\mathcal{N}_{cubic}^{*}=\mathcal{N}_{cubic}\cup\\{K_{4}\\}$. In [6, 8], it
was established that if $G\in\mathcal{N}_{cubic}$, then
$Z(G)=\frac{1}{4}n(G)+2$. This together with the fact that
$Z(K_{4})=3=\frac{1}{4}n(K_{4})+2$, imply the following lemma.

######  Lemma 4.

If $G\in\mathcal{N}_{cubic}^{*}$ has order $n$, then $Z(G)=\frac{1}{4}n+2$.

Let $D$ be a diamond-unit in the $\Delta$-D-partition of a cubic and claw-free
graph $G$ and let $V(D)=\\{a,b,c,d\\}$ denote the vertex set of $D$, where
$ab$ is the missing edge in $D$. Then, the only neighbors of vertices $b$ and
$c$, are vertices contained in $V(D)$, and as a consequence of this, we obtain
the following lemma.

######  Lemma 5.

If $D$ is a diamond-unit in a $\Delta$-D-partition of the cubic and claw-free
graph $G$, and if $X\subseteq V(G)$ is a dominating set of $G$, then $V(D)\cap
X\neq\emptyset$.

A trivial lower bound for the domination number of any graph $G$ of order $n$
and maximum degree $\Delta$, is $\gamma(G)\geq\frac{n}{\Delta+1}$. Thus, for a
cubic graph $G$ of order $n$, we have the lower bound
$\gamma(G)\geq\frac{n}{4}$. Let $D_{1},D_{2},...,D_{k}$ be the diamond-units
in the diamond-necklace $N_{k}$, where
$V(D_{i})=\\{a_{i},b_{i},c_{i},d_{i}\\}$ and where $a_{i}b_{i}$ is the missing
edge in $D_{i}$, and let $n$ be the order of $N_{k}$. It is easy to see that
$X=\\{c_{1},\dots,c_{k}\\}$ is dominating set of $N_{k}$, where
$|X|=\frac{n}{4}$. This, together with the lower bound
$\gamma(N_{k})\geq\frac{n}{4}$, imply that $X$ is a minimum dominating set for
$N_{k}$, and so, $\gamma(N_{k})=\frac{n}{4}$. This result can be combined with
Lemma 4, implying the following formula for the zero forcing number of
diamond-necklaces in terms of the domination number.

######  Lemma 6.

If $G\in\mathcal{N}_{cubic}^{*}$, then $Z(G)=\gamma(G)+2$.

The following result improves on the statement of Conjecture 1 when the graph
$G$ has no diamond-unit in its $\Delta$-D-partition.

######  Lemma 7.

If $G$ is a connected and cubic graph with a spanning 2-factor consisting only
of triangles, then $Z(G)\leq\gamma(G)+1$.

###### Proof.

Let $G$ be a connected and cubic graph with a spanning 2-factor consisting
only of triangles. Thus, $G$ is connected, cubic, and claw-free, where every
unit in the $\Delta$-D-partition of $V(G)$ is a triangle-unit. Thus, $G$ is
diamond-free. We next define the _contraction multigraph_ of $G$, denoted
$M_{G}$, to be the multigraph whose vertices correspond to the triangle-units
in the $\Delta$-D-partition of $G$, and where two vertices of $M_{G}$ are
joined by the number of edges joining the corresponding triangle-units in $G$.
By construction, $M_{G}$ has no loops but does possibly contain multiedges.
Note that $n(M_{G})$ is precisely the number of triangle-units in $G$. Since
$G$ contains at least two triangle-units, it must be the case that
$n(M_{G})\geq 2$. Moreover, each vertex of $M_{G}$ has degree three, and so,
$M_{G}$ is a cubic multigraph. For each $v\in V(M_{G})$, let
$V(T_{v})=\\{a_{v},b_{v},c_{v}\\}$ denote the vertices of the triangle-unit in
$G$ associated with $v$. Further, we say that $T_{v}$ is derived from $v$ in
$M_{G}$.

Let $X\subseteq V(G)$ be a minimum (independent) dominating set of $G$ and let
$Y=V(G)\setminus X$. Thus, every vertex of $G$ not in $X$ has a neighbor in
$X$, and no two vertices in $X$ are endpoints of the same edge in $G$; also,
$|X|=\gamma(G)$. Further note that if $T$ is a triangle-unit in the
$\Delta$-D-partition of $V(G)$, then either $T$ contains precisely one vertex
from $X$ (recall $X$ is an independent set), or each of the triangle-units
adjacent with $T_{v}$ contains a vertex from $X$. Since $G$ is a cubic graph
and every vertex not in $X$ has a neighbor in $X$, next observe
$\Delta(G[Y])=2$. Therefore, $G[Y]$ is either a path, a cycle, or a disjoint
union of paths and cycles. In the following two initialization procedures, we
define how to color a set of blue vertices using the dominating set $X$, from
which we construct a zero forcing set of $G$.

Path Initialization. If $G[Y]$ contains at least one path component, let

$H_{G}:b_{v_{1}}a_{v_{2}}\dots b_{v_{\ell}}c_{v_{\ell}}$

be a maximum path component of $G[Y]$, and note that $H_{G}$ corresponds to
the path

$H_{M}:v_{1},v_{2},\dots,v_{\ell},$

in the multigraph $M_{G}$. Next, color blue the vertices in
$S=X\cup\\{b_{v_{1}}\\}$ and color white the vertices in $V(G)\setminus S$.
Under this coloring of the vertices in $V(G)$, observe that the only white-
colored neighbor of $b_{v_{1}}$ is $c_{v_{1}}$, and so, the zero forcing
process may begin by $b_{v_{1}}$ forcing $c_{v_{1}}$ to become colored blue.
After $c_{v_{1}}$ becomes colored blue, then the only possibly white-colored
neighbor of $c_{v_{1}}$ would be $b_{v_{2}}$, and so, $c_{v_{1}}$ may then
$b_{v_{2}}$ to become colored blue. This process continues until
$b_{v_{\ell}}$ become colored blue, and thereafter forces $c_{v_{\ell}}$ to
become colored blue; see Figure 2. Thus, all vertices in the path component
$H_{G}$ become colored blue, and more so, the derived triangle-units from the
vertices of $H_{M}$ contain only blue-colored vertices. If $G[Y]$ does not
contain a path component, move to the next initialization procedure.

$T_{v_{1}}$$T_{v_{2}}$$T_{v_{\ell-1}}$$T_{v_{\ell}}$$b_{v_{1}}$$a_{v_{1}}$$c_{v_{1}}$$b_{v_{2}}$$a_{v_{2}}$$c_{v_{2}}$$b_{v_{\ell-1}}$$a_{v_{\ell-1}}$$c_{v_{\ell-1}}$$b_{v_{\ell}}$$a_{v_{\ell}}$$c_{v_{\ell}}$$\dots$
Figure 2: The the initialization procedure when $G[Y]$ contains a path
component. The initial set $S$ of blue colored vertices in $G$ shown with dark
blue color, whereas forcing steps and color changes indicated by directed
arrows and light blue colored vertices; dominating vertices indicated by red
dashed circles.

Cycle Initialization. If $G[Y]$ does not contain a path component, then let

$H_{G}:b_{v_{1}}a_{v_{2}}\dots b_{v_{\ell}}c_{v_{\ell}b_{v_{1}}},$

be a largest cycle component of $G[Y]$, where

$H_{M}:v_{1}v_{2}\dots v_{\ell}v_{1},$

is a corresponding cycle (allowing 2-cycles) in the multigraph $M_{G}$. Since
$G$ is cubic, claw-free, and diamond-free, a vertex from the dominating set
$X$ of $G$ will dominate at most two vertices on the cycle component $H_{G}$,
and if so, then these two vertices must be neighbors on the component $H_{G}$.
Moreover, if a vertex of $w\in X$ dominates exactly one vertex in $H_{G}$, say
$b\in V(H)$, then $H$ is the cycle $C_{3}$, for otherwise, $v$ and its two
neighbors in $H$ together with $w$ would induce the claw $K_{1,3}$, a
contradiction. Thus, since $n(H)\geq 3$, at least one pair of vertices in
$H_{G}$, say $v_{1}$ and $v_{\ell}$ (renaming if need be), which are dominated
by distinct vertices in $X$. Thus, $a_{v_{1}}$ is the unique vertex dominating
vertices in the triangle-unit derived from $v_{1}$, and $a_{v_{\ell}}$ is the
unique vertex dominating the triangle-unit derived from $v_{\ell}$. Next color
blue the vertices in
$S=(X\setminus\\{a_{v_{\ell}}\\})\cup\\{b_{v_{1}},c_{v_{1}}\\}$ and color
white the vertices in $V(G)\setminus S$.

Under this coloring of vertices in $V(G)$, observe that the only white-colored
neighbor of $b_{v_{1}}$ is $c_{v_{\ell}}$ and the only white colored neighbor
of $c_{v_{1}}$ is $b_{v_{2}}$. Thus, the zero forcing process may begin by
having $b_{v_{1}}$ force $c_{v_{\ell}}$ to become colored blue, and also
having $c_{v_{1}}$ force $b_{v_{2}}$ to become colored blue. Thereafter, the
only white-colored neighbor of $c_{v_{1}}$ would be $b_{v_{2}}$, and so,
$c_{v_{1}}$ may then force $b_{v_{2}}$ to become colored blue, and this
process continues until $b_{v_{\ell}}$ becomes colored blue. Then after
$b_{v_{\ell}}$ becomes colored blue, recall that $b_{v_{1}}$ had previously
forced $c_{v_{\ell}}$ to become colored blue. Thus, the only currently white-
colored neighbor of $b_{v_{\ell}}$ is $a_{v_{\ell}}$, and so, $b_{v_{\ell}}$
would now force $a_{v_{\ell}}$ to become colored blue; see Figure 3 for an
illustration. Thus, all vertices in the cycle $H_{G}$ become colored blue, and
more so, the derived triangle-units from the vertices of $H_{M}$ contain only
blue-colored vertices.

$T_{v_{1}}$$T_{v_{2}}$$T_{v_{\ell-1}}$$T_{v_{\ell}}$$b_{v_{1}}$$a_{v_{1}}$$c_{v_{1}}$$b_{v_{2}}$$a_{v_{2}}$$c_{v_{2}}$$b_{v_{\ell-1}}$$a_{v_{\ell-1}}$$c_{v_{\ell-1}}$$b_{v_{\ell}}$$a_{v_{\ell}}$$c_{v_{\ell}}$$\dots$
Figure 3: The the initialization procedure when $G[Y]$ does not contain a path
component. The initial set $S$ of blue colored vertices in $G$ shown with dark
blue color, whereas forcing steps and color changes indicated by directed
arrows and light blue colored vertices; dominating vertices indicated by red
dashed circles.

Let $S\subseteq V(G)$ be the set of vertices obtained by either of the above
initialization techniques. and thereafter, allow the zero forcing process to
start and continue until no further color changes are possible. By the
construction of the initial set of blue colored vertices in $S$, observe the
following properties:

  * •

$|S|=|X|+1$.

  * •

All vertices in the dominating set $X$ of $G$ are currently blue-colored.

  * •

Each of triangle-units derived from the subgraph $H_{M}$ contain blue-colored
vertices in $G$.

  * •

$X$ is reachable from $S$.

If all vertices of $G$ have become blue-colored, then $S$ is a zero forcing
set of $G$, and so,

$Z(G)\leq|S|=|X|+1=\gamma(G)+1.$

Hence, we may assume that not all vertices of $G$ are reachable by $S$ since
the desired result follows otherwise.

Suppose the zero forcing process stopped before all vertices in $V(G)$ become
blue-colored. By constructing $S$, we know that all vertices in $P_{G}$ are
currently blue-colored, and further, that any derived triangle-unit from a
vertex in $H_{M}$ will only contain blue-colored vertices in $G$. We will now
track color changes in $G$ through associated color changes in the triangle-
units of $G$, which we now define in terms of the multigraph $M_{G}$. For a
given blue and white coloring of $V(G)$ and a vertex $v\in V(M_{G})$, we say
that $v$ (and also $T_{v}$) is _$\frac{k}{3}$ -blue-colored_ whenever
$V(T_{v})$ contains exactly $k$ blue currently colored vertices in $G$, where
$k\in[3]$; see Figure 4. Thus, there is a duality between blue and white
colorings of $V(G)$ and $\frac{k}{3}$-blue colorings of the triangle-units in
$G$. That is, a coloring of $V(G)$ implies a coloring of the triangle-units of
$G$ and vice versa. We define a _blue-white-open_ edge to be an edge of $G$
with a blue-colored endpoint in a $\frac{3}{3}$-blue-colored triangle-unit and
a white-colored endpoint in an adjacent triangle-unit.

$\frac{0}{3}$-blue colored$\frac{1}{3}$-blue colored$\frac{2}{3}$-blue
colored$\frac{3}{3}$-blue colored Figure 4: The different types of
$\frac{k}{3}$-blue colorings of the triangle-units in $G$ as given in the
proof of Lemma 7.

The following two claims significantly simplify the monitoring of color
changes in $G$ regarding the derived triangle units from vertices in $M_{G}$.

######  Claim 1.

Let $v$ and $w$ be two adjacent vertices of $M_{G}$ adjacent by at least one
blue-white-open edge in $G$. If $v$ is $\frac{3}{3}$-blue-colored and $w$ is
$\frac{1}{3}$-blue-colored, then $w$ becomes $\frac{3}{3}$-blue-colored by
zero forcing color changes in $G$.

###### Proof.

Let $v$ and $w$ be two adjacent vertices of $M_{G}$ which are adjacent by at
least one blue-white-open edge in $G$. Recalling our choice of notation, let
$T_{v}=\\{a_{v},b_{v},c_{v}\\}$ and $V(T_{w})=\\{a_{w},b_{w},c_{w}\\}$ denote
the vertices of the derived triangle-units from $v$, and $w$, respectively.
Suppose $v$ is $\frac{3}{3}$-blue colored and $w$ is $\frac{1}{3}$-blue
colored, where $a_{v}a_{w}$ is a blue-white-open edge connecting $v$ to $w$.
Since $w$ is $\frac{1}{3}$-blue colored, this supposition implies exactly one
of the vertices in $\\{b_{w},c_{w}\\}$ is currently blue-colored, say $c_{w}$.
Moreover, since $v$ is $\frac{3}{3}$-blue-colored, $a_{w}$ is the only white-
colored neighbor of the blue-colored vertex $a_{v}$ in $G$. Thus, $a_{v}$ may
force $a_{w}$ to become blue-colored. After $a_{w}$ becomes blue-colored, the
only white-colored neighbor of $a_{w}$ would be $b_{w}$, and so, $a_{w}$ may
then force $b_{w}$ to become blue-colored. Therefore, by these aforementioned
color changes in $G$, the vertex $w$ in $M_{G}$ becomes $\frac{3}{3}$-blue
colored. ($\Box$)

######  Claim 2.

Let $v$ and $w$ be two adjacent vertices of $M_{G}$. If $v$ is
$\frac{3}{3}$-blue-colored and $w$ is $\frac{2}{3}$-blue-colored, then $w$
will become $\frac{3}{3}$-blue-colored by way of zero forcing color changes in
$G$.

###### Proof.

Let $v$ and $w$ be two adjacent vertices of $M_{G}$, and suppose $v$ is
$\frac{3}{3}$-blue-colored and $w$ is $\frac{2}{3}$-blue-colored. Recalling
our choice of notation, let $T_{v}=\\{a_{v},b_{v},c_{v}\\}$ and
$V(T_{w})=\\{a_{w},b_{w},c_{w}\\}$ denote the vertices of the derived
triangle-units from $v$, and $w$, respectively. Let $a_{v}a_{w}$ be an edge of
$G$ connecting the triangle-units $T_{v}$ and $T_{w}$. Since $v$ is
$\frac{3}{3}$-blue-colored, every vertex in $V(T_{v})$ is blue-colored in $G$.
Since $w$ is $\frac{2}{3}$-blue-colored, exactly two of the vertices in
$V(T_{w})$ are blue-colored in $G$. If $a_{w}$ is white-colored, then $b_{w}$
and $c_{w}$ are blue-colored in $G$. With this supposition, $a_{w}$ would then
be the only white-colored neighbor of $a_{v}$, and so, $a_{v}$ would then
force $a_{w}$ to become blue-colored, resulting in $w$ becoming
$\frac{3}{3}$-blue-colored. If $a_{w}$ were currently blue-colored, then
exactly one of the vertices in $\\{b_{w},c_{w}\\}$ is blue-colored, say
$c_{w}$. Thus, since $a_{v}$ is blue-colored, the only white-colored neighbor
of $a_{w}$ would be $b_{w}$, and so, $a_{w}$ would then force $b_{w}$ to
become blue-colored. Hence, $w$ becomes $\frac{3}{3}$-blue-colored. ($\Box$)

With the above claims proven, we now return to the current state of blue and
white colored vertices in $V(G)$. Since each vertex in $H_{M}$ is
$\frac{3}{3}$-blue-colored, we know the current set of $\frac{3}{3}$-blue-
colored vertices is nonempty. Let $B$ be the current set of
$\frac{3}{3}$-blue-colored vertices in $M_{G}$. Since $M_{G}$ is a connected
multigraph, and not all vertices of $G$ are blue-colored, at least one vertex
of $M_{G}$ must exist that is (noninclusive) adjacent to a vertex in $B$. Let
$w\in V(M_{G})$ be a vertex adjacent to the set $B$ in $M_{G}$. Note that $w$
cannot be $\frac{0}{3}$-blue-colored, since if so, one of the vertices in $B$
would have forced onto $T_{w}$ making $w$ at least $\frac{1}{3}$-blue-colored.
If $w$ were $\frac{2}{3}$-blue-colored, then by Claim 2, $w$ would become
$\frac{3}{3}$-blue-colored, and hence belong to $B$. Thus, $w$ must be
$\frac{1}{3}$-blue-colored. However, by Claim 1, if $w$ were adjacent with $B$
by at least one blue-white-open edge in $G$, then $w$ would become
$\frac{3}{3}$-blue-colored, and hence belong to $B$. Hence, $w$ is
$\frac{1}{3}$-blue-colored, and no edge connecting $w$ to $B$ is blue-white-
open. Both endpoints of exactly one edge connecting $w$ to $B$ are blue-
colored.

Since we are assuming that $S$ is not a zero forcing set $G$, we now define a
collection of _extension rules_ that modify the set $S$ so that after each
application of the said rule, more vertices become colored blue; also we
maintain the cardinality of our original set $S$. For each rule we introduce,
we will formally state it and then prove a claim for its validity. For
example, see the first simple rule given below.

######  Extension Rule I.

Let $w\notin B$ be adjacent with $v\in B$ in $M_{G}$. If $a_{v}a_{w}$ is the
edge connecting $v$ to $w$ in $G$ and $a_{v}$ did not force during the zero
forcing process previously, then

$S\leftarrow(S\setminus\\{a_{w}\\})\cup\\{b_{w}\\}.$

######  Claim 3.

Extension Rule I is a valid-$z$-proper-extension rule on $S$.

###### Proof.

Let $w\notin B$ is adjacent with $v\in B$ in $M_{G}$. Recalling our choice of
notation, let $T_{v}=\\{a_{v},b_{v},c_{v}\\}$ and
$V(T_{w})=\\{a_{w},b_{w},c_{w}\\}$ denote the vertices of the derived
triangle-units from $v$, and $w$, respectively. Next, suppose $a_{v}a_{w}$ is
the edge connecting $v$ to $w$ in $G$, and, further, that $a_{v}$ did not
force during the zero forcing process previously. Note $a_{w}$ is blue-
colored. Let $S^{\prime}=(S\setminus\\{a_{w}\\})\cup\\{b_{w}\\}$, and so,
$|S^{\prime}|=|S|$. Thus, it remains to show $N_{G}^{z}[S]\subset
N_{G}^{z}[S^{\prime}]$. Since $a_{v}$ did not force a color change during the
zero forcing process, and since $b_{w}$ and $c_{w}$ are white-colored,
removing $a_{w}$ does not affect any color changes that occurred by applying
the zero forcing process on $S$ in $G$. Thus, all color changes due to $S$
will also occur with $S^{\prime}$. In particular, at some point in the zero
forcing process, each vertex in the triangle-unit $T_{v}$ is colored blue,
after which $a_{w}$ would be the only white-colored neighbor of $a_{v}$.
Therefore, $a_{v}$ may then force $a_{w}$ to become colored blue. Thus,
$N_{G}^{z}[S]\subseteq N_{G}^{z}[S^{\prime}]$. However, since $b_{w}\notin
N_{G}^{z}[S]$ and $b_{w}\in N_{G}^{z}[S^{\prime}]$, we establish
$N_{G}^{z}[S]\subset N_{G}^{z}[S^{\prime}]$, and the desired result follows.
($\Box$)

By Claim 3, we may apply Extension Rule I as many times as needed, always
producing a new initial set of $S$ of blue-colored vertices in $G$ and always
maintaining $|S|=|X|+1$. If we eventually arrive at a set $S$ of blue-colored
vertices so that all of $V(G)$ becomes blue-colored, then $S$ is a zero
forcing set of $G$. Thus,

$Z(G)\leq|S|=|X|+1=\gamma(G)+1.$

Therefore, we will assume that not all of $V(G)$ has become blue-colored since
otherwise, the desired result will follow.

Let $z$ be a $\frac{1}{3}$-blue colored vertex of $M_{G}$ adjacent with the
set $B$ and note that Extension Rule I implies the blue-colored vertex of
$T_{z}$ was not originally colored in the set $S$. Thus, the blue-colored
vertex in $T_{z}$ must have originally been white-colored and become blue-
colored by the zero forcing process in $G$. Let $a_{z}$ be the vertex of
$T_{z}$ that became blue-colored during the zero forcing process in $G$, and
so, $a_{z}$ is the endpoint of some edge whose other endpoint is in $B$. There
are two possible cases for the vertices in the triangle-unit $T_{z}$
concerning the dominating set $X$ of $G$; either $V(T_{z})\cap X\neq\emptyset$
or $V(T_{z})\cap X=\emptyset$; see Figure 5. If $a_{z}\in X$, we are in the
configuration shown by Figure 5 (a). In this case, recall that all vertices of
$X$ are currently colored blue (either in $S$ or by some forcing step). Thus,
$b_{z}$ and $c_{z}$ belong to some component of $G[Y]$, say $H_{G}^{z}$, and
this component is either a path or a cycle. We are considering both
possibilities now.

$a_{v}$$a_{z}$$b_{z}$$c_{z}$$T_{z}$(a)$a_{v}$$a_{z}$$b_{z}$$c_{z}$$T_{z}$(b)
Figure 5: (a) The vertex $a_{v}\in X$ forces $a_{z}\notin X$ to become blue-
colored. (b) The vertex $a_{v}\notin X$ forces $a_{z}\in X$ to become blue-
colored. In both instances, the dominating vertex of the configuration is
indicated by the red dashed circle.

Suppose first that $a_{v}\in X$ forces a neighbor $a_{z}$ to become blue-
colored. Since $b_{z}$ and $c_{z}$ must be dominated by a vertex in $X$,
$b_{z}$ and $c_{z}$ have a neighbor in $X$, say $a_{x}$ and $a_{w}$,
respectively. Since all vertices of $X$ are reachable from $S$, we remark that
$a_{x}$ and $a_{w}$ are currently blue-colored.

We next introduce an Extension Rule for handling this case, provided Extension
Rule I has been applied as many times as possible prior.

######  Extension Rule II.

Let $z\notin B$ be adjacent with $v\in B$ in $M_{G}$. If $a_{v}\in X$ forces
$a_{z}\notin X$ to become blue-colored, then

$S\leftarrow(S\setminus\\{a_{w}\\})\cup\\{b_{z}\\}.$

######  Claim 4.

Extension Rule II is a valid-$z$-proper-extension rule on $S$

###### Proof.

Note that since the $\Delta$-D-partition of $V(G)$ contains no diamond-unit,
$a_{x}\neq a_{w}$. Let $S^{\prime}=(S\setminus\\{a_{w}\\})\cup\\{b_{z}\\}$,
and so, $|S^{\prime}|=|S|$. Thus, it remains to show $N_{G}^{z}[S]\subset
N_{G}^{z}[S^{\prime}]$. If any neighbor of $a_{w}$ forced during the zero
forcing process under the coloring starting with $S$, then all vertices of the
triangle-unit $T_{y}$ would necessarily be colored blue, which implies that
$y$ was $\frac{3}{3}$-blue-colored. Thus, $y$ may force onto $T_{z}$ across
the blue-white-open edge $a_{w}c_{z}$. By Claim 1, $T_{z}$ would then become
$\frac{3}{3}$-blue-colored, a contradiction since $b_{z}$ and $c_{z}$ are
currently white-colored. Thus, no neighbor of $a_{w}$ forces a color change
during the zero forcing process starting with $S$. Therefore, all color
changes previously due to $S$ will also occur by starting the zero forcing
process with $S^{\prime}$. In particular, at some point of the zero forcing
process, $a_{v}$ will force $a_{z}$ to become blue-colored. Thereafter, the
only white-colored neighbor of $a_{z}$ would be $c_{z}$, so $a_{z}$ may force
$c_{z}$ to become blue-colored. After $c_{z}$ becomes blue-colored, the only
white-colored neighbor of $c_{z}$ would be $a_{w}$, and so, $c_{w}$ may force
$a_{w}$ to become blue-colored. Thus,
$N_{G}^{z}[S^{\prime}]=N_{G}^{z}[S]\cup\\{b_{z},c_{z}\\}$. Hence,
$N_{G}^{z}[S]\subset N_{G}^{z}[S^{\prime}]$, and the proof of the claim is
finished. ($\Box$)

$a_{v}$$a_{z}$$b_{z}$$c_{z}$$a_{w}$$b_{w}$$c_{w}$$a_{x}$$b_{x}$$c_{x}$$T_{z}$$T_{w}$$T_{x}$
Figure 6: The vertex $a_{v}\in X$ forces $a_{w}\notin X$ to become blue-
colored

Apply Extension Rule II, and note that (as seen in the proof of Claim 4), that
$x$ may become $\frac{3}{3}$-blue-colored by applying Extension Rule I, while
we do not yet have a rule for $w$. Continue the zero forcing process and apply
Extension Rule I whenever possible until no further color changes are
possible. If $w$ does not become $\frac{3}{3}$-blue-colored, then we are in
the case as seen by Figure 5 (b), and we proceed to the following two
extension rules given below; otherwise $y$ becomes $\frac{3}{3}$-blue-colored
and we may once again apply Extension Rule II. That is, you are not allowed to
apply Extension Rule II again unless you have first ensured that all triangle-
units containing a _“swapped dominating vertex”_ used by an extension rule are
$\frac{3}{3}$-blue-colored. Since $a_{w}$ is a dominating vertex, we note that
$b_{w}$ and $c_{w}$ must belong to some component of $G[Y]$, say $H_{G}^{w}$.

Suppose that $H_{G}^{w}$ is a path component of $G[Y]$. Denote to the vertices
of this component by $H_{G}^{w}:b_{w_{1}}c_{w_{1}}\dots
b_{w_{\ell}}c_{w_{\ell}}$, and denote the associated vertices (triangle-units)
in $M_{G}$ by $H_{M}^{w}:w_{1}w_{2}\dots w_{\ell}$. Note for some
$i\in[\ell]$, $a_{w_{i}}=a_{w}$, $b_{w_{i}}=b_{w}$, and $c_{w_{i}}=c_{w}$.
Since $H_{G}^{w}$ is a path component of $G[Y]$ and since $G$ is cubic, the
enpoints of $H_{G}^{w}$ are necessarily adjacent with two vertices from the
dominating set $X$ of $G$, say $a_{y^{\prime}}$ and $a_{w_{1}}$ for
$b_{w_{1}}$, and $a_{w_{\ell}}$ and $a_{y^{\prime\prime}}$ for $c_{w_{\ell}}$;
see Figure 7 for an illustration of this configuration. The following
extension rule addresses this possibility.

$a_{w_{1}}$$b_{w_{1}}$$a_{y^{\prime}}$$c_{w_{1}}$$T_{w_{1}}$$\dots$$a_{v}$$a_{w_{i}}$$b_{w_{i}}$$c_{w_{i}}$$T_{w_{i}}$$\dots$$a_{w_{\ell}}$$b_{w_{\ell}}$$c_{w_{\ell}}$$a_{y^{\prime\prime}}$$T_{w_{\ell}}$
Figure 7: A dominating vertex $a_{w_{i}}$ is forced to become blue-colored and
belongs to a path in the multigraph $M_{G}$.

######  Extension Rule III.

Let $a_{v}$ be a vertex that forced the dominating vertex $a_{w_{i}}$ in the
triangle-unit $T_{w_{i}}$ with vertex set
$V(T_{w_{i}})=\\{a_{w_{i}},b_{w_{i}},c_{w_{i}}\\}$. If the component $H_{G}$
containing $b_{w_{i}}$ and $c_{w_{i}}$ is a path, then

$S\leftarrow(S\setminus\\{a_{y^{\prime\prime}}\\})\cup\\{b_{w_{i}}\\},$

where $a_{y^{\prime\prime}}$ is adjacent with $c_{w_{\ell}}$ (and
$a_{y^{\prime\prime}}\notin T_{w_{i}}$).

With the following claim, we establish the validity of Extension Rule III.

######  Claim 5.

Extension Rule III is a valid-$z$-proper-extension rule on $S$.

###### Proof.

Let $S^{\prime}=(S\setminus\\{a_{y^{\prime\prime}}\\})\cup\\{b_{w_{i}}\\}$,
and so, $|S^{\prime}|=|S|$. Thus is remains to show that $N_{G}^{z}[S]\subset
N_{G}^{z}[S^{\prime}]$. If any neighbor of $a_{y^{\prime\prime}}$ forced
during the zero forcing process under the coloring starting with $S$, then all
vertices of the triangle-unit $T_{y^{\prime\prime}}$ would necessarily be
blue-colored, which implies that $y^{\prime\prime}$ was $\frac{3}{3}$-blue-
colored. Thus, $y^{\prime\prime}$ may then forced onto $T_{w_{\ell}}$ across
the blue-white-open edge $a_{y^{\prime\prime}}b_{w_{\ell}}$. By Claim 1,
$T_{w_{\ell}}$ would then become $\frac{3}{3}$-blue-colored. There after,
$T_{w_{\ell}}$ could then force onto $T_{w_{\ell-1}}$ by the blue-white-open
edge $b_{w_{\ell}}c_{w_{\ell-1}}$, which in turn would make $w_{\ell-1}$ a
$\frac{3}{3}$-blue-colored vertex. This process would continue until $w_{i}$
is forced onto, making it a $\frac{3}{3}$-blue-colored vertex, a contradiction
since $b_{w_{i}}$ and $c_{w_{i}}$ are currently white-colored. Thus, no
neighbor of $a_{y^{\prime\prime}}$ forces a color change during the zero
forcing process starting with $S$. Therefore, all color changes previously due
to $S$ will also occur by starting the zero forcing process at $S^{\prime}$.

$a_{w_{1}}$$b_{w_{1}}$$a_{x}$$c_{w_{1}}$$T_{w_{1}}$$\dots$$a_{v}$$a_{w_{i}}$$b_{w_{i}}$$c_{w_{i}}$$T_{w_{i}}$$\dots$$a_{w_{\ell}}$$b_{w_{\ell}}$$c_{w_{\ell}}$$a_{y}$$T_{w_{\ell}}$
Figure 8: An illustration of applying Extension Rule III.

Let the zero forcing process begin from $S^{\prime}$ until $a_{w_{i}}$, after
which, $c_{w_{i}}$ would then be the only white-colored neighbor of
$a_{w_{i}}$. Thus, $a_{w_{i}}$ may then force $c_{w_{i}}$ to become blue
colored. After $c_{w_{i}}$ becomes blue-colored, $w_{i}$ would be a
$\frac{3}{3}$-blue-colored vertex of $M_{G}$. Moreover, $w_{i}$ is connected
to the $\frac{1}{3}$-blue-colored neighbors $w_{i-1}$ and $w_{i+1}$ by blue-
white-open edges $c_{w_{i-1}}b_{w_{i}}$ and $c_{w_{i}}b_{w_{i+1}}$,
respectively. By Claim 1, $w_{i-1}$ and $w_{i+1}$ would then become
$\frac{3}{3}$-blue-colored. Thereafter, this process would continue until both
$w_{1}$ and $w_{\ell}$ become $\frac{3}{3}$-blue-colored. After $w_{\ell}$
becomes $\frac{3}{3}$-blue-colored, the only white colored neighbor of
$c_{w_{\ell}}$ would be $a_{y^{\prime\prime}}$, and so, $c_{w_{\ell}}$ may
then force $a_{y^{\prime\prime}}$ to become blue-colored; see Figure 8 for an
illustration. Note that all vertices in the dominating set $X$ of $G$ remain
reachable from $S^{\prime}$. Thus, $N_{G}^{z}[S]\subset
N_{G}^{z}[S^{\prime}]$, and the proof of the claim is finished. ($\Box$)

If $H_{G}^{w}$ was not a path component of $G[Y]$, then $H_{G}^{w}$ is
necessarily a cycle component of $G[Y]$. Denote to the vertices of this
component by $H_{G}^{w}:b_{w_{1}}c_{w_{1}}\dots
b_{w_{\ell}}c_{w_{\ell}}b_{w_{1}}$, and denote the associated vertices
(triangle-units) in $M_{G}$ by $H_{M}^{w}:w_{1}w_{2}\dots w_{\ell}w_{1}$. Note
for some $i\in[\ell]$, $a_{w_{i}}=a_{w}$, $b_{w_{i}}=b_{w}$, and
$c_{w_{i}}=c_{w}$. configuration.

$a_{w_{1}}$$b_{w_{1}}$$c_{w_{1}}$$T_{w_{1}}$$\dots$$a_{v}$$a_{w_{i}}$$b_{w_{i}}$$c_{w_{i}}$$T_{w_{i}}$$\dots$$a_{w_{\ell}}$$b_{w_{\ell}}$$c_{w_{\ell}}$$T_{w_{\ell}}$
Figure 9: A dominating vertex $a_{w_{i}}$ is forced to become blue-colored and
is on a cycle of the multigraph $M_{G}$.

We introduce the following extension rule to deal with cycle components of
$G[Y]$.

######  Extension Rule IV.

Let $a_{v}$ be a vertex that forced the dominating vertex $a_{w_{i}}$ in the
triangle-unit $T_{w_{i}}$ with vertex set
$V(T_{w_{i}})=\\{a_{w_{i}},b_{w_{i}},c_{w_{i}}\\}$. If the component $H_{G}$
containing $b_{w_{i}}$ and $c_{w_{i}}$ is a cycle, then

$S\leftarrow(S\setminus\\{a_{w_{\ell}}\\})\cup\\{b_{w_{i}}\\},$

where $a_{y^{\prime\prime}}$ is adjacent with $c_{w_{\ell}}$ (and
$a_{y^{\prime\prime}}\notin T_{w_{i}}$).

The following claim verifies the validity of Extension Rule IV.

######  Claim 6.

Extension Rule IV is a valid-$z$-proper-extension rule on $S$.

###### Proof.

Let $S^{\prime}=(S\setminus\\{a_{w_{\ell}}\\})\cup\\{b_{w_{i}}\\}$, and so,
$|S^{\prime}|=|S|$. Note that we have only swapped one vertex from the
dominating set $X$ of $G$; see Extension Rule II. Thus, no vertex $a_{w_{j}}$,
for $j\in[\ell]\setminus\\{i\\}$, has been forced to become blue-colored by
the zero forcing process in $G$; that is, each of these vertices is initially
blue-colored in $S$. If vertex adjacent with $a_{w_{\ell}}$ was contained in a
$\frac{3}{3}$-blue-colored triangle-unit, then we could have applied Extension
Rule I and then forced $w_{\ell}$ to become $\frac{3}{3}$-blue-colored. If
$a_{w_{\ell}}$ was not contained in a $\frac{3}{3}$-blue-colored triangle-
unit, then necessarily no neighbor of $a_{w_{\ell}}$ forced a color change
during the zero forcing process starting with $S$. Thus, all color changes
under the set $S$ will also occur from starting with set $S^{\prime}$.

$a_{w_{1}}$$b_{w_{1}}$$c_{w_{1}}$$T_{w_{1}}$$\dots$$a_{v}$$a_{w_{i}}$$b_{w_{i}}$$c_{w_{i}}$$T_{w_{i}}$$\dots$$a_{w_{\ell}}$$b_{w_{\ell}}$$c_{w_{\ell}}$$T_{w_{\ell}}$
Figure 10: An illustration of applying Extension Rule IV.

Starting from the set $S^{\prime}$, let the zero forcing process start and
continue. At some iteration of the zero forcing process, $a_{v}$ will force
$a_{w_{i}}$ to become blue-colored. Thereafter, $c_{w_{i}}$ would be the only
white-colored neighbor of $a_{w_{i}}$. Thus, $a_{w_{i}}$ may then force
$c_{w_{i}}$ to become blue-colored. After $c_{w_{i}}$ becomes blue-colored,
$w_{i}$ would be $\frac{3}{3}$-blue-colored. Thus, $w_{i}$ may then force onto
the triangle-units $T_{w_{i-1}}$ and $T_{w_{i+1}}$ along the blue-white open
edges $b_{w_{i}}c_{w_{i-1}}$ and $c_{w_{i}}b_{w_{i+1}}$, respectively. In
particular, a sequence of color changes occurs until $w_{1}$ becomes
$\frac{3}{3}$-blue-colored. Thereafter, $c_{w_{\ell}}$ is the only white-
colored neighbor of $b_{w_{1}}$, and so, $b_{w_{1}}$ may then force
$c_{w_{\ell}}$ to become blue-colored. Note that $w_{\ell}$ was also forced
onto by $w_{\ell-1}$, and so, $b_{w_{\ell}}$ is blue-colored. Thus, at some
iteration of the zero forcing process starting with $S^{\prime}$,
$a_{w_{\ell}}$ would be the only white-colored neighbor of $c_{w_{\ell}}$.
Hence, $c_{w_{\ell}}$ may then force $a_{w_{\ell}}$ to become colored blue;
see Figure 10 for an illustration. Therefore, $N_{G}^{z}[S]\subset
N_{G}^{z}[S^{\prime}]$, and the proof of the claim is finished. ($\Box$)

Apply Extension Rule III if $H_{G}^{w}$ is a path component of $G[Y]$, and
Extension Rule IV if $H_{G}^{w}$ is a cycle component of $G[Y]$. Thereafter,
allow the zero forcing process to continue and apply Extension Rule I whenever
possibly until no further color changes are possible. If a triangle-unit that
we swapped a dominating vertex does not become $\frac{3}{3}$-blue-colored,
then apply either Extension Rule III or Extension Rule IV, depending on the
component of $G[Y]$ in consideration. After all, borrowed from triangle-units
become $\frac{3}{3}$-blue-colored, apply Extension Rule II if need be and
repeat. Since $G$ is connected, we eventually arrive at a set $S$ of blue-
colored vertices so that all of $V(G)$ becomes blue-colored, and so, the
resulting set $S$ is a zero forcing set of $G$. Thus,

$Z(G)\leq|S|=|X|+1=\gamma(G)+1,$

and the proof of the lemma is finished. ∎

In the next section, we give our proof for Conjecture 1.

##  3 Proof of Conjecture 1

In this section, we prove Conjecture 1 and characterize graphs attaining
equality in its statement.

######  Theorem 8.

If $G$ is a connected, cubic, and claw-free graph, then

$Z(G)\leq\gamma(G)+2,$

if and only if $G\in\mathcal{N}_{\text{cubic}}^{*}$.

###### Proof.

We will proceed by induction on the order $n\geq 4$ of a connected, cubic, and
claw-free graph. If $n=4$, then $G=K_{4}$ implying $Z(G)=\gamma(G)+2$; see
Figure 11 (a). If $n=6$, then $G$ is the prism $C_{3}\>\Box\>K_{2}$ implying
$Z(G)=3<\gamma(G)+2=4$; see Figure 11 (b). If $n=8$, then $G$ is the diamond-
necklace $N_{2}$ which implies $Z(G)=\gamma(G)+2$ by Lemma 6; also see Figure
11 (c). Thus, we have established our base cases. Next, let $n\geq 10$ and
assume that if $G^{\prime}$ is a connected, cubic, and claw-free graph of
order $n^{\prime}$, where $6\leq n^{\prime}<n$, then
$Z(G^{\prime})\leq\gamma(G^{\prime})+2$.

(a) $K_{4}$(b) $C_{3}\>\Box\>K_{2}$(c) $N_{2}$ Figure 11: The complete graph
$K_{4}$, the prism $C_{3}\>\Box\>K_{2}$, and the diamond-necklace $N_{2}$ as
seen in the base cases for the proof of Theorem 1. Minimum zero forcing sets
are shown in dark blue, while forcing steps and color changes are indicated by
directed edges and light blue colored vertices, respectively; minimum
dominating sets shown by red dashed circles.

Let $G$ be a connected, cubic, and claw-free graph with order $n$. If
$G\in\mathcal{N}_{\text{cubic}}^{*}$, then by Lemma 6, $Z(G)=\gamma(G)+2$.
Thus, we may assume that $G\notin\mathcal{N}_{\text{cubic}}^{*}$, since
otherwise the desired result follows. Hence, at least one unit in the
$\Delta$-D-partition of $V(G)$ is a diamond-unit. Since every triangle-unit of
$G$ is joined by three edges to vertices in other units, and since every
diamond-unit is joined by two edges to vertices in other units, it must be the
case that there are at least two triangle-units in our $\Delta$-D-partition.
If $V(G)$ does not contain a diamond-unit in its $\Delta$-D-partition, then
$G$ has a spanning 2-factor consisting of triangles, which by Lemma 7, implies
$Z(G)\leq\gamma(G)+1<\gamma(G)+2$. Thus, we may further assume $G$ contains at
least one diamond since otherwise, the desired result follows. Let $D$ be an
arbitrary diamond-unit in the $\Delta$-D-partition of $V(G)$ and denote the
vertices of $D$ by $V(D)=\\{a,b,c,d\\}$, where $ab$ is the missing edge in
$D$. Let $e$ be the neighbor of $a$, not in $D$, and $f$ be the neighbor of
$b$, not in $f$, where $e\neq f$ because $G$ is claw-free. The vertices $e$
and $f$ may, or may not be adjacent, and we consider these cases with the
following claims.

######  Claim 7.

If $e$ and $f$ are not adjacent, then $Z(G)<\gamma(G)+2$.

###### Proof.

Suppose that $e$ and $f$ are not adjacent. Next, let $e_{1}$ and $e_{2}$ be
the neighbors of $e$ different from $a$, and let $f_{1}$ and $f_{2}$ be the
neighbors of $f$ different from $b$. Since $G$ is claw-free, note that
$\\{e,e_{1},e_{2}\\}$ and $\\{f,f_{1},f_{2}\\}$ both induce triangles in $G$,
say $T_{e}$ and $T_{f}$, respectively. Note that $T_{e}$ and $T_{f}$ share no
common vertex. Moreover, $T_{e}$ and $T_{f}$ are themselves either triangle-
units, or are a part of some diamond-unit in the $\Delta$-D-partition of
$V(G)$; see Figure 12 for an illustration of this configuration.

$e$$e_{1}$$e_{2}$$a$$b$$c$$d$$f$$f_{1}$$f_{2}$ Figure 12: The structure of the
subgraph as seen in the proof of Claim 7.

Let $G^{\prime}$ be the graph obtained from $G$ by deleting the vertices in
$V(G)$ and any edges incident edges from $V(G)$, and then adding the edge
$ef$. Note that $G^{\prime}$ is a connected, cubic, and claw-free graph with
order $n^{\prime}$, where $6\leq n^{\prime}<n$. If the $\Delta$-D-partition of
$V(G^{\prime})$ consists of only diamond-units and no triangle-units, then
$G\in\mathcal{N}_{\text{cubic}}^{*}$, a contradiction our earlier assumption
that $G\notin\mathcal{N}_{\text{cubic}}^{*}$. Thus,
$G^{\prime}\notin\mathcal{N}_{\text{cubic}}$. Hence, the $\Delta$-D-partition
of $V(G^{\prime})$ contains at least one triangle-unit. If $G^{\prime}$ is the
prism $C_{3}\>\Box\>K_{2}$, then renaming vertices if necessary, we may assume
$e_{i}$ and $f_{i}$ are adjacent for $i\in[2]$, which implies that $G$ is the
graph with order $n=10$ shown in Figure 13. The set $\\{c,e,f_{1}\\}$ is a
minimum dominating set of $G$, and the set $\\{c,e,e_{1},f\\}$ is a minimum
zero forcing set of $G$. Thus, $Z(G)=4<\gamma(G)+2=5$. Hence, we may assume
that $G^{\prime}$ is not the prism $C_{3}\>\Box\>K_{2}$ since otherwise, our
desired result follows. We proceed by proving the following two subclaims.

$e$$e_{1}$$e_{2}$$a$$b$$c$$d$$f$$f_{1}$$f_{2}$ Figure 13: The graph $G$ as
seen in Claim 7 given in the proof of Theorem 1. A minimum zero forcing set
shown in dark blue, while forcing steps and color changes are indicated by
directed edges and light blue colored vertices, respectively; a minimum
dominating set shown by red dashed circles.

######  Claim 7.1.

$Z(G)=Z(G^{\prime})+1$

###### Proof.

Let $G$ be a cubic and claw-free graph. Next, let $D$ be an arbitrary diamond-
unit in the $\Delta$-D-partition of $V(G)$ and denote the vertices of $D$ by
$V(D)=\\{a,b,c,d\\}$, where $ab$ is the missing edge in $D$. Let $e$ be the
neighbor of $a$, not in $D$, and $f$ be the neighbor of $b$, not in $f$, where
$e\neq f$ because $G$ is claw-free.Let $S^{\prime}\subseteq V(G^{\prime})$ be
a minimum zero forcing set of $G^{\prime}$. If $f\notin S^{\prime}$, then at
some iteration of the zero forcing process in $G^{\prime}$, a neighbor of $f$
forces $f$ to become colored blue. If $f$ was forced to become colored blue
during the zero forcing process in $G^{\prime}$, let $S=S^{\prime}\cup\\{c\\}$
in $G$. If $e$ was the vertex that forced $f$ to become colored blue in
$G^{\prime}$, starting from the blue coloring $S$ in $G$, at some iteration of
the zero forcing process $e$ would force $a$ to become colored blue. After $a$
becomes colored blue, $d$ would be the only white-colored neighbor of $a$, so
$a$ would then force $d$ to become colored blue. After $d$ becomes colored
blue, $b$ would be the only white-colored neighbor of $d$, so $d$ would then
force $b$ to become colored blue. Finally, after $b$ becomes colored blue, $f$
would be the only white-colored neighbor of $f$, so $d$ would force $f$ to
become colored blue. After $f$ becomes colored blue, all color changes in
$G^{\prime}$ starting from $S^{\prime}$ would now occur in $G$. Thus, $S$ is a
zero forcing set of $G$. Hence, $Z(G)\leq|S^{\prime}|+1=Z(G^{\prime})+1$.
However, since every diamond-unit contains at least one vertex from every zero
forcing set of $G$, it must be the case that $Z(G)=Z(G^{\prime})+1$.

Next, suppose that $f$ was forced to become colored blue by either $f_{1}$ or
$f_{2}$. Without loss of generality, suppose $f_{2}$ forces $f$ to become
colored blue. At some iteration of the zero forcing process in $G$ $f$ is the
only white-colored neighbor of $f_{2}$, so $f_{1}$ was colored blue before $f$
was colored blue. These color changes would still occur in $G$ starting from
the set $S$, after which the only white-colored neighbor of $f$ would be $b$,
and so, $f$ may then force $b$ to become colored blue. After $b$ becomes
colored blue, $d$ would be the only white-colored neighbor, so $b$ would force
$d$ to become colored blue. After $d$ becomes colored blue, $a$ would be the
only white-colored neighbor of $d$, so $d$ would then force $a$ to become
colored blue. At this point of the zero forcing process, all colors that
happened in $G^{\prime}$ would still happen in $G$. Thus, $S$ is a zero
forcing set of $G$. Hence, $Z(G)\leq|S^{\prime}|+1=Z(G^{\prime})+1$. However,
since every diamond-unit contains at least one vertex from every zero forcing
set of $G$, it must be the case that $Z(G)=Z(G^{\prime})+1$. Hence, the result
follows if $f$ was forced to become colored blue during the zero forcing
process on $G^{\prime}$.

Since the above arguments apply to the vertex $e$, we may assume that neither
$e$ nor $f$ become colored blue during the zero forcing process in
$G^{\prime}$. In particular, this implies $e,f\in S^{\prime}$. Next suppose
that at some iteration of the zero forcing process in $G^{\prime}$, $f_{2}$
becomes colored blue. After $f_{2}$ becomes colored blue, the only white-
colored neighbor of $f_{2}$ would be $f_{1}$, and so, $f_{2}$ may then force
$f_{1}$ to become colored blue. After these color changes have in $G^{\prime}$
and $G^{\prime}$, the only white-colored neighbor of $f$ in $G$ would be $b$,
so, $f$ could then force $b$ to become colored blue. After $b$ becomes colored
blue, $d$ would be the only white-colored neighbor, so $b$ would force $d$ to
become colored blue. After $d$ becomes colored blue, $a$ would be the only
white-colored neighbor of $d$, so $d$ would then force $a$ to become colored
blue. At this point of the zero forcing process, all colors that happened in
$G^{\prime}$ would still happen in $G$. Thus, $S$ is a zero forcing set of
$G$. Hence, $Z(G)\leq|S^{\prime}|+1=Z(G^{\prime})+1$. However, since every
diamond-unit contains at least one vertex from every zero forcing set of $G$,
it must be the case that $Z(G)=Z(G^{\prime})+1$. Hence, $Z(G)=Z(G^{\prime})+1$
when any neighbor of $f$ is forced to become colored blue by a vertex
different than $f$ during the zero forcing process on $G^{\prime}$.

Since the above arguments on $f$ also apply to the vertex $e$, we may also
assume that no neighbor of $e$ is forced to become colored blue by a vertex
different than $e$. Our suppositions combined imply that $e$ and $f$ each have
exactly one neighbor, which is not contained in $S^{\prime}$, where these
white-colored neighbors are forced to become colored blue at the start of the
zero forcing process in $G^{\prime}$. Without loss of generality, suppose
$e_{2}$ and $f_{2}$ are initially blue colored in $S^{\prime}$, so $e$ forces
$e_{1}$ to become colored blue and $f$ forces $f_{1}$ to become colored blue.
Next let $S^{\prime\prime}=(S^{\prime}\setminus\\{e\\})\cup\\{f_{1}\\}$ be a
different set of initially blue colored vertices in $G^{\prime}$, and then let
$S=S^{\prime\prime}\cup\\{c\\}$ and note
$|S^{\prime\prime}|=|S^{\prime}|=Z(G)$. Under the new coloring $S$ in $G$,
observe that the only white-colored neighbor of $f$ in $G$ is $b$, and the
only white-colored neighbor of $f$ in $G^{\prime}$ is $e$. Thus, $f$ may force
$b$ to become colored blue in $G$ and $e$ to become colored blue in
$G^{\prime}$. Thus, $S^{\prime\prime}$ is a zero forcing set, implying
$|S^{\prime\prime}|=Z(G^{\prime})$. Next, observe that after $b$ becomes
colored blue in $G$, the only white-colored neighbor of $b$ would be $d$, and
so, $b$ would force $d$ to become colored blue. After $d$ becomes colored
blue, $a$ would be the only white-colored neighbor of $d$, so $d$ would then
force $a$ to become colored blue. After $a$ becomes colored blue, $e$ would be
the only white-colored neighbor of $a$, so $a$ may force $e$ to become colored
blue. After $e$ becomes colored blue in $G$, all color changes in $G^{\prime}$
will now occur in $G$. Thus, $S$ is a zero forcing set of $G$. Hence,
$Z(G)\leq|S^{\prime}|+1=Z(G^{\prime})+1$. However, since every diamond-unit
contains at least one vertex from every zero forcing set of $G$, it must be
the case that $Z(G)=Z(G^{\prime})+1$.

######  Claim 7.2.

$\gamma(G)=\gamma(G^{\prime})+1$

###### Proof.

Let $X^{\prime}\subseteq V(G^{\prime})$ be a minimum (independent) dominating
set of $G^{\prime}$. If both $e$ and $f$ are not in $X^{\prime}$, then clearly
$X=X^{\prime}\cup\\{c\\}$ is a minimum (independent) dominating set of $G$
implying $\gamma(G)=\gamma(G^{\prime})+1$. Thus, we will $X^{\prime}$ contains
either $e$ or $f$. Note that since $e$ and $f$ are adjacent in $G^{\prime}$,
and since $X^{\prime}$ is independent, either $e\in X^{\prime}$ and $f\notin
X^{\prime}$, or $e\notin X^{\prime}$ and $f\in X^{\prime}$. Without loss of
generality, suppose $e\notin X^{\prime}$ and $f\in X^{\prime}$. Then, the set
$X=X^{\prime}\cup\\{a\\}$ is clearly a minimum dominating set of $G$. Thus,
$\gamma(G)=\gamma(G^{\prime})+1$, completing out proof. ($\Box$)

Apply the inductive hypothesis to the graph $G^{\prime}$, and so,

$Z(G^{\prime})<\gamma(G^{\prime})+2.$

By Claim 7.1, $Z(G)=Z(G^{\prime})+1$, and by Claim 7.2,
$\gamma(G)=\gamma(G^{\prime})+1$. Thus,

$Z(G)-1=Z(G^{\prime})<\gamma(G^{\prime})+2=(\gamma(G)-1)+2.$

Hence,

$Z(G)<\gamma(G)+2,$

and the proof of our claim is finished. ($\Box$)

By Claim 7, we may assume that $e$ and $f$ are adjacent in $G$ since
otherwise, the desired inequality follows. Thus, $e$ and $f$ belong to a
common triangle-unit in the $\Delta$-D-partition of $V(G)$, say $T$. Let $g$
be the remaining vertex in the triangle-unit $T$, and let $h$ be the neighbor
of $g$ not in $T$. Further, let $i$ and $j$ be the two vertices in the
triangle containing $h$. If $h$ belongs to a diamond-unit, then choosing this
diamond-unit initially in our argument would bring us back to Claim 7,
implying $Z(G)\leq\gamma(G)+1$. Thus, we may assume that $h$ belongs to a
triangle-unit in the $\Delta$-D-partition of $V(G)$; that is $\\{h,i,j\\}$
form a triangle-unit. Let $k$ and $\ell$ denote the neighbors of $i$ and $j$,
respectively, not contained in $\\{h,i,j\\}$. By assumption, the vertex $h$
does not belong to a diamond-unit, so $k\neq\ell$. The resulting subgraph of
$G$ is illustrated in Figure 14, where $k$ and $\ell$ may be adjacent
vertices.

$a$$b$$c$$d$$e$$f$$g$$h$$i$$j$$k$$\ell$ Figure 14: The subgraph of $G$
appearing towards the end of the proof given for Theorem 1.

Suppose now that the vertex $k$ belongs to a diamond-unit $D^{*}$ in $G$,
which implies that $D^{*}$ also is a diamond-unit of $G^{\prime}$ considered
previously. If the diamond-unit $D^{*}$ does not contain the vertex $\ell$,
then choosing this diamond-unit as our initial diamond-unit $D$ brings us back
to Claim 7, which implies that $Z(G)\leq\gamma(G)+2$.

$a$$b$$c$$d$$e$$f$$g$$h$$i$$j$$k$$\ell$$p$$m$ Figure 15: The graph $G$
appearing in the proof of Theorem 1. A minimum zero forcing set is shown in
dark blue, whereas zero forcing color changes are indicated by directed edges
and lighter blue colored vertices.

We will now assume that the diamond-unit $D^{*}$ contains the vertex $\ell$.
Thus, $G$ is a graph with order $n=14$ shown in Figure 15, where
$V(D^{*})=\\{k,\ell,m,p\\}$. Then, the set $\\{a,c,e,i,m\\}$ is a minimum zero
forcing set of $G$, and the set $\\{c,e,i,m\\}$ is a minimum dominating set of
$G$. Thus,

$Z(G)=5<\gamma(G)+2=7.$

Hence, we may assume that the vertex $k$ belongs to a triangle-unit in the
$\Delta$-D-partition of $V(G)$, since otherwise the desired result follows.

Consider now the connected, cubic, and claw-free graph $G^{\prime}$ with order
$n^{\prime}$ obtained from $G$ by removing the vertices in the set
$\\{e,f,g,h,i,j\\}$ and any edges incident with this set, and then adding the
edges $ak$ and $b\ell$.

######  Claim 8.

$Z(G)\leq Z(G^{\prime})+2$

###### Proof.

Let $S^{\prime}$ be a minimum zero forcing set of $G^{\prime}$ and let $D$ be
the diamond-unit of $G^{\prime}$ (and also of $G$) with vertex set
$V(D)=\\{a,b,c,d\\}$. We will consider the following three subclaims. Suppose
first that $|V(D)\cap S^{\prime}|=3$. In this case Let
$S=S^{\prime}\cup\\{i\\}$. Note that any three vertices of $D$ will zero force
all vertices of $D$ to become colored blue, and so, we assume $S^{\prime}\cap
D=\\{a,b,c\\}$. Then, as shown in Figure 16, all vertices of the subgraph $H$
in $G$ become colored blue. Then, after $k$ and $j$ become colored blue, all
color changes in $G^{\prime}$ will happen in $G$. Thus, $S$ is a zero forcing
set of $G$. Hence,
$Z(G)\leq|S|=|S^{\prime}|+1=Z(G^{\prime})+1<Z(G^{\prime})+2$.

Next suppose $|V(D)\cap S^{\prime}|=2$. In this case, we may assume without
loss of generality that $a\notin S^{\prime}$ and let
$S=S^{\prime}\cup\\{a,i\\}$. Then, as shown in Figure 16, all vertices of the
subgraph $H$ in $G$ become colored blue. Then, after $k$ and $j$ become
colored blue, all color changes in $G^{\prime}$ will happen in $G$. Thus, $S$
is a zero forcing set of $G$. Hence, $Z(G)\leq|S|=|S^{\prime}|+2\leq
Z(G^{\prime})+2$.

$a$$b$$c$$d$$e$$f$$g$$h$$i$$j$$k$$\ell$ Figure 16: The subgraph of $G$
appearing towards the end of the proof given for Theorem 1.

Suppose $|V(D)\cap S^{\prime}|=1$, and so, either $c$ or $d$ belong to
$S^{\prime}$. If Moreover, either $a$ is forced to become colored blue by $i$
in $G^{\prime}$, or $b$ is forced to become colored blue by $\ell$ in
$G^{\prime}$. Without loss of generality suppose $\ell$ forces $b$ to become
colored blue in $G^{\prime}$. Under this assumption we let
$S=S^{\prime}\cup\\{e,i\\}$. Then in $G$, at some point of the zero forcing
process starting with with $S$ as our initial set of blue colored vertices,
$\ell$ would force $j$ to become colored blue, thereafter, all vertices of $H$
become colored blue as shown in Figure 17. ($\Box$)

$a$$b$$c$$d$$e$$f$$g$$h$$i$$j$$k$$\ell$ Figure 17: The subgraph of $G$
appearing towards the end of the proof given for Theorem 1.

######  Claim 9.

$\gamma(G^{\prime})\leq\gamma(G)-2$

###### Proof.

Observe there exists some minimum dominating set of $G$ containing the set of
vertices $\\{c,g,k,\ell\\}$. If $X$ is this dominating set, then the let
$X^{\prime}=X\setminus\\{i,g\\}$ is a dominating set of $G^{\prime}$. Thus,

$\gamma(G^{\prime})\leq|X^{\prime}|=|X|-2=\gamma(G)-2.$

($\Box$)

Now that we have established our final claims, apply the inductive hypothesis
to the graph $G^{\prime}$, and observe

$Z(G^{\prime})<\gamma(G^{\prime})+2.$

Then by Claim 8, $Z(G)\leq Z(G^{\prime})+2$, and by Claim 9,
$\gamma(G^{\prime})=\gamma(G)-2$. Thus,

$Z(G)-2=Z(G^{\prime})<\gamma(G^{\prime})+2\leq(\gamma(G)-2)+2.$

Hence,

$Z(G)<\gamma(G)+2,$

and the proof of the desired result is finished. ∎

##  4 Conclusion

In this paper, we have proven $Z(G)\leq\gamma(G)+2$ for any connected, cubic,
and claw-free graph $G$. This result resolves Conjecture 1 in the affirmative
and so provides further support for the usefulness of the artificial
intelligence program TxGraffiti. Moreover, since $\gamma(G)\leq\alpha(G)$ for
all graphs, Theorem 8 also improves on the bound $Z(G)\leq\alpha(G)+1$ graphs
connected, cubic, and claw-free graphs given in [6, 11]. Indeed,

$Z(N_{k})=\gamma(N_{k})+2<\alpha(N_{k})+1,$

for all diamond-necklaces $N_{k}$ with $k\geq 3$. Furthermore, when the
additional condition that $G$ is claw-free is imposed, Theorem 8 also improves
on the more general bound $Z(G)\leq 2\gamma(G)$ for any connected and cubic
graph $G$, other than $K_{4}$, presented in [6, 10].

By Theorem 8, if $G$ is connected, cubic, and claw-free, then
$Z(G)=\gamma(G)+2$, if and only if $G\in\mathcal{N}_{\text{cubic}}^{*}$. It
therefore seems interesting to find all connected, cubic, and claw-free graphs
for which $Z(G)=\gamma(G)+1$.

######  Question 1.

What connected, cubic, and claw-free graphs with
$G\notin\mathcal{N}_{\text{cubic}}^{*}$ satisfy $Z(G)\leq\gamma(G)+1$ with
equality?

Surprisingly, after completing the proof of Theorem 8, we discovered the
following conjecture of TxGraffiti while prompting it to directly conjecture
on the zero forcing number for all possible combinations of the hypothesis
that included cubic graphs.

######  Conjecture 9 (TxGraffiti – Open).

If $G$ is a connected, cubic, and diamond-free graph, then

$Z(G)\leq\gamma(G)+2,$

and this bound is sharp.

Conjecture 9 was ranked as more substantial than the more well-known
$\alpha$-Z Conjecture, so this conjecture also warrants further investigation.

## References

  * [1] AIM Special Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428(7) (2008), 1628–1648.
  * [2] R. B. Allan and R. Laskar, On domination and independent domination numbers of a graph, _Discrete Math._ , 23(2) (1978), 73–76.
  * [3] B. Brimkov, R. Davila, H. Schuerger, and M. Young, Computer assisted discovery: Zero forcing vs vertex cover. ArXiv preprint https://arxiv.org/pdf/2209.04552, 2023.
  * [4] Y. Caro, R. Davila, M. A. Henning, and R. Pepper, Conjectures of TxGraffiti: Independence, domination, and matchings, _Australas. J. Comb._ , 84(2) (2022), 258–274.
  * [5] Y. Caro, R. Davila, and R. Pepper, Independence, domination, and matchings, _Discuss. Math. Graph Theory_ , 42(3) (2022), 921–935.
  * [6] R. Davila, Total and Zero Forcing in Graphs. _University of Johannesburg, Ph.D Thesis,_ May 2019.
  * [7] R. Davila, _TxGraffiti_ , https://txgraffiti.streamlit.app, accessed 2024-06-19.
  * [8] R. Davila and M. A. Henning, Total forcing and zero forcing in claw-free cubic graphs, Graphs Combin., 34 (2018), 1371–1384.
  * [9] R. Davila and M. A. Henning, Total forcing versus total domination in cubic graphs, Appl. Math. Comput., 354 (2019), 385–395.
  * [10] R. Davila and M. A. Hennings, Relating zero forcing and domination in cubic graphs, J. Comb. Optim., 41 (2021), 553–577.
  * [11] R. Davila and M. A. Henning, Zero forcing in claw-free cubic graphs, _Bull. Malays. Math. Sci. Soc._ , 43 (2020), 673–688.
  * [12] E. DeLaVina, Graffiti.pc: a variant of Graffiti, _DIMACS Ser. Discret. Math. Theor. Comput. Sci._ , 69 (2005), p. 71.
  * [13] E. DeLaVina, Some history of the development of Graffiti, _Graphs and Discovery, DIMACS Ser. Discret. Math. Theor. Comput. Sci._ , vol. 69, Amer. Math. Soc., Providence, RI (2005), 81–118.
  * [14] L. Hogben, J. C.-H. Lin, and B. L. Shader, _Inverse Problems and Zero Forcing for Graphs (AMS Mathematical Surveys and Monographs, 270)_ . ISBN: 978-1-4704-6655-8 (2022).
  * [15] E. Flandrin, R. Faudree, and Z. Ryjáček, Claw-free graph - a survey, _Discrete Math._ ,214 (2016), 196–200.
  * [16] T. Haynes, S. Hedetniemi, and M. A. Henning, _Topics in Domination in Graphs (Springer Developments in Mathematics, 64)_. ISBN: 978-3-031-09495-8 (2021).
  * [17] T. Haynes, S. Hedetniemi, and M. A. Henning, _Domination in Graphs: Core Concepts (Springer Monographs in Mathematics)_. ISBN: 978-3-031-09495-8 (2023).
  * [18] M. A. Henning and C. Löwenstein, Locating-total domination in claw-free cubic graphs. Discrete Math., 312(21) (2012), 3107–3116.