# Isomorphisms and properties of TAR reconfiguration graphs for zero forcing
and other $X$-set parameters

Novi H. Bong Department of Mathematical Sciences, University of Delaware,
Newark, DE 19716, USA<EMAIL_ADDRESS>Joshua Carlson Department of
Mathematics and Computer Science, Drake University, Des Moines, IA 50311, USA
<EMAIL_ADDRESS>Bryan Curtis Department of Mathematics, Iowa State
University, Ames, IA 50011, USA<EMAIL_ADDRESS>Ruth Haas Department of
Mathematics, University of Hawaii at Mānoa, Honolulu, HI 96822, USA
<EMAIL_ADDRESS>Leslie Hogben Department of Mathematics, Iowa State
University, Ames, IA 50011, USA and American Institute of Mathematics, 600 E.
Brokaw Road, San José, CA 95112, USA (hogben@aimath.org).

###### Abstract

An $X$-TAR (token addition/removal) reconfiguration graph has as its vertices
sets that satisfy some property $X$, with an edge between two sets if one is
obtained from the other by adding or removing one element. This paper
considers the $X$-TAR graph for $X-$ sets of vertices of a base graph $G$
where the $X$-sets of $G$ must satisfy certain conditions. Dominating sets,
power dominating sets, zero forcing sets, and positive semidefinite zero
forcing sets are all examples of $X$-sets. For graphs $G$ and $G^{\prime}$
with no isolated vertices, it is shown that $G$ and $G^{\prime}$ have
isomorphic $X$-TAR reconfiguration graphs if and only if there is a relabeling
of the vertices of $G^{\prime}$ such that $G$ and $G^{\prime}$ have exactly
the same $X$-sets. The concept of an $X$-irrelevant vertex is introduced to
facilitate analysis of $X$-TAR graph isomorphisms. Furthermore, results
related to the connectedness of the zero forcing TAR graph are given. We
present families of graphs that exceed known lower bounds for connectedness
parameters.

Keywords reconfiguration; token addition and removal; TAR; vertex; $X$-set;
isomorphism; zero forcing

AMS subject classification 68R10, 05C50, 05C57, 05C60, 05C69

##  1 Introduction

The study of reconfiguration examines relationships among solutions to a
problem. These solutions are modeled as vertices in a graph called a
reconfiguration graph. A reconfiguration rule describes the adjacency
relationship in a reconfiguration graph. When the solutions are sets, the
_token addition or removal rule_ says that two sets $S$ and $S^{\prime}$ are
adjacent in the _TAR reconfiguration graph_ if $S^{\prime}$ can be obtained
from $S$ by adding or removing one element. For our purposes, solutions are
sets of vertices of a graph $G$ defined by a property, such as being a
dominating set, power dominating set, or zero forcing set of $G$, although
reconfiguration is studied more broadly. The graph $G$ is called the _base
graph_. In [4], Bjorkman et al. established various properties of a TAR
reconfiguration graph in a universal framework for parameters that we call
$X$-set parameters (see Definition 1.1), and we call the associated TAR
reconfiguration graphs $X$-TAR graphs. Examples of $X$-set parameters include
the domination number, the power domination number, the zero forcing number,
and the positive semidefinite zero forcing number (definitions of these
parameters are presented later in this introduction).

It is established in Theorems 2.10 and 2.12 that if $G$ and $G^{\prime}$ are
graphs with no isolated vertices that have isomorphic $X$-TAR reconfiguration
graphs, then there is a relabeling of the vertices of $G^{\prime}$ such that
$G$ and $G^{\prime}$ have exactly the same $X$-sets. To prove Theorem 2.12 we
introduce the concept of a set of irrelevant vertices (or an $X$-irrelevant
set). In Section 2.2, $X$-irrelevant sets are used to characterize the
automorphism group of an $X$-TAR graph. There we also discuss the existence
(or nonexistence) of nonempty $X$-irrelevant sets when $X$ is the domination
number, power domination number, zero forcing number, or positive semidefinite
zero forcing number. The study of which $X$-TAR graphs are unique (up to
isomorphism of the base graph and with isolated vertices prohibited) is
parameter-specific, and we examine this question for zero forcing TAR graphs
in Section 2.4.

Connectedness, that is, whether any one feasible solution can be transformed
into any other by the reconfiguration rule, is a fundamental question in the
study of reconfiguration. Connectedness properties seem to be very parameter-
specific. In Section 3 we present results related to connectedness for zero
forcing TAR reconfiguration graphs. This includes exhibiting families of
graphs that exceed known bounds for parameters describing connectedness of the
zero forcing TAR reconfiguration graphs.

All graphs are simple, undirected, finite, and have nonempty vertex sets. Let
$G=(V(G),E(G))$ be a graph. The _neighborhood_ of a vertex $v$ of $G$ is the
set of all vertices adjacent to $v$ and is denoted by $N_{G}(v)$. The _closed
neighborhood_ of $v$ is $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. If $S$ is a set of
vertices of $G$, then $N_{G}[S]=\cup_{x\in S}N_{G}[x]$. Let $G$ be a graph and
color all the vertices of $G$ blue or white. Zero forcing is a process that
changes the color of white vertices to blue by applying the _standard color
change rule_ , i.e., a blue vertex $v$ can force a white vertex $w$ to change
color to blue if $w$ is the only white vertex in the neighborhood of $v$. A
zero forcing set is a set $S\subseteq V(G)$ that can result in all the
vertices of $G$ turning blue by repeated application of the standard color
change rule starting with exactly the vertices in $S$ blue. In the context of
TAR reconfiguration, “solutions” to zero forcing on a graph $G$ are zero
forcing sets. The _zero forcing number_ of $G$, denoted by
$\operatorname{Z}(G)$, is the minimum cardinality of a zero forcing set. The
zero forcing TAR reconfiguration graph allows us to consider all the zero
forcing sets (of various sizes) and the relationships among them for a
particular graph. The study of zero forcing reconfiguration was initiated in
[11], where the token exchange zero forcing reconfiguration graph was studied.
Note that for the zero forcing token exchange reconfiguration graph, only
minimum zero forcing sets are used as vertices and two such sets are adjacent
if one can be obtained from the other by exchanging one vertex.

Positive semidefinite zero forcing is a variant of zero forcing defined by the
_PSD color change rule_ : Let $S$ be the set of blue vertices and let
$W_{1},\dots,W_{k}$ be the sets of vertices of the $k\geq 1$ components of
$G-S$ (the graph obtained from $G$ by deleting the vertices in $S$). If $u\in
S$, $w\in W_{i}$, and $w$ is the only white neighbor of $u$ in $G[W_{i}\cup
S]$, then change the color of $w$ to blue (where $G[U]$ denotes the subgraph
of $G$ induced by the vertices of $U$). A _PSD zero forcing set_ is a set
$S\subseteq V(G)$ that can result in all the vertices of $G$ turning blue by
repeated application of the PSD color change rule starting with exactly the
vertices in $S$ blue. The _PSD zero forcing number_ of $G$, denoted by
$\operatorname{Z_{+}}(G)$, is the minimum cardinality of a PSD zero forcing
set. More information on zero forcing and positive semidefinite zero forcing
can be found in [10].

A set $S$ of vertices of a graph $G$ is a _dominating set_ of $G$ if
$N_{G}[S]=V(G)$ and the _domination number_ $\gamma(G)$ of $G$ is the minimum
cardinality of a dominating set of $G$. A set $S$ of vertices of a graph $G$
is a _power dominating set_ of $G$ if $N_{G}[S]$ is a zero forcing set of $G$,
and the _power domination number_ $\gamma_{P}(G)$ of $G$ is the minimum
cardinality of a power dominating set of $G$. The study of $\gamma$-TAR
reconfiguration was introduced in [12] and $\gamma_{P}$-TAR reconfiguration
was introduced in [4].

In the next two sections we present the definitions of an $X$-set parameter,
its TAR graph, and related parameters, followed by basic results concerning
the zero forcing TAR graph, including determinations of the zero forcing TAR
graphs for several graph families.

###  1.1 $X$-set parameter definitions

The next definition is adapted from [4] (the term $X$-set parameter is new but
the list of conditions in Definition 1.1 is taken from [4, Definition 2.1]).

######  Definition 1.1.

An $X$-set parameter is a graph parameter $X(G)$ defined to be the minimum
cardinality of an $X$-set of $G$, where the $X$-sets of $G$ are defined by a
given property and satisfy the following conditions:

  1. (1)

If $S$ is an $X$-set of $G$ and $S\subseteq S^{\prime}$, then $S^{\prime}$ is
an $X$-set of $G$.

  2. (2)

The empty set is not an $X$-set of any graph.

  3. (3)

An $X$-set of a disconnected graph is the union of an $X$-set of each
component.

  4. (4)

If $G$ has no isolated vertices, then every set of $|V(G)|-1$ vertices is an
$X$-set.

Note that $\operatorname{Z}(G),\operatorname{Z_{+}}(G),\gamma(G),$ and
$\gamma_{P}(G)$ are all $X$-set parameters. Let $X$ be an $X$-set parameter.
The following definitions are adapted from [4]. The $X$ token addition and
removal reconfiguration graph ($X$-TAR graph) of a base graph $G$, denoted by
$\mathscr{X}^{{\tiny\rm TAR}}(G)$, has the set of all $X$-sets of $G$ as the
set of vertices, and there is an edge between two vertices $S_{1}$ and $S_{2}$
of $\mathscr{X}^{{\tiny\rm TAR}}(G)$ if and only if $|S_{1}\ominus S_{2}|=1$
where $A\ominus B=(A\cup B)\setminus(A\cap B)$ denotes the symmetric
difference of sets $A$ and $B$. The $k$-token addition and removal
reconfiguration graph for $X$ of $G$, denoted by $\mathscr{X}^{{\tiny\rm
TAR}}_{k}(G)$, is the subgraph of $\mathscr{X}^{{\tiny\rm TAR}}(G)$ induced by
the set of all $X$-sets of cardinality at most $k$. The maximum cardinality of
a minimal $X$-set of $G$ is the _upper $X$-number_ of $G$ and is denoted by
$\overline{X}(G)$.

When the vertices of a TAR graph represent a collection of solutions to a
problem and an edge represents the application of a transformation rule from
one solution to another, then that TAR graph is connected if and only if
within the collection any solution can be transformed to any other by repeated
application of the transformation rule. Observe that $\mathscr{X}^{{\tiny\rm
TAR}}(G)$ is connected for any graph $G$. Thus determining for which $k$ the
$k$-TAR is connected is a main theme of the study of TAR graph reconfiguration
and connectedness is also a theme of other types of reconfiguration. The least
$k$ such that $\mathscr{X}^{{\tiny\rm TAR}}_{k}(G)$ is connected is denoted by
$\underline{x_{0}}(G)$. The least $k$ such that $\mathscr{X}^{{\tiny\rm
TAR}}_{i}(G)$ is connected for $k\leq i\leq|V(G)|$ is denoted by $x_{0}(G)$.

The disjoint union of graphs $G$ and $H$ is denoted by $G\sqcup H$ and
$rK_{1}$ denotes $r$ isolated vertices. As noted in [4], if $G$ is a graph
with has no isolated vertices, $G^{\prime}=G\sqcup rK_{1}$, and $X$ is an
$X$-set parameter, then $X(G^{\prime})=X(G)+r$, $\mathscr{X}^{{\tiny\rm
TAR}}_{k+r}(G^{\prime})\cong\mathscr{X}^{{\tiny\rm TAR}}_{k}(G)$, and
$\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})\cong\mathscr{X}^{{\tiny\rm
TAR}}(G)$. Thus it suffices to study $X$-TAR reconfiguration graphs with no
isolated vertices.

The _order_ of a graph $G$ is the cardinality of $V(G)$. The maximum degree
and minimum degree of $G$ are denoted $\Delta(G)$ and $\delta(G)$
respectively. It is well known (and easy to see) that
$\delta(G)\leq\operatorname{Z}(G)$. Let $G$ be a graph of order $n\geq 2$ with
no isolated vertices. As noted in [4], $\Delta(\mathscr{X}^{{\tiny\rm
TAR}}(G))=n$. Observe that an $X$-set $S\neq V(G)$ of $G$ has
$\deg_{\mathscr{X}^{{\tiny\rm TAR}}_{|S|+1}(G)}(S)=n$ if and only if
$S\setminus\\{x\\}$ is an $X$-set for every $x\in S$.

###  1.2 Zero forcing TAR graphs

Next we implement definitions in Section 1.1 for zero forcing.

######  Definition 1.2.

The _zero forcing token addition and removal ( $\operatorname{Z}$-TAR) graph_
of a base graph $G$, denoted by $\mathscr{Z}^{{\tiny\rm TAR}}(G)$, has the set
of all zero forcing sets of $G$ as the set of vertices, and there is an edge
between two vertices $S_{1}$ and $S_{2}$ of $\mathscr{Z}^{{\tiny\rm TAR}}(G)$
if and only if $|S_{1}\ominus S_{2}|=1$. The zero forcing $k$-token addition
and removal reconfiguration graph of $G$, denoted by $\mathscr{Z}^{{\tiny\rm
TAR}}_{k}(G)$, is the subgraph of $\mathscr{Z}^{{\tiny\rm TAR}}(G)$ induced by
the set of all zero forcing sets of cardinality at most $k$.

######  Definition 1.3.

The maximum cardinality of a minimal zero forcing set of a graph $G$ is the
_upper zero forcing number_ of $G$ and is denoted by
$\overline{\operatorname{Z}}(G)$. The least $k$ such that
$\mathscr{Z}^{{\tiny\rm TAR}}_{k}(G)$ is connected is denoted by
$\underline{z_{0}}(G)$. The least $k$ such that $\mathscr{Z}^{{\tiny\rm
TAR}}_{i}(G)$ is connected for each $i=k,\dots,|V(G)|$ is denoted by
$z_{0}(G)$.

It was shown in [3] that a graph with no isolated vertices has more than one
minimum zero forcing set and no vertex is in every minimum zero forcing set.
Let $G$ be a graph that has no isolated vertices. Since a minimal zero forcing
set of cardinality $k$ has no neighbors in $\mathscr{Z}^{{\tiny\rm
TAR}}_{k}(G)$, $\mathscr{Z}^{{\tiny\rm TAR}}_{k}(G)$ is not connected whenever
there is a minimal zero forcing set of cardinality $k$. In particular,
$\mathscr{Z}^{{\tiny\rm TAR}}_{\operatorname{Z}(G)}(G)$ and
$\mathscr{Z}^{{\tiny\rm TAR}}_{\overline{\operatorname{Z}}(G)}(G)$ are not
connected. Brimkov and Carlson constructed an example of an infinite family of
graphs $G_{n}$ with $\operatorname{Z}(G_{n})=5$ and
$\overline{\operatorname{Z}}(G_{n})=n-2$ in [6].

Next we determine the zero forcing TAR reconfiguration graphs and related
parameters for several families of graphs. The complete graph is denoted by
$K_{n}$ and $K_{1,r}$ denotes the star with $r$ leaves (where a _leaf_ is a
vertex of degree one); the _center vertex_ of $K_{1,r}$ is the vertex of
degree $r$.

######  Proposition 1.4.

For $n\geq 2$, $\mathscr{Z}^{{\tiny\rm TAR}}(K_{n})=K_{1,n}$. Furthermore,
$\overline{\operatorname{Z}}(K_{n})=\operatorname{Z}(K_{n})=n-1$ and
$z_{0}(K_{n})=\underline{z_{0}}(K_{n})=n$.

###### Proof.

It is well known (and immediate from $\delta(K_{n})=n-1$) that
$\operatorname{Z}(K_{n})=n-1$ and the zero forcing sets of $K_{n}$ consist of
all subsets of vertices of $K_{n}$ that contain at least $n-1$ vertices. Thus
$\mathscr{Z}^{{\tiny\rm TAR}}(K_{n})=K_{1,n}$. Since $\mathscr{Z}^{{\tiny\rm
TAR}}_{\operatorname{Z}(G)}(G)$ is disconnected for any connected graph that
has order at least two, $z_{0}(K_{n})=\underline{z_{0}}(K_{n})=n$. ∎

If $G_{1}$ and $G_{2}$ are disjoint, the _Cartesian product_ of $G_{1}$ and
$G_{2}$, denoted by $G_{1}\square G_{2}$, is the graph with $V(G\square
G^{\prime})=V(G_{1})\times V(G_{2})$ such that $(v_{1},v_{2})$ and
$(u_{1},u_{2})$ are adjacent if and only if (1) $v_{1}=u_{1}$ and
$v_{2}u_{2}\in E(G_{2})$, or (2) $v_{2}=u_{2}$ and $v_{1}u_{1}\in E(G_{1})$.
Figure 1.1 illustrates the next result.

$\small{\\{1,2,3\\}}$$\small{\\{1,2\\}}$$\small{\\{2,3\\}}$$\small{\\{1,3\\}}$$\small{\\{0,1,2\\}}$$\small{\\{0,2,3\\}}$$\small{\\{0,1,3\\}}$$\small{\\{0,1,2,3\\}}$
Figure 1.1: $\mathscr{Z}^{{\tiny\rm TAR}}(K_{1,3})$

######  Proposition 1.5.

Let $r\geq 2$. Then $\mathscr{Z}^{{\tiny\rm TAR}}(K_{1,r})=K_{1,r}\square
K_{2}$. Furthermore,
$\overline{\operatorname{Z}}(K_{1,r})=\operatorname{Z}(K_{1,r})=r-1$ and
$z_{0}(K_{1,r})=\underline{z_{0}}(K_{1,r})=r$.

###### Proof.

Let $V(K_{1,r})=\\{0,1,\ldots,r\\}$ where $0$ is the unique vertex of degree
$r$. The collection of zero forcing sets of $K_{1,r}$ can be partitioned as

$T_{1}=\\{V(K_{1,r})\\}\cup\\{S\subseteq V(K_{1,r}):|S|=r\text{ and }0\in
S\\}$

and

$T_{2}=\\{V(K_{1,r})\setminus\\{0\\}\\}\cup\\{S\subseteq
V(K_{1,r}):|S|=r-1\text{ and }0\notin S\\}.$

Observe that the induced subgraph of $\mathscr{Z}^{{\tiny\rm TAR}}(K_{1,r})$
on either $T_{1}$ or $T_{2}$ is $K_{1,r}$. Further, zero forcing sets
$S_{1}\in T_{1}$ and $S_{2}\in T_{2}$ are adjacent in $\mathscr{Z}^{{\tiny\rm
TAR}}(G)$ if and only if $S_{2}=S_{1}\setminus\\{0\\}$. Thus
$\mathscr{Z}^{{\tiny\rm TAR}}(K_{1,r})=K_{1,r}\square K_{2}$.

It is immediate from the list of zero forcing sets that
$\overline{\operatorname{Z}}(K_{1,r})=\operatorname{Z}(K_{1,r})=r-1$ and
$z_{0}(K_{1,r})=\underline{z_{0}}(K_{1,r})=r$. ∎

######  Remark 1.6.

Let $n\geq 3$. It is well known that a set $S\subseteq V(C_{n})$ is a zero
forcing set of $C_{n}$ if and only if $S$ contains two consecutive vertices.
Thus $\operatorname{Z}(C_{n})=\overline{\operatorname{Z}}(C_{n})=2$ and
$z_{0}(C_{n})=\underline{z_{0}}(C_{n})=3$.

Next we apply results established for TAR graphs of $X$-set parameters in [4]
and known properties of zero forcing to the zero forcing TAR graph and related
parameters. The $t$ dimensional hypercube $Q_{t}$ can be defined recursively
in terms of the Cartesian product as $Q_{0}=K_{1}\mbox{ and
}Q_{t}=Q_{t-1}\square K_{2}.$

######  Theorem 1.7.

[4] Let $G$ be a graph of order $n\geq 2$ with no isolated vertices. Then

  1. 1.

$\Delta(\mathscr{Z}^{{\tiny\rm TAR}}(G))=n$.

  2. 2.

If $n\geq 2$, then $\delta(\mathscr{Z}^{{\tiny\rm
TAR}}(G))=n-\overline{\operatorname{Z}}(G)$.

  3. 3.

$\overline{\operatorname{Z}}(G)+1\leq
z_{0}(G)\leq\min\\{\overline{\operatorname{Z}}(G)+\operatorname{Z}(G),n\\}$.

  4. 4.

If $\operatorname{Z}(G)=1$, then $z_{0}(G)=\overline{\operatorname{Z}}(G)+1$

  5. 5.

For every $k\geq\operatorname{Z}(G)$, $\mathscr{Z}^{{\tiny\rm TAR}}_{k}(G)$ is
a subgraph of $Q_{n}$. Thus $\mathscr{Z}^{{\tiny\rm TAR}}_{k}(G)$ is
bipartite.

  6. 6.

No zero forcing TAR graph is isomorphic to a hypercube.

The next result is immediate since $K_{2}=Q_{1}$.

######  Corollary 1.8.

There does not exist a graph $G$ such that $\mathscr{Z}^{{\tiny\rm
TAR}}(G)=K_{2}$.

Theorem 1.7 allows us to show that the values of certain parameters of the
base graphs of isomorphic zero forcing TAR graphs must be equal.

######  Corollary 1.9.

[4] Let $G$ and $G^{\prime}$ be graphs with no isolated vertices. If
$\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm
TAR}}(G^{\prime})$, then

  1. 1.

$|V(G)|=|V(G^{\prime})|$,

  2. 2.

$\operatorname{Z}(G)=\operatorname{Z}(G^{\prime})$, and

  3. 3.

$\overline{\operatorname{Z}}(G)=\overline{\operatorname{Z}}(G^{\prime})$.

##  2 Irrelevant sets and TAR graph isomorphisms

The TAR reconfiguration graph of an $X$-set parameter carries a great deal of
information about the $X$-sets of $G$, but the information about $X$-sets of
$G$ does not generally determine $G$; in particular, the information about
zero forcing sets of $G$ sets does not generally determine $G$.

We show that for graphs $G$ and $G^{\prime}$ with no isolated vertices,
$\mathscr{X}^{{\tiny\rm TAR}}(G)\cong\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$
implies there is a relabeling of the vertices of $G^{\prime}$ such that $G$
and $G^{\prime}$ have exactly the same $X$-sets (see Theorem 2.12). When
applied to zero forcing, $\mathscr{Z}^{{\tiny\rm
TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm TAR}}(G^{\prime})$ implies $G$ and
$G^{\prime}$ necessarily have the same the zero forcing polynomials (as
defined in [5], see Section 2.3). Showing that an isomorphism of zero forcing
TAR graphs implies that their base graphs have the same the zero forcing
polynomial triggered this study of isomorphisms.

Irrelevant sets are introduced in Section 2.1 to prove that if
$\mathscr{X}^{{\tiny\rm TAR}}(G)\cong\mathscr{X}^{{\tiny\rm
TAR}}(G^{\prime})$, then there is an isomorphism that preserves the
cardinality of $X$-sets (see Theorem 2.10). The focus of Section 2.1 is
proving Theorem 2.12, but irrelevant sets are interesting in their own right
(and exhibit significant differences among various $X$-set parameters). These
ideas are discussed in Section 2.2.

In Section 2.4 we establish that certain zero forcing TAR graphs are unique up
to isomorphism of the base graph (assuming the base graph has no isolated
vertices), and also show that a cycle and a cycle with one chord have the same
zero forcing TAR graphs (see Proposition 2.30).

###  2.1 Isomorphisms of the TAR graph

There is a natural poset structure on the vertices of $X$-TAR reconfiguration
graphs whose partial ordering is determined by set inclusion. This poset
structure can be used to better understand the isomorphisms between $X$-TAR
reconfiguration graphs. We begin this subsection with a result showing that
the vertices of induced hypercubes of $X$-TAR reconfiguration graphs are
intervals in the aforementioned poset. To formally state this result, we
recall some basic poset terminology found in [13].

Let $Y$ be a set and $P=(Y,\leq)$ be a poset. An element $u\in Y$ is maximal
(respectively, minimal) if $u\not<y$ (respectively, $u\not<y$) for each $y\in
Y$. Elements $u,v\in Y$ are comparable provided $u\leq v$ or $v\leq u$. If
$u\leq v$ in $P$, then the set $[u,v]=\\{y:u\leq y\leq v\\}$ is called an
interval. A chain is a poset such that each pair of elements is comparable.
The _length_ of a chain $C$ is $|C|-1$ and the length of the interval $[u,v]$
is the maximum length of a chain in $[u,v]$ and is denoted by $\ell(u,v)$.

For a set $T$, let $\mathcal{P}(T)$ denote the power set of $T$. We remark
that $\mathscr{X}^{{\tiny\rm TAR}}(G)$ is a join-semilattice contained in
$(\mathcal{P}(V(G)),\subseteq)$ and
$\ell(S,S^{\prime})=\operatorname{dist}(S,S^{\prime})$ for any interval
$[S,S^{\prime}]$ in $\mathscr{X}^{{\tiny\rm TAR}}(G)$ since $S$ and
$S^{\prime}$ are comparable (where $\operatorname{dist}(S,S^{\prime})$ is the
distance in the graph $\mathscr{X}^{{\tiny\rm TAR}}(G)$).

######  Lemma 2.1.

Let $X$ be an $X$-set parameter, let $t\geq 0$ be an integer, let $G$ be a
graph on $n$ vertices, and let $H$ be an induced subgraph of
$\mathscr{X}^{{\tiny\rm TAR}}(G)$. If $H\cong Q_{t}$, then $V(H)$ is an
interval of length $t$ in the poset $(\mathcal{P}(V(G)),\subseteq)$.

###### Proof.

The claim is obvious for $t=0,1$. Suppose that $t\geq 2$. We begin by showing
that $(V(H),\subseteq)$ has exactly 1 maximal element.

Assume, to the contrary, that $(V(H),\subseteq)$ has at least 2 maximal
elements $u$ and $v$. Since $H$ is connected, there exists a path from $u$ to
$v$ in $H$. Every path $P$ from $u$ to $v$ in $H$ can be written in the form
$uy_{1}\cdots y_{i}v$. For each such $P$, let $d_{P}$ to be the smallest index
$k$ such that $y_{k-1}\subseteq y_{k}$, where $y_{0}=u$ and $y_{i+1}=v$. Note
that since $u$ and $v$ are maximal in $(V(H),\subseteq)$, $d_{P}\geq 2$ is
always defined.

Let $d$ be the minimum $d_{P}$ amongst all paths $P$ from $u$ to $v$ in $H$.
Pick a path $P^{*}$ in $H$ of the form $ux_{1}\cdots x_{i}v$ such that
$d_{P^{*}}=d$, and let $x_{0}=u$ and $x_{i+1}=v$. Then $x_{d-1}\subseteq
x_{d-2}$ because $x_{d-2}\not\subseteq x_{d-1}$ and $x_{d-2}$ is adjacent to
$x_{d-1}$. Since $x_{d-2}$ and $x_{d}$ have $x_{d-1}$ as a common neighbor and
each pair of vertices in a hypercube share exactly 0 or 2 common neighbors,
there exists some vertex $w\not=x_{d-1}$ in $H$ that is adjacent to $x_{d-2}$
and $x_{d}$. By our choice of $d$, $w\subseteq x_{d-2}$ and $w\subseteq x_{d}$
or else $P^{\prime}=ux_{1}\dots x_{d-2}wx_{d}\dots x_{i}v$ would be a path
with $d_{P^{\prime}}<d_{P^{*}}$ since $w=x_{d-2}\cup x_{d}$. Hence
$x_{d-2}\cap x_{d}=w$. This is absurd since $x_{d-2}\cap x_{d}=x_{d-1}$ and
$w\not=x_{d-1}$.

Thus, $H$ has exactly 1 maximal element $T$. A similar argument shows $H$ has
exactly 1 minimal element $S$ in the subset partial ordering of
$\mathscr{X}^{{\tiny\rm TAR}}(G)$. Thus, $S\subseteq R\subseteq T$ for every
$R\in V(H)$. Since $H\cong Q_{t}$,
$\operatorname{dist}(S,T)\leq\operatorname{diam}(Q_{t})=t$. So there are at
most $2^{t}$ elements in the interval $[S,T]$. But $|V(H)|=|V(Q_{t})|=2^{t}$.
Therefore, $\operatorname{dist}(S,T)=t$ and $V(H)=[S,T]$. ∎

######  Remark 2.2.

We remark that the proof of Lemma 2.1 is really an argument about cover
graphs. For a poset $(Y,\leq)$ and $x,y\in Y$, we say that $y$ covers $x$
provided $x<y$ and there is no $z\in Y$ such that $x<z<y$. The cover graph or
_Hasse diagram graph_ of $P$ is the simple graph with vertices in $Y$ and an
edge $uv$ if and only if $u$ covers $v$, or $v$ covers $u$. Lemma 2.1 says
that if $G\cong Q_{t}$, then $V(G)$ is an interval in
$(\mathcal{P}(Y),\subseteq)$.

######  Lemma 2.3.

Let $X$ be an $X$-set parameter, let $G$ and $G^{\prime}$ be graphs. Suppose
$\varphi:\mathscr{X}^{{\tiny\rm TAR}}(G)\to\mathscr{X}^{{\tiny\rm
TAR}}(G^{\prime})$ is an isomorphism. Let $S^{\prime}=\varphi(V(G))$. If
$Y^{\prime}$ is a minimal $X$-set of $G^{\prime}$, then $Y^{\prime}\subseteq
S^{\prime}$.

###### Proof.

Let $Y^{\prime}$ be a minimal $X$-set of $G^{\prime}$. Define
$Y=\varphi^{-1}(Y^{\prime})$. The interval $[Y,V(G)]$ in
$(\mathcal{P}(V(G),\subseteq)$ forms an induced $Q_{t}$ in
$\mathscr{X}^{{\tiny\rm TAR}}(G)$ for some integer $t>0$. By Lemma 2.1,
$\varphi([Y,V(G)])$ is an interval $[Z^{\prime},W^{\prime}]$ in
$(\mathcal{P}(V(G^{\prime})),\subseteq)$. Since $Y^{\prime}$ is a minimal
$X$-set of $G^{\prime}$, $Z^{\prime}=Y^{\prime}$. Thus, $Y^{\prime}\subseteq
S^{\prime}$. ∎

Some zero forcing TAR graphs have automorphisms that do not preserve the
cardinality of the zero forcing sets that are the vertices of the TAR graph
(see Example 2.5). The next definition allows us to manage that issue.

######  Definition 2.4.

Let $G$ be a graph. We say that a vertex $v\in V(G)$ is $X$-irrelevant if
$x\not\in S$ for every minimal $X$-set $S$ of $G$. A set $R\subseteq V(G)$ is
an $X$-irrelevant set if every vertex of $R$ is $X$-irrelevant.

Irrelevant vertices exist for zero forcing as seen in the next example, but
not for domination as discussed in Section 2.2.

######  Example 2.5.

Observe that the center vertex of $K_{1,r}$ is a $\operatorname{Z}$-irrelevant
vertex and is in fact the only $\operatorname{Z}$-irrelevant vertex.

######  Definition 2.6.

Let $G$ be a graph and $R\subseteq V(G)$. We define the map

$\nu_{R}:V(\mathscr{X}^{{\tiny\rm
TAR}}(G))\to\mathcal{P}(V(G))\quad\text{via}\quad\nu_{R}(S)=S\ominus R.$

For a nonempty set $R$, the map $\nu_{R}$ maps $X$-sets to $X$-sets, and is
thus an automorphism of $\mathscr{X}^{{\tiny\rm TAR}}(G)$. This is illustrated
in the next example and shown in Theorem 2.8. Observe that $\nu_{R}$ maps $S$
to $S^{\prime}$ with $|S^{\prime}|\neq|S|$.

######  Example 2.7.

Consider $K_{1,r}$ with center vertex $0$. Recall that $\mathscr{Z}^{{\tiny\rm
TAR}}(K_{1,r})=K_{1,r}\square K_{2}$ (see Figure 1.1 for
$\mathscr{Z}^{{\tiny\rm TAR}}(K_{1,3})$). For $R=\\{0\\}$, $\nu_{R}$ is the
automorphism of $K_{1,r}\square K_{2}$ obtained by reversing the two vertices
of $K_{2}$.

######  Theorem 2.8.

Let $X$ be an $X$-set parameter, let $G$ be a graph, and let $R\subseteq
V(G)$. Then $\nu_{R}$ is a graph automorphism of $\mathscr{X}^{{\tiny\rm
TAR}}(G)$ if and only if $R$ is $X$-irrelevant.

###### Proof.

Suppose that $\nu_{R}$ is an automorphism. By Lemma 2.3 every minimal $X$-set
of $G$ is a subset of $\nu_{R}(V(G))=V(G)\setminus R$. Thus, $R$ is
$X$-irrelevant.

Suppose that $R$ is $X$-irrelevant. Let $S$ be an $X$-set of $G$. Then there
exists some minimal $X$-set $T\subseteq S$. Since $R$ is $X$-irrelevant,
$T\subseteq S\setminus R\subseteq S$. Thus, $\nu_{R}(S)\supseteq S\setminus R$
is an $X$-set of $G$. By construction, adjacency is preserved by $\nu_{R}$.
Therefore, $\nu_{R}$ is an automorphism. ∎

We restate Theorem 2.8 for the specific case of zero forcing.

######  Corollary 2.9.

Let $G$ be a graph and let $R\subseteq V(G)$. Then $\nu_{R}$ is a graph
automorphism of $\mathscr{Z}^{{\tiny\rm TAR}}(G)$ if and only if $R$ is
$\operatorname{Z}$-irrelevant.

We are now ready to state one of our main results, namely that if there is an
isomorphism between $X$-TAR graphs that does not preserve the sizes of the
$X$-sets, then the difference in size is due to an $X$-irrelevant set.
Moreover, there is an isomorphism between these $X$-TAR graphs that preserves
the size of the $X$-sets.

######  Theorem 2.10.

Let $X$ be an $X$-set parameter, let $G$ and $G^{\prime}$ be graphs with no
isolated vertices, and let $\tilde{\varphi}:\mathscr{X}^{{\tiny\rm
TAR}}(G)\to\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$ be an isomorphism. Then
$R^{\prime}=V(G^{\prime})\setminus\tilde{\varphi}(V(G))$ is $X$-irrelevant and
$\varphi=\nu_{R^{\prime}}\circ\tilde{\varphi}$ is an isomorphism such that
$|\varphi(S)|=|S|$ for every $S\in V(\mathscr{X}^{{\tiny\rm TAR}}(G))$.

###### Proof.

Let $n=|V(G)|$. If $\tilde{\varphi}(V(G))=V(G^{\prime})$, then
$R^{\prime}=\emptyset$ is $X$-irrelevant. So suppose that
$\tilde{\varphi}(V(G))=S^{\prime}$, where $S^{\prime}\not=V(G^{\prime})$.
Since $\tilde{\varphi}$ is an isomorphism, Lemma 2.3 implies every minimal
$X$-set of $G^{\prime}$ is a subset of $S^{\prime}$ and hence $R^{\prime}$ is
$X$-irrelevant. By Theorem 2.8, $\nu_{R^{\prime}}$ is an automorphism of
$\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$. Thus,
$\varphi=\nu_{R^{\prime}}\circ\tilde{\varphi}$ is an isomorphism such that
$\varphi(V(G))=V(G^{\prime})$.

Note that $|V(G^{\prime})|=n$ and $X(G^{\prime})=X(G)$. Let $S\in
V(\mathscr{X}^{{\tiny\rm TAR}}(G))$. The interval
$H=[S,V(G)]\in\mathscr{X}^{{\tiny\rm TAR}}(G)$ is an induced hypercube in
$\mathscr{X}^{{\tiny\rm TAR}}(G)$, so $\varphi(H)$ is an induced hypercube in
$\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$. By Lemma 2.1 and since
$\varphi(V(G))=V(G^{\prime})$, $\varphi(H)=[S^{\prime},V(G^{\prime})]$ in
$\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$ and
$\operatorname{dist}(S^{\prime},V(G^{\prime}))=\operatorname{dist}(S,V(G))$.
We show by induction on $|S|$ that $|\varphi(S)|=|S|$. We say $S$ is a
$k$-$X$-set if $S$ is an $X$-set and $|S|=k$.

For the base case, assume $|S|=X(G)$, so
$\operatorname{dist}(S^{\prime},T^{\prime})=\operatorname{dist}(S,T)=n-X(G)=|V(G^{\prime})|-X(G^{\prime})$.
This implies $|S^{\prime}|=X(G^{\prime})=X(G)=|S|$. The same reasoning applies
using $\varphi^{-1}$, since $\varphi^{-1}(V(G^{\prime}))=V(G)$. Thus $\varphi$
defines a bijection between minimum $X$-sets of $G$ and minimum $X$-sets of
$G^{\prime}$.

Now assume $\varphi$ defines a bijection between $i$-$X$-sets of $G$ and
$i$-$X$-sets of $G^{\prime}$ for $X(G)\leq i\leq k$ and let $S$ be a
$(k+1)$-$X$-set of $G$. This implies $|\varphi(W)|\geq k+1$ for
$W\in[S,V(G)]$. By Lemma 2.1, $\varphi([S,V(G)])=[S^{\prime},V(G^{\prime})]$
in $\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$ and
$\operatorname{dist}(S^{\prime},V(G^{\prime}))=n-k-1$. Thus $S^{\prime}$ is a
$(k+1)$-$X$-set of $G$. ∎

We restate Theorem 2.10 for the specific case of zero forcing.

######  Corollary 2.11.

Let $G$ and $G^{\prime}$ be graphs with no isolated vertices and let
$\tilde{\varphi}:\mathscr{Z}^{{\tiny\rm TAR}}(G)\to\mathscr{Z}^{{\tiny\rm
TAR}}(G^{\prime})$ be an isomorphism. Then
$R^{\prime}=V(G^{\prime})\setminus\tilde{\varphi}(V(G))$ is
$\operatorname{Z}$-irrelevant and
$\varphi=\nu_{R^{\prime}}\circ\tilde{\varphi}$ is an isomorphism such that
$|\varphi(S)|=|S|$ for every $S\in V(\mathscr{Z}^{{\tiny\rm TAR}}(G))$.

In the next theorem, we show that if two graphs $G$ and $G^{\prime}$ (with no
isolated vertices) have isomorphic $X$-TAR graphs, then there is a bijection
between the vertices of $G$ and the vertices of $G^{\prime}$ that results in
the correspondence of the $X$-sets. Note this bijection need not be a graph
isomorphism between $G$ and $G^{\prime}$. A cycle and a cycle plus one edge
provide an example of nonisomorphic graphs with the same zero forcing sets
(see Proposition 2.30). We first give some useful notation. For any map
$\psi:A\to A^{\prime}$ and subset $B\subseteq A$ we write $\psi(B)$ to mean
the image of $B$, i.e., $\psi(B)=\\{\psi(b):b\in B\\}$. This is particularly
useful when working with a map $\psi:V(G)\to V(G^{\prime})$ that maps $X$-sets
of $G$ to $X$-sets of $G^{\prime}$, since this convention naturally induces a
map $\psi:V(\mathscr{X}^{{\tiny\rm TAR}}(G))\to V(\mathscr{X}^{{\tiny\rm
TAR}}(G^{\prime}))$. For any graph $G$ and $v\in V(G)$, define
$S_{v}=V(G)\setminus\\{v\\}$.

######  Theorem 2.12.

Let $X$ be an $X$-set parameter, let $G$ and $G^{\prime}$ be graphs with no
isolated vertices, and suppose $\varphi:\mathscr{X}^{{\tiny\rm
TAR}}(G)\to\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$ is a graph isomorphism.
Then $|\varphi(S)|=|S|$ for every $X$-set $S$ if and only if there exists a
bijection $\psi:V(G)\to V(G^{\prime})$ such that $\psi(S)=\varphi(S)$ for
every $X$-set $S$ of $G$.

###### Proof.

Let $n=|V(G)|$. For $v\in V(G)$ and $v^{\prime}\in V(G^{\prime})$, note that
$S_{v}$ is an $X$-set of $G$ and $S_{v^{\prime}}$ is an $X$-set of
$G^{\prime}$.

Begin by assuming $|\varphi(S)|=|S|$ for every $X$-set $S$. Since
$|\varphi(S_{v})|=n-1$ for every $v\in V(G)$, we may define
$\psi(v)=v^{\prime}$ where $v^{\prime}$ is the unique vertex such that
$\varphi(S_{v})=S_{v^{\prime}}$. Note that $\psi:V(G)\to V(G^{\prime})$ is a
bijection.

The proof that $\psi(S)=\varphi(S)$ for every $X$-set $S$ of $G$ proceeds
iteratively from $|S|=n$ to $|S|=1$. By the choice of $\varphi$ and the
definition of $\psi$, we have $\varphi(S)=\psi(S)$ for $|S|=n,n-1$. Assume
$\varphi(S)=\psi(S)$ for each $X$-set $S$ of order $k$ for some $k$ with
$n-1\geq k>X(G)$. Let $S$ be an $X$-set of order $k-1$. Since $k-1\leq n-2$,
there exist distinct vertices $a,b\in V(G)\setminus S$ such that
$S\cup\\{a\\}$ and $S\cup\\{b\\}$ are $X$-sets of order $k$. Since $S$ is
adjacent to $S\cup\\{a\\}$ and $S\cup\\{b\\}$ in $\mathscr{X}^{{\tiny\rm
TAR}}(G)$, and $|\varphi(S\cup\\{a\\})|=|\varphi(S\cup\\{b\\})|>|\varphi(S)|$,
there exist distinct $a^{\prime},b^{\prime}\in
V(G^{\prime})\setminus\varphi(S)$ such that
$\varphi(S\cup\\{a\\})=\varphi(S)\cup\\{a^{\prime}\\}$ and
$\varphi(S\cup\\{b\\})=\varphi(S)\cup\\{b^{\prime}\\}$. Thus,

$\varphi(S)=\varphi(S\cup\\{a\\})\cap\varphi(S\cup\\{b\\})=\psi(S\cup\\{a\\})\cap\psi(S\cup\\{b\\})=\psi(S),$

where the last equality follows since $\psi$ is a bijection.

Now assume there exists a bijection $\psi:V(G)\to V(G^{\prime})$ such that
$\psi(S)=\varphi(S)$ for every $X$-set $S$ of $G$. Then
$|S|=|\psi(S)|=|\varphi(S)|$ as desired. ∎

We restate Theorem 2.12 for the specific case of zero forcing.

######  Corollary 2.13.

Let $G$ and $G^{\prime}$ be graphs with no isolated vertices, and suppose
$\varphi:\mathscr{Z}^{{\tiny\rm TAR}}(G)\to\mathscr{Z}^{{\tiny\rm
TAR}}(G^{\prime})$ is a graph isomorphism. Then $|\varphi(S)|=|S|$ for every
zero forcing set $S$ if and only if there exists a bijection $\psi:V(G)\to
V(G^{\prime})$ such that $\psi(S)=\varphi(S)$ for every zero forcing set $S$
of $G$.

Theorem 2.12 also shows that if the domination (respectively, power
domination, PSD zero forcing) TAR reconfiguration graphs of $G$ and
$G^{\prime}$ are isomorphic, then $G^{\prime}$ can be relabeled so that $G$
and $G^{\prime}$ have exactly the same dominating (respectively, power
dominating, positive semidefinite zero forcing) sets.

The next two results focus on mappings and minimal $X$-sets.

######  Proposition 2.14.

Let $X$ be an $X$-set parameter and let $G$ and $G^{\prime}$ be graphs with no
isolated vertices. Suppose $\varphi:\mathscr{X}^{{\tiny\rm
TAR}}(G)\to\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$ is a graph isomorphism
such that $|\varphi(S)|=|S|$. Then $\varphi$ maps minimal $X$-sets to minimal
$X$-sets (of the same size).

###### Proof.

If $S$ is minimal $X$-set of $G$, then $\deg_{\mathscr{X}^{{\tiny\rm
TAR}}(G)}(S)=n-|S|$. If $T$ is an $X$-set of $G$ that is not minimal in
$\mathscr{X}^{{\tiny\rm TAR}}(G)$, then $\deg_{\mathscr{X}^{{\tiny\rm
TAR}}(G)}(T)\geq n-|T|+1$ (since $T$ has a subset neighbor). Analogous
statements are true for $G^{\prime}$. ∎

######  Theorem 2.15.

Let $X$ be an $X$-set parameter and let $G$ and $G^{\prime}$ be graphs with no
isolated vertices. Suppose $\psi:V(G)\to V(G^{\prime})$ is a bijection.

  1. $(1)$

Suppose $\psi$ maps $X$-sets of $G$ to $X$-sets of $G^{\prime}$. Then the
induced mapping $\psi:V(\mathscr{X}^{{\tiny\rm TAR}}(G))\to
V(\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime}))$ is an isomorphism of
$\mathscr{X}^{{\tiny\rm TAR}}(G)$ and $\psi(\mathscr{X}^{{\tiny\rm TAR}}(G))$.
If every $X$-set of $G^{\prime}$ is the image of an $X$-set of $G$, then
$\psi:V(\mathscr{X}^{{\tiny\rm TAR}}(G))\to V(\mathscr{X}^{{\tiny\rm
TAR}}(G^{\prime}))$ is an isomorphism of $\mathscr{X}^{{\tiny\rm TAR}}(G)$ and
$\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$.

  2. $(2)$

Suppose $\psi$ maps minimal $X$-sets of $G$ to minimal $X$-sets of
$G^{\prime}$. Then $\psi$ maps $X$-sets of $G$ to $X$-sets of $G^{\prime}$. If
every minimal $X$-set of $G^{\prime}$ is the image of a minimal $X$-set of
$G$, then $\psi$ is a bijection from $X$-sets of $G$ to $X$-sets of
$G^{\prime}$.

  3. $(3)$

Suppose $\psi$ maps minimal $X$-sets of $G$ to minimal $X$-sets of
$G^{\prime}$. Then the induced mapping $\psi:V(\mathscr{X}^{{\tiny\rm
TAR}}(G))\to V(\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime}))$ is an isomorphism of
$\mathscr{X}^{{\tiny\rm TAR}}(G)$ and $\psi(\mathscr{X}^{{\tiny\rm TAR}}(G))$.
If every minimal $X$-set of $G^{\prime}$ is the image of a minimal $X$-set of
$G$, then $\psi:V(\mathscr{X}^{{\tiny\rm TAR}}(G))\to V(\mathscr{X}^{{\tiny\rm
TAR}}(G^{\prime}))$ is an isomorphism of $\mathscr{X}^{{\tiny\rm TAR}}(G)$ and
$\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$.

###### Proof.

(1): Since $\psi$ maps $X$-sets of $G$ to $X$-sets of $G^{\prime}$, $\psi$
induces a bijection between the vertices of $\mathscr{X}^{{\tiny\rm TAR}}(G)$
and a subset of the vertices of $\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$
($X$-sets of $G^{\prime}$ of the form $\psi(S)$ where $S$ is an $X$-set of
$G$). Assume that $S_{1},S_{2}\in V(\mathscr{X}^{{\tiny\rm TAR}}(G))$ are
adjacent in $\mathscr{X}^{{\tiny\rm TAR}}(G)$. Without loss of generality,
$|S_{1}\setminus S_{2}|=1$. Since $\psi$ is a bijection,
$|\psi(S_{1})\setminus\psi(S_{2})|=1$. Thus, $\psi(S_{1})$ and $\psi(S_{2})$
are adjacent in $\mathscr{X}^{{\tiny\rm TAR}}(G^{\prime})$. Hence $\psi$ is an
isomorphism from $\mathscr{X}^{{\tiny\rm TAR}}(G)$ to
$\psi(\mathscr{X}^{{\tiny\rm TAR}}(G))$.

(2): Let $S\in V(\mathscr{X}^{{\tiny\rm TAR}}(G))$ be an $X$-set. There is a
minimal $X$-set $T\subseteq S$ of $G$ and $\psi(T)\subseteq\psi(S)$. Since
$\psi(T)$ is a minimal $X$-set of $G^{\prime}$, $\psi(S)$ is an $X$-set of
$G^{\prime}$.

Statement (3) is immediate from statements (2) and (1) ∎

It is possible to have a vertex bijection $\psi$ that maps minimal zero
forcing sets of $G$ to minimal zero forcing sets of $G^{\prime}$ but not vice
versa, as the next example shows (using the identity function as $\psi$).

######  Example 2.16.

Consider the graph $K_{1,3}$ with vertices $\\{0,1,2,3\\}$ where 0 is the
center vertex, and the paw graph $P$ constructed from $K_{1,3}$ by adding the
edge $23$. The minimal zero forcing sets of $K_{1,3}$ are $\\{1,2\\}$,
$\\{1,3\\}$, and $\\{2,3\\}$. The minimal zero forcing sets of $P$ are
$\\{0,2\\}$, $\\{0,3\\}$, $\\{1,2\\}$, $\\{1,3\\}$, and $\\{2,3\\}$.

$\small{\\{1,2,3\\}}$$\small{\\{1,2\\}}$$\small{\\{2,3\\}}$$\small{\\{1,3\\}}$$\small{\\{0,1,2\\}}$$\small{\\{0,2,3\\}}$$\small{\\{0,1,3\\}}$$\small{\\{0,1,2,3\\}}$

$\small{\\{1,2,3\\}}$$\small{\\{1,2\\}}$$\small{\\{2,3\\}}$$\small{\\{1,3\\}}$$\small{\\{0,2\\}}$$\small{\\{0,3\\}}$$\small{\\{0,1,2\\}}$$\small{\\{0,2,3\\}}$$\small{\\{0,1,3\\}}$$\small{\\{0,1,2,3\\}}$

Figure 2.1: $\mathscr{Z}^{{\tiny\rm TAR}}(K_{1,3})$ and
$\mathscr{Z}^{{\tiny\rm TAR}}(P)$

###  2.2 $X$-irrelevant vertices and automorphisms of $X$-TAR graphs.

In this section we explore the existence (or non-existence) of $X$-irrelevant
vertices for various $X$-set parameters and consequences for automorphisms of
$X$-TAR graphs. The following proposition is an application of Theorems 2.8
and 2.10.

######  Proposition 2.17.

Let $G$ be a graph with no isolated vertices. If there exists an automorphism
$\varphi\in\text{aut}(G)$ that does not fix $V(G)$, then
$\mathscr{X}^{{\tiny\rm TAR}}(G)$ has a perfect matching.

###### Proof.

Suppose that there exists an automorphism $\varphi\in\text{aut}(G)$ that does
not fix $V(G)$. By Theorem 2.10, $V(G)\setminus\varphi(V(G))$ is
$X$-irrelevant. Let $R$ be any single element subset of
$V(G)\setminus\varphi(V(G))$. Then $R$ is $X$-irrelevant and by Theorem 2.8
$\nu_{R}$ is an automorphism of $\mathscr{X}^{{\tiny\rm TAR}}(G)$. Observe
that no vertex is fixed by $\nu_{R}$ and $\nu_{R}^{2}$ is the identity map.
Thus, $\nu_{R}$ induces a perfect matching on $\mathscr{X}^{{\tiny\rm
TAR}}(G)$. ∎

Let $M_{X}(G)$ denote the set of bijections $\psi:V(G)\to V(G)$ that send
minimal $X$-sets of $G$ to minimal $X$-sets of $G$ of the same size.

######  Theorem 2.18.

Let $G$ be a graph with no isolated vertices. Then the automorphism group of
$\mathscr{X}^{{\tiny\rm TAR}}(G)$ is generated by

$\\{\nu_{R}:R\text{ is $X$-irrelevant}\\}\cup M_{X}(G).$

###### Proof.

By Theorem 2.8 $\nu_{R}\in\text{aut}(\mathscr{X}^{{\tiny\rm TAR}}(G))$ for
every $X$-irrelevant set $R$. By Theorem 2.15(3),
$\psi\in\text{aut}(\mathscr{X}^{{\tiny\rm TAR}}(G))$ for every $\psi\in
M_{X}(G)$ (since $G^{\prime}=G$ here, having $\psi$ map minimal $X$-sets to
minimal $X$-sets is sufficient).

We now show that $\\{\nu_{R}:R\text{ is $X$-irrelevant}\\}\cup M_{X}(G)$
generates aut$(\mathscr{X}^{{\tiny\rm TAR}}(G))$. Let $\varphi$ by an
automorphism of $\mathscr{X}^{{\tiny\rm TAR}}(G)$. Suppose that $V(G)$ is
fixed by $\mathscr{X}^{{\tiny\rm TAR}}(G)$. Then $|\varphi(S)|=|S|$ for each
$S\in V(\mathscr{X}^{{\tiny\rm TAR}}(G))$. By Theorem 2.12 there exists a
bijection $\psi:V(G)\to V(G)$ such that $\psi(S)=\varphi(S)$ for every $X$-set
$S$ of $G$. By Proposition 2.15, $\psi$ maps minimal $X$-sets to minimal
$X$-sets of the same size.

Suppose that $V(G)$ is not fixed by $\varphi$. By Theorem 2.10 and the
preceding argument, there exists a bijection $\psi\in M_{X}(G)$ such that
$\psi=\nu_{R}\circ\varphi$, where $R=V(G)\setminus\varphi(G)$. Thus,
$\varphi=\nu_{R}^{-1}\circ\psi$. ∎

######  Example 2.19.

Consider $P_{4}$ with vertices $1,2,3,4$ and edges $12,23,34$. Define
$\psi:V(G)\to V(G)$ by $\psi(1)=4$, $\psi(2)=2$, $\psi(3)=3$ and $\psi(1)=4$.
The minimal zero forcing sets are $\\{1\\}$, $\\{4\\}$, and $\\{2,3\\}$, so
$\psi$ maps minimal forcing sets to minimal forcing sets. Thus $\psi$ defines
an automorphism of $\mathscr{Z}^{{\tiny\rm TAR}}(P_{4})$. However, $\psi$ is
_not_ an automorphism of $P_{4}$.

The next result provides many examples of graphs with nonempty
$\operatorname{Z}$-irrelevant sets (and includes $K_{1,r}$ discussed in
Example 2.5). Let $H$ and $G$ be graphs, and for each $v\in V(H)$, let $G_{v}$
denote a copy of $G$ such that $H$ and $G_{v},v\in V(H)$ are all disjoint
graphs. The _corona_ of $H$ with $G$, denoted by $H\circ G$, has $V(H\circ
G)=V(H)\cup\bigcup_{v\in V(H)}V(G_{v})$ and $E(H\circ G)=E(H)\cup\bigcup_{v\in
V(H)}E(G_{v})\cup\bigcup_{v\in V(H)}\\{vx:x\in V(G_{v})\\}$. The graph
$K_{3}\circ 2K_{1}$ is shown in Figure 2.2.

######  Proposition 2.20.

Let $H$ be a connected graph and $G=H\circ rK_{1}$ with $r\geq 2$. Then
$T\subseteq V(G)$ is a $\operatorname{Z}$-irrelevant set of $G$ if and only if
$T\subseteq V(H)$.

###### Proof.

Let $V(H)=\\{v_{1},\dots,v_{k}\\}$ and denote the leaves adjacent to $v_{i}$
by $x_{i,j}$ for $j=1,\dots,r$. Then $S\subseteq V(G)$ is a zero forcing set
of $G$ if and only if $S$ contains at least $r-1$ of the vertices
$x_{i,1},\dots,x_{i,r}$ for all $i=1,\dots,k$. Thus $T\subseteq V(G)$ is
$\operatorname{Z}$-irrelevant set if and only if $T\subseteq V(H)$. ∎

Figure 2.2: The graphs $K_{3}\circ 2K_{1}$ and $G(5,2)$

Next we apply the results in Section 2.1 to other $X$-set parameters. The
power domination TAR reconfiguration graph of a graph $G$ was introduced in
[4]. We define a family of graphs with nonempty $\gamma_{P}$-irrelevant sets.
For $r\geq 3$ and $1\leq\ell\leq r-2$, construct $G(r,\ell)$ from $K_{r}\circ
K_{1}$ by deleting $r-\ell$ leaves.

######  Proposition 2.21.

For $r\geq 3$ and $1\leq\ell\leq r-2$, let $L$ denote the set of leaves of
$G(r,\ell)$. Then $T\subseteq V(G(r,\ell))$ is a $\gamma_{P}$-irrelevant set
of $G(r,\ell)$ if and only if $T\subseteq L$.

###### Proof.

The set $L$ is not a power dominating set of $G(r,\ell)$ because no vertex
dominated by $L$ is adjacent to exactly one vertex of $G(r,\ell)$ that is not
dominated by $L$, and $L$ does not dominate $G$. But any one vertex of $K_{r}$
is a power dominating set. ∎

The domination TAR reconfiguration graph of a graph $G$, denoted by
$\mathscr{D}^{{\tiny\rm TAR}}(G)$, was studied in [1] after
$\mathscr{D}^{{\tiny\rm TAR}}_{k}(G)$ was introduced in [12]. The next remark
is known.

######  Remark 2.22.

Let $G$ be a graph and $v\in V(G)$. A minimal dominating set containing $v$
can be constructed by starting with $S=\\{v\\}$ and repeatedly adding
$w\not\in N[S]$ until $N[S]=V(G)$.

Remark 2.22 immediately implies the next result.

######  Proposition 2.23.

If $G$ is a graph and $S\subseteq V(G)$ is $\gamma$-irrelevant, then
$S=\emptyset$.

The next result is immediate from Proposition 2.23 and Theorems 2.10 and 2.12.

######  Corollary 2.24.

Let $G$ and $G^{\prime}$ be graphs with no isolated vertices, and suppose
$\varphi:\mathscr{D}^{{\tiny\rm TAR}}(G)\to\mathscr{D}^{{\tiny\rm
TAR}}(G^{\prime})$ is a graph isomorphism. For every dominating set $S$ of
$G$, $|\varphi(S)|=|S|$. Furthermore, there exists a bijection $\psi:V(G)\to
V(G^{\prime})$ such that $\psi(S)=\varphi(S)$ for every dominating set $S$ of
$G$.

Let $\mathscr{Z}_{+}^{{\tiny\rm TAR}}(G)$ denote the positive semidefinite
zero forcing TAR reconfiguration graph of $G$, which has positive semidefinite
zero forcing sets as vertices. No work on this reconfiguration graph has
appeared, but the positive semidefinite zero forcing number is an $X$-set
parameter. Known results about positive semidefinite zero forcing and Theorems
2.10 and 2.12 provide information about isomorphisms of
$\mathscr{Z}_{+}^{{\tiny\rm TAR}}(G)$.

######  Proposition 2.25.

[9] Let $G$ be a graph. Then for any vertex $v\in V(G)$, there exists a
minimum positive semidefinite zero forcing set $S$ such that $v\in S$.

######  Corollary 2.26.

Let $G$ and $G^{\prime}$ be graphs with no isolated vertices, and suppose
$\varphi:\mathscr{Z}_{+}^{{\tiny\rm TAR}}(G)\to\mathscr{Z}_{+}^{{\tiny\rm
TAR}}(G^{\prime})$ is a graph isomorphism. For every positive semidefinite
zero forcing set $S$ of $G$, $|\varphi(S)|=|S|$. Furthermore, there exists a
bijection $\psi:V(G)\to V(G^{\prime})$ such that $\psi(S)=\varphi(S)$ for
every positive semidefinite zero forcing set $S$ of $G$.

###  2.3 Zero forcing TAR graphs and zero forcing polynomials

Let $G$ be a graph of order $n$ and let $z(G;k)$ denote the number of zero
forcing sets of cardinality $k$. Boyer et al. defined the _zero forcing
polynomial_ of $G$ to be $Z(G;x)=\sum_{k=\operatorname{Z}(G)}^{n}z(G;k)x^{k}$
in [5]. The next result is immediate from Corollary 2.11 (or Corollary 2.13).

######  Corollary 2.27.

Let $G$ and $G^{\prime}$ be graphs with no isolated vertices such that
$\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm
TAR}}(G^{\prime})$. Then the zero forcing polynomials of $G$ and $G^{\prime}$
are equal.

The converse to Corollary 2.27 is false. Small examples of graphs with the
same zero forcing polynomial and nonisomorphic zero forcing TAR graphs are
easy to find with software, and one such example is presented next.

526413$G$234516$H$ Figure 2.3: Two graphs the the same zero forcing polynomial
and nonisomorphic zero forcing TAR graphs

######  Example 2.28.

The graphs $G$ and $H$ in Figure 2.3 have

$Z(G;x)=Z(H;x)=x^{6}+6x^{5}+13x^{4}+8x^{3}$

(see [7] for the computations). The minimal zero forcing sets of $G$ are {1,
2, 4}, {1, 2, 6}, {1, 4, 5}, {1, 5, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5, 6}, {4,
5, 6} and the minimal zero forcing sets of $H$ are {1, 2, 4}, {1, 2, 5}, {1,
3, 4}, {1, 3, 5}, {2, 4, 6}, {2, 5, 6}, {3, 4, 6}, {3, 5, 6}, {2, 3, 4, 5}.
Thus $\overline{\operatorname{Z}}(G)=3$, $\overline{\operatorname{Z}}(H)=4$,
and $\mathscr{Z}^{{\tiny\rm TAR}}(G)\not\cong\mathscr{Z}^{{\tiny\rm TAR}}(H)$.

######  Corollary 2.29.

Let $G$ and $G^{\prime}$ be graphs with no isolated vertices. Suppose that
$\psi:V(G)\to V(G^{\prime})$ is a bijection that maps minimal zero forcing
sets of $G$ to minimal zero forcing sets of $G^{\prime}$. Then the
coefficients of $Z(G,x)$ are bounded above by the coefficients of
$Z(G^{\prime},x)$.

###### Proof.

By Theorem 2.15(2), $\psi$ maps zero forcing sets of $G$ to zero forcing sets
of $G^{\prime}$. Since $\psi$ is a bijection, $S$ and $\psi(S)$ have the same
cardinality. Thus $G^{\prime}$ must have at least as many zero forcing sets of
cardinality $k$ as $G$ does. ∎

###  2.4 Uniqueness and nonuniqueness

In this section we present examples of nonisomorphic graphs $G$ and $H$ with
no isolated vertices such that $\mathscr{Z}^{{\tiny\rm
TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm TAR}}(H)$. Recall that by Theorem 2.12,
this implies the vertices of $G$ can be labelled so that $G$ and $H$ have the
same zero forcing sets. We also present examples of graphs $H$ (with no
isolated vertices) for which the zero forcing TAR reconfiguration is unique,
meaning that for any graph $G$ with no isolated vertices,
$\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm TAR}}(H)$ implies
$G\cong H$. For a graph $G$ and vertices $u$ and $v$ that are not adjacent in
$G$, the graph $G+uv$ is the graph with vertex set $V(G)$ and edge set
$E(G)\cup\\{uv\\}$.

######  Proposition 2.30.

Let $n\geq 4$. Then $\mathscr{Z}^{{\tiny\rm
TAR}}(C_{n})=\mathscr{Z}^{{\tiny\rm TAR}}(C_{n}+uv)$ for any two vertices $u$
and $v$ of $C_{n}$ that are not adjacent in $C_{n}$.

###### Proof.

For both $C_{n}$ and $C_{n}+uv$, a set of vertices $S$ is a zero forcing set
if and only if $S$ contains two vertices that are consecutive on the cycle.
Since $C_{n}$ and $C_{n}+uv$ have exactly the same zero forcing sets,
$\mathscr{Z}^{{\tiny\rm TAR}}(C_{n})=\mathscr{Z}^{{\tiny\rm TAR}}(C_{n}+uv)$.
∎

Next we present examples of unique zero forcing TAR graphs. The first two are
immediate since they are the unique graphs having the given zero forcing
number. However, the third is less obvious.

######  Proposition 2.31.

Let $G$ be a graph on $n\geq 2$ vertices with no isolated vertices. If
$\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm TAR}}(P_{n})$,
then $G\cong P_{n}$.

###### Proof.

By Corollary 1.9, $\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm
TAR}}(P_{n})$ implies $\operatorname{Z}(G)=\operatorname{Z}(P_{n})=1$, which
implies $G$ is a path. ∎

######  Proposition 2.32.

Let $G$ be a connected graph on $n\geq 2$ vertices with no isolated vertices.
Then $\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong K_{1,n}$ implies $G\cong K_{n}$.

###### Proof.

By Corollary 1.9, $\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong
K_{1,n}\cong\mathscr{Z}^{{\tiny\rm TAR}}(K_{n})$ implies
$\operatorname{Z}(G)=\operatorname{Z}(K_{n})=n-1$, which implies $G$ is a
complete graph. ∎

In order to discuss uniqueness of the next family of graphs, we need to know
what happens in the case of disconnected graphs.

######  Proposition 2.33.

Let $X$ be an $X$-set parameter and let $G=G_{1}\sqcup G_{2}$. Then
$\mathscr{X}^{{\tiny\rm TAR}}(G)=\mathscr{X}^{{\tiny\rm
TAR}}(G_{1})\square\mathscr{X}^{{\tiny\rm TAR}}(G_{2})$.

###### Proof.

Let $S$ and $T$ be $X$-sets of $G$. Then $S=S_{1}\sqcup S_{2}$ and
$T=T_{1}\sqcup T_{2}$, where $S_{1}$ and $T_{1}$ are zero forcing sets of
$G_{1}$, and $S_{2}$ and $T_{2}$ are zero forcing sets of $G_{2}$. Observe
that $S$ and $T$ are adjacent in $\mathscr{Z}^{{\tiny\rm TAR}}(G)$ if and only
if there exists a vertex $v\in V(G_{1})\sqcup V(G_{2})$ such that

  * •

$S_{1}=T_{1}$ and ($T_{2}=S_{2}\setminus\\{v\\}$ or
$S_{2}=T_{2}\setminus\\{v\\}$), or

  * •

$S_{2}=T_{2}$ and ($T_{1}=S_{1}\setminus\\{v\\}$ or
$S_{1}=T_{1}\setminus\\{v\\}$).

Further, $T_{2}=S_{2}\setminus\\{v\\}$ or $S_{2}=T_{2}\setminus\\{v\\}$ if and
only if $S_{2}$ is adjacent to $T_{2}$ in $\mathscr{X}^{{\tiny\rm
TAR}}(G_{2})$, and $T_{1}=S_{1}\setminus\\{v\\}$ or
$S_{1}=T_{1}\setminus\\{v\\}$ if and only $S_{1}$ is adjacent to $T_{1}$ in
$\mathscr{X}^{{\tiny\rm TAR}}(G_{1})$. ∎

We restate Proposition 2.33 for the specific case of zero forcing.

######  Corollary 2.34.

Let $G=G_{1}\sqcup G_{2}$. Then $\mathscr{Z}^{{\tiny\rm
TAR}}(G)=\mathscr{Z}^{{\tiny\rm TAR}}(G_{1})\square\mathscr{Z}^{{\tiny\rm
TAR}}(G_{2})$.

The proof of the next result uses some additional definitions and known
properties of zero forcing. Let $G$ be a graph. For a given zero forcing set
$S$, carry out a forcing process to color all vertices blue, recording the
forces; the set of these forces is denoted by ${\mathcal{F}}$. A set of forces
${\mathcal{F}}$ of $S$ defines a _reversal_ of $S$, namely the set of vertices
that do not perform a force (using the set of forces ${\mathcal{F}}$). The
next process is sometimes called _neighbor trading_ [11]. Let $S$ be a minimum
zero forcing set of $G$ and $v\in S$ with $\deg_{G}(v)\geq 2$. Suppose $v\to
w$ can be the first force performed in a forcing process. Let $u\in N_{G}(v)$
and $u\neq w$. Then $u\in S$ and $S\setminus\\{u\\}\cup\\{w\\}$ is a minimum
zero forcing set with first force $v\to w$ by $v\to u$ and the other forces
remaining the same.

######  Proposition 2.35.

Let $G$ be a graph on $n\geq 3$ vertices with no isolated vertices. If
$\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong K_{1,r}\square K_{2}$, then $G\cong
K_{1,r}$.

###### Proof.

Suppose $\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong K_{1,r}\square K_{2}$. Recall
that $\mathscr{Z}^{{\tiny\rm TAR}}(H_{1}\sqcup
H_{2})\cong\mathscr{Z}^{{\tiny\rm TAR}}(H_{1})\square\mathscr{Z}^{{\tiny\rm
TAR}}(H_{2})$. Since there does not exist a graph $H_{2}$ with
$\mathscr{Z}^{{\tiny\rm TAR}}(H_{2})=K_{2}$, we may assume $G$ is connected.

Since $\mathscr{Z}^{{\tiny\rm TAR}}(G)\cong\mathscr{Z}^{{\tiny\rm
TAR}}(K_{1,r})$, the order of $G$ is $r+1$ and we label the vertices of $G$ so
that the zero forcing sets of $G$ are exactly the zero forcing sets of
$K_{1,r}$ where the vertices of both graphs are $\\{0,\dots,r\\}$ and $0$ is
the center vertex of $K_{1,r}$. Note that every minimal zero forcing set of
$K_{1,r}$, and thus of $G$, is a minimum zero forcing set. Recall from Example
2.5 that the center vertex $0$ is $\operatorname{Z}$-irrelevant, i.e., not in
any minimum zero forcing set.

Let $B$ be a minimum zero forcing set of $G$. Since
$\operatorname{Z}(G)=|V(G)|-2$, exactly two forces are performed to color all
vertices blue starting with the vertices in $B$ blue. Since a vertex that does
not force is in the zero forcing set of the reversal of the set of forces, $0$
must perform a force and the set of forces must be $\\{i\to 0,0\to j\\}$. If
$\deg_{G}i\geq 2$, then by neighbor trading $0$ would be in a minimum zero
forcing set. Thus $\deg_{G}i=1$. By considering the reversal, $\deg_{G}j=1$.
If $n=3$, then $G\cong K_{1,2}$, so assume $n\geq 4$ (i.e., $r\geq 3$). Then
there is another vertex $k$, which must be adjacent to $0$ and not adjacent to
$i$ or $j$. If $r=3$, then $G\cong K_{1,r}$. If $r\geq 4$ then there exists
another vertex $\ell$. Since $\ell\not\in N_{G}(i)$ and $\ell\not\in
N_{G}(j)$, $\ell\in N_{G}(0)$ or $\ell\in N_{G}(k)$. Let $\ltimes$ denote the
graph obtained from $K_{3}$ by adding adding two leaves to one vertex. If
$\ell\in N_{G}(0)\cap N_{G}(k)$, then $G[\\{0,i,j,k,\ell\\}]\cong\ltimes$,
which is a forbidden induced subgraph for $\operatorname{Z}(G)=|V(G)|-2$. If
$\ell\in N_{G}(k)$ and $\ell\not\in N_{G}(0)$, then $G[\\{0,i,k,\ell\\}]\cong
P_{4}$, which is a forbidden induced subgraph for
$\operatorname{Z}(G)=|V(G)|-2$. Thus $G[\\{0,i,j,k,\ell\\}]\cong K_{1,4}$. The
argument for $\ell$ shows any additional vertices must also be leaves and
$G\cong K_{1,r}$. ∎

The next table shows the number of (nonismorphic) graphs without isolated
vertices of order at most eight that have unique Z-TAR reconfiguration graphs.

vertices | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---
# graphs with no isolated vertices | 1 | 2 | 7 | 23 | 122 | 888 | 11302
# graphs with unique $\mathscr{Z}^{{\tiny\rm TAR}}(G)$ | 1 | 2 | 4 | 7 | 34 | 303 | 5318
ratio (# unique/# no isolated) | 1 | 1 | 0.5714 | 0.3043 | 0.2787 | 0.3412 | 0.4705
Table 1: Number of graphs with unique zero forcing TAR graph for small orders

##  3 Connectedness properties of the zero forcing TAR graph

The focus of this section is connectedness properties of the zero forcing TAR
graph. We exhibit a family of graphs $H$ where $z_{0}(H)$ exceeds the lower
bound $\overline{\operatorname{Z}}(H)+1$ by an arbitrary amount and another
family of graphs $G$ where $\underline{z_{0}}(G)$ is strictly less than
$z_{0}(G)$. These examples are interesting because the more common situation
is $\underline{z_{0}}(G)=z_{0}(G)=\overline{\operatorname{Z}}(G)+1$. Since the
next result applies to several graph parameters, we state it in the universal
format (the result is known for domination [12]).

######  Proposition 3.1.

Let $X$ be an $X$-set parameter and let $G$ be a graph. If
$\mathscr{X}^{{\tiny\rm TAR}}_{k}(G)$ is connected for some
$k>\overline{X}(G)$, then $\mathscr{X}^{{\tiny\rm TAR}}_{k^{\prime}}(G)$ is
connected for $k^{\prime}=k,\dots,n$ and $x_{0}(G)\leq k$. If
$\mathscr{X}^{{\tiny\rm TAR}}_{\overline{X}(G)+1}(G)$ is connected, then
$x_{0}(G)=\overline{X}(G)+1$. If $\underline{x_{0}}(G)>\overline{X}(G)$, then
$\underline{x_{0}}(G)=x_{0}(G)$.

###### Proof.

Suppose $\mathscr{X}^{{\tiny\rm TAR}}_{k}(G)$ is connected for some
$k\geq\overline{X}(G)+1$. Consider two distinct $X$-sets
$S_{1}^{\prime},S_{2}^{\prime}\in V(\mathscr{X}^{{\tiny\rm
TAR}}_{k^{\prime}}(G))$ with $k^{\prime}\geq k$. Let $S_{1}$ and $S_{2}$ be
minimal $X$-sets of $G$ contained in $S_{1}^{\prime}$ and $S_{2}^{\prime}$,
respectively, and note that $S_{1},S_{2}\in V(\mathscr{X}^{{\tiny\rm
TAR}}_{k}(G))$. Since $\mathscr{X}^{{\tiny\rm TAR}}_{k}(G)$ is connected,
there exists a path in $\mathscr{X}^{{\tiny\rm TAR}}_{k}(G)$ from $S_{1}$ to
$S_{2}$. Furthermore, there is a path $P_{i}$ from $S_{i}$ to $S_{i}^{\prime}$
in $\mathscr{X}^{{\tiny\rm TAR}}_{k^{\prime}}(G)$ for $i=1,2$. Since
$\mathscr{X}^{{\tiny\rm TAR}}_{k}(G)$ is a subgraph of $\mathscr{X}^{{\tiny\rm
TAR}}_{k^{\prime}}(G)$, there exists a path from $S_{1}^{\prime}$ to
$S_{2}^{\prime}$ in $\mathscr{X}^{{\tiny\rm TAR}}_{k^{\prime}}(G)$. Thus,
$\mathscr{X}^{{\tiny\rm TAR}}_{k^{\prime}}(G)$ is connected. This implies
$x_{0}(G)\leq k$. When $k=\overline{X}(G)+1$, the bound
$x_{0}(G)\leq\overline{X}(G)+1$ [4] then implies $x_{0}(G)=\overline{X}(G)+1$.
The last statement is immediate from the first. ∎

######  Corollary 3.2.

Let $G$ be a graph. If $\mathscr{Z}^{{\tiny\rm TAR}}_{k}(G)$ is connected for
some $k>\overline{\operatorname{Z}}(G)$, then $\mathscr{Z}^{{\tiny\rm
TAR}}_{k^{\prime}}(G)$ is connected for $k^{\prime}=k,\dots,n$ and
$z_{0}(G)\leq k$. If $\mathscr{Z}^{{\tiny\rm
TAR}}_{\overline{\operatorname{Z}}(G)+1}(G)$ is connected, then
$z_{0}(G)=\overline{\operatorname{Z}}(G)+1$. If
$\underline{z_{0}}(G)>\overline{\operatorname{Z}}(G)$, then
$\underline{z_{0}}(G)=z_{0}(G)$.

######  Example 3.3.

Let $n\geq 4$ and consider the path $P_{n}$ with vertices in path order. Then
$S\subseteq V(P_{n})$ is a zero forcing set if and only if $S$ contains an
endpoint or $S$ contains two consecutive vertices in $S$. Hence the set
$\\{2,3\\}$ is a zero forcing set, but is not adjacent to any minimum zero
forcing set in $\mathscr{Z}^{{\tiny\rm TAR}}(P_{n})$. Thus
$\overline{\operatorname{Z}}(G)=2$. It is easy to see that
$\underline{z_{0}}(P_{n})=3$, so $z_{0}(P_{n})=\underline{z_{0}}(P_{n})=3$.

For TAR reconfiguration of the $X$-set parameters domination and power
domination, examples are known such that $x_{0}(G)$ exceeds the lower bound
$\overline{X}(G)+1$ (see [12] and [4]). Naturally, such examples are specific
to the $X$-set parameter being studied, and knowing examples for one $X$-set
parameter does not generally help construct such examples for other $X$-set
parameters. Next we construct a family of examples such that
$\overline{\operatorname{Z}}(G)+r\leq
z_{0}(G)<\min\\{\overline{\operatorname{Z}}(G)+\operatorname{Z}(G),|V(G)|\\}$
for $r\geq 2$. Software such as [7] is a useful tool for finding examples (and
found $H(2)$, which we then generalized).

Define $H(r)$ to be the graph with $2r+4$ vertices such that both sets
$V_{1}=\\{1,\dots,r+2\\}$ and $V_{2}=\\{r+3,\dots,2r+4\\}$ form cliques and
there is a matching between the vertices $\\{1,\dots,r\\}$ and
$\\{r+3,\dots,2r+2\\}$. The graphs $H(2)$ and $\mathscr{Z}^{{\tiny\rm
TAR}}(H(2))$ are shown in Figure 3.1.

12345687

$\\{3,5,6,7,8\\}$$\\{3,5,6,7\\}$$\\{3,4,5,6,7\\}$$\\{4,5,6,7\\}$$\\{4,5,6,7,8\\}$$\\{4,5,6,8\\}$$\\{3,4,5,6,8\\}$$\\{3,5,6,8\\}$$\\{3,6,7,8\\}$$\\{3,4,6,7,8\\}$$\\{4,6,7,8\\}$$\\{4,5,7,8\\}$$\\{3,4,5,7,8\\}$$\\{3,5,7,8\\}$$\\{1,3,6,7,8\\}$$\\{2,3,6,7,8\\}$$\\{1,4,6,7,8\\}$$\\{2,4,6,7,8\\}$$\\{1,3,5,7,8\\}$$\\{2,3,5,7,8\\}$$\\{1,4,5,7,8\\}$$\\{2,4,5,7,8\\}$$\\{1,3,5,6,8\\}$$\\{2,3,5,6,8\\}$$\\{1,3,5,6,7\\}$$\\{2,3,5,6,7\\}$$\\{1,4,5,6,8\\}$$\\{2,4,5,6,8\\}$$\\{1,4,5,6,7\\}$$\\{2,4,5,6,7\\}$$\\{1,2,3,4,7\\}$$\\{1,2,3,7\\}$$\\{1,2,3,7,8\\}$$\\{1,2,3,8\\}$$\\{1,2,3,4,8\\}$$\\{1,2,4,8\\}$$\\{1,2,4,7,8\\}$$\\{1,2,4,7\\}$$\\{2,3,4,7\\}$$\\{2,3,4,7,8\\}$$\\{2,3,4,8\\}$$\\{1,3,4,8\\}$$\\{1,3,4,7,8\\}$$\\{1,3,4,7\\}$$\\{2,3,4,5,7\\}$$\\{2,3,4,6,7\\}$$\\{2,3,4,5,8\\}$$\\{2,3,4,6,8\\}$$\\{1,3,4,5,7\\}$$\\{1,3,4,6,7\\}$$\\{1,3,4,5,8\\}$$\\{1,3,4,6,8\\}$$\\{1,2,4,5,7\\}$$\\{1,2,4,6,7\\}$$\\{1,2,3,5,7\\}$$\\{1,2,3,6,7\\}$$\\{1,2,4,5,8\\}$$\\{1,2,4,6,8\\}$$\\{1,2,3,5,8\\}$$\\{1,2,3,6,8\\}$

Figure 3.1: The graphs $H(2)$ (top) and $\mathscr{Z}^{{\tiny\rm
TAR}}_{5}(H(2))$ (bottom)

######  Proposition 3.4.

For $r\geq 2$, $\operatorname{Z}(H(r))=\overline{\operatorname{Z}}(H(r))=r+2$
and
$\underline{z_{0}}(H(r))=z_{0}(H(r))=2r+2=\overline{\operatorname{Z}}(H(r))+r$.

###### Proof.

Observe that the vertices $r+1,r+2,2r+3$ and $2r+4$ have degree $r+1$ and all
other vertices of $H(r)$ have degree $r+2$ so $\delta(H(r))=r+1$. Let
$U_{1}=\\{r+1,r+2\\}$ and $U_{2}=\\{2r+3,2r+4\\}$. If $v\in V_{i}$, then
$|N_{H(r)}(v)\cap V_{i}|=r+1$. Let $S\subset V(H(r))$ and let $S_{i}=S\cap
V_{i}$ for $i=1,2$. Assuming that $|S_{1}|\geq|S_{2}|$, we show that $S$ is a
zero forcing set of $H(r)$ if and only if $|S_{1}|\geq r+1$ and $|S_{2}\cap
U_{2}|\geq 1$. Once this is established,
$\operatorname{Z}(H(r))=\overline{\operatorname{Z}}(H(r))=r+2$ with a minimum
zero forcing set $S$ having ($|S_{1}|=r+1$ and $|S_{2}|=1$) or ($|S_{2}|=r+1$
and $|S_{1}|=1$). Furthermore, $\mathscr{Z}^{{\tiny\rm TAR}}_{2r+1}(H(r))$ has
2 components, one containing zero forcing sets $S$ with $|S_{1}|>|S_{2}|$ and
the other with $|S_{2}|>|S_{1}|$, whereas $\mathscr{Z}^{{\tiny\rm
TAR}}_{2r+2}(H(r))$ is connected.

Suppose first that $|S_{1}|=r+1$, $|S_{2}|=1$, and $S_{2}\subset U_{2}$ (the
argument where $|S_{2}|=r+1$ is similar). There must be a vertex $u\in
U_{1}\cap S_{1}$, and $u$ can force the one white vertex of $S_{1}$. Then
$i\to r+2+i$ for $i=1,\dots,r$. Finally any blue vertex of $V_{2}$ can force
the one remaining white vertex in $V_{2}$. Thus $S$ is a zero forcing set.

Now suppose $S$ is a zero forcing set. Let $v$ be the vertex that performs the
first force, and without loss of generality $v\in V_{1}$. Since $v$ and all
but one of its neighbors must be in $S$, $S$ contains at least $r+1$ of the
vertices in $S$. Since at most $r$ vertices of $V_{2}$ can be forced by
vertices in $V_{1}$, $S$ must contain a vertex of $V_{2}$ that has no neighbor
in $V_{1}$, i.e., $S$ must contain at least one vertex of $U_{2}$. ∎

A computer search on graphs up to 8 vertices (with no isolated vertices) found
exactly 2 graphs $G$ such that $z_{0}(G)>\underline{z_{0}}(G)$. For example,
the graph $H_{2}$ in Figure 3.2 has $z_{0}(H_{2})=7$ and
$\underline{z_{0}}(H_{2})=5$ (because there are minimal zero forcing sets of
orders 4 and 6 but not 5, and $\mathscr{Z}^{{\tiny\rm TAR}}_{5}(H_{2})$ is
connected, see [7]).

$\small{u_{1}}$$\small{u_{2}}$ Figure 3.2: A graph $H_{2}$ satisfying
$z_{0}(H_{2})>\underline{z_{0}}(H_{2})$

Next we show that the graph $H_{2}$ can be used to create an infinite family
of graphs $H_{r}$ such that $z_{0}(H_{r})>\underline{z_{0}}(H_{r})$. Observe
that $N_{H_{2}}(u_{2})=N_{H_{2}}(u_{1})$. Construct $H_{r}$ from $H_{2}$ by
adding vertices $u_{3},\dots,u_{r}$ with $N_{H_{r}}(u_{k})=N_{H_{r}}(u_{1})$
for $k=3,\dots,r$. In general, vertices $u_{1}$ and $u_{2}$ in a graph $G$ are
called _twins_ if $N_{G}(u_{1})=N_{G}(u_{2})$ (what we define as twins are
often called _independent twins_). A _set of twins_ is a set
$\\{u_{1},\dots,u_{k}\\}\subseteq V(G)$ such that $u_{i}$ and $u_{j}$ are
twins for all $1\leq i<j\leq k$.

######  Observation 3.5.

If $G$ is a graph with a set of twins $\\{u_{1},\dots,u_{r}\\}$, then any zero
forcing set of $G$ must contain at least $r-1$ of the vertices
$\\{u_{1},\dots,u_{r}\\}$.

######  Proposition 3.6.

Let $G$ be a graph that has a set of twins $T=\\{u_{1},\dots,u_{r}\\}$ with
$r\geq 3$, and let $G_{i}=G-u_{i}$. If $S_{i}$ is a zero forcing set of
$G_{i}$, then $S=S_{i}\cup\\{u_{i}\\}$ is a zero forcing set of $G$. If $S$ is
a zero forcing set of $G$ and $u_{i}\in S$, then $S_{i}=S\setminus\\{u_{i}\\}$
is a zero forcing set of $G_{i}$. Thus there is a bijection between zero
forcing sets of $G_{i}$ and zero forcing sets of $G$ that contain $u_{i}$, and
a zero forcing set $S_{i}$ of $G_{i}$ is minimal if and only if
$S=S_{i}\cup\\{u_{i}\\}$ is a minimal zero forcing set of $G$.

###### Proof.

It is immediate that $S_{i}$ being a zero forcing set of $G_{i}$ implies
$S=S_{i}\cup\\{u_{i}\\}$ is a zero forcing set of $G$ (without any assumption
about twins). Let $S$ be a zero forcing set of $G$. Since $r\geq 3$, $S$ must
contain at least two vertices in $T$, say $u_{i}$ and $u_{j}$. Choose a set of
forces $\mathscr{F}$ that color every vertex of $G$ blue. We show that at
least one of $u_{i}$ and $u_{j}$ does not perform a force. Neither $u_{i}$ nor
$u_{j}$ can perform a force until all but one of their common set of neighbors
are blue. So if $u_{i}$ forces the one white neighbor blue, then $u_{j}$
cannot perform a force and if $u_{j}$ forces, then $u_{i}$ can’t (it is
possible neither forces). Thus we may assume $u_{i}$ does not perform a force.
Then $S_{i}=S\setminus\\{u_{i}\\}$ is a zero forcing set of $G_{i}$ using the
set of forces $\mathscr{F}$. The last sentence is immediate. ∎

The technique of removing a nonforcing vertex $v$ from a zero forcing set $S$
of $G$ to obtain a zero forcing set $S\setminus\\{v\\}$ is well known (see,
for example, the proof of Theorem 2.7 in [8]). When there are only two twins,
it is not true that $S_{i}=S\setminus\\{u_{i}\\}$ must be a zero forcing set
of $G_{i}$, because it is possible that only one of $u_{1}$ and $u_{2}$ is in
$S$ and that vertex is required to perform a force. This is illustrated in the
next example.

######  Example 3.7.

Consider the _double star_ $DS(2,2)$ constructed by adding an edge between the
centers of two disjoint copies of $K_{1,2}$. If the leaves of one star are
$u_{1}$ and $u_{2}$, then
$\operatorname{Z}(DS(2,2))=2=\operatorname{Z}(DS(2,2)-u_{1})$ (see [7]).

######  Lemma 3.8.

Let $G$ be a graph that has a set of twins $T=\\{u_{1},\dots,u_{r}\\}$ with
$r\geq 3$, and let $G_{i}=G-u_{i}$. If $\mathscr{Z}^{{\tiny\rm
TAR}}_{k}(G_{i})$ is connected for some $i$, then $\mathscr{Z}^{{\tiny\rm
TAR}}_{k+1}(G)$ is connected.

###### Proof.

The graphs $G_{i}$ are isomorphic and hence the $\mathscr{Z}^{{\tiny\rm
TAR}}_{k}(G_{i})$ are isomorphic as well. Thus if $\mathscr{Z}^{{\tiny\rm
TAR}}_{k}(G_{i})$ is connected for some $i$ then $\mathscr{Z}^{{\tiny\rm
TAR}}_{k}(G_{i})$ is connected for all $i$.

For $S\subseteq V(G)$ with $u_{i}\in S$, let $S_{i}=S\setminus\\{u_{i}\\}$.
Since $r\geq 3$, any zero forcing set $S$ of $G$ must contain at least two
vertices in $T$, say $u_{i}$ and $u_{j}$. By Proposition 3.6, a set
$S\subseteq V(G)$ that contains $u_{i},u_{j}$ is a zero forcing set of $G$ if
and only if $S\setminus{u_{i}}$ is a zero forcing set of $G_{i}$ and
$S\setminus{u_{j}}$ is a zero forcing set of $G_{j}$.

Let $S,S^{\prime}$ be two zero forcing sets of $G$ of size $k+1$ or less.
Since $r\geq 3$ and each can omit at most one vertex in $T$, their
intersection must contain at least one $u_{i}$. Then
$S\setminus{u_{i}},S^{\prime}\setminus{u_{i}}$ are zero forcing sets for
$G_{i}$. Since by assumption $\mathscr{Z}^{{\tiny\rm TAR}}_{k}(G_{i})$ is
connected, that means that there is a path between $S\setminus{u_{i}}$ and
$S^{\prime}\setminus{u_{i}}$ in $\mathscr{Z}^{{\tiny\rm TAR}}_{k}(G_{i})$ and
hence a path between $S,S^{\prime}$ in $\mathscr{Z}^{{\tiny\rm
TAR}}_{k+1}(G)$. ∎

######  Proposition 3.9.

For $r\geq 2$, $\operatorname{Z}(H_{r})=r+2$, $\underline{z_{0}}(H_{r})=r+3$,
and $z_{0}(H_{r})=r+5$.

###### Proof.

The proof is by induction. The base case is $H=H_{2}$, which has minimal zero
forcing sets of sixes 4 and 6 and has $\mathscr{Z}^{{\tiny\rm
TAR}}_{5}(H_{2})$ is connected. Apply Proposition 3.6 to show that $H_{r}$ has
minimal zero forcing sets of sizes $r+2$ and $r+4$. Apply Lemma 3.8 to show
$\mathscr{Z}^{{\tiny\rm TAR}}_{r+3}(H_{r})$ is connected. ∎

## Acknowledgements

The authors thank the American Institute of Mathematics (AIM) and the National
Science Foundation (NSF) for support of this research. The research of B.
Curtis was also partially supported by NSF grant 1839918.

## References

  * [1] K. Adaricheva, C. Bozeman, N.E. Clarke, R. Haas, M.-E. Messinger, K. Seyffarth, and H.C. Smith. Reconfiguration Graphs for Dominating Sets. In Research Trends in Graph Theory and Applications (D. Ferrero, L. Hogben, S. Kingan, G. Mathews, editors), pp. 119–135, Springer, 2021.
  * [2] AIM Minimum Rank – Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. Cioaba, D. Cvetković, S. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K. Vander Meulen, and A. Wangsness Wehe). Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl., 428 (2008), 1628–1648.
  * [3] F. Barioli, W. Barrett, S. Fallat, H.T. Hall, L. Hogben, B. Shader, P. van den Driessche, and H. van der Holst. Zero forcing parameters and minimum rank problems. Linear Algebra Appl., 433 (2010), 401–411.
  * [4] B. Bjorkman, C. Bozeman, D. Ferrero, M. Flagg, C. Grood, L. Hogben, B. Jacob, and C. Reinhart. Power domination reconfiguration. https://arxiv.org/abs/2201.01798.
  * [5] K. Boyer, B. Brimkov, S. English, D. Ferrero, A. Keller, R. Kirsch, M. Phillips, C. Reinhart. The zero forcing polynomial of a graph. _Discrete Appl. Math._ 258 (2019), 35–48.
  * [6] B. Brimkov, J. Carlson. Minimal Zero Forcing Sets. https://arxiv.org/abs/2204.01810
  * [7] B. Curtis and L. Hogben. Sage code for ‘Isomorphisms and properties of TAR reconfiguration graphs for zero forcing and other $X$-set parameters.’ Available at https://sage.math.iastate.edu/home/pub/150/. PDF available at https://aimath.org/~hogben/ZeroForcingReconfiguration--Sage.pdf.
  * [8] C.J. Edholm, L. Hogben, M. Huynh, J. LaGrange, and D.D. Row. Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph. Linear Algebra Appl., 436 (2012), 4352–4372.
  * [9] J. Ekstrand, C. Erickson, H.T. Hall, D. Hay, L. Hogben, R. Johnson, N. Kingsley, S. Osborne, T. Peters, J. Roat, A. Ross, D.D. Row, N. Warnberg, and M. Young. Positive semidefinite zero forcing. Linear Algebra Appl., 439 (2013), 1862–1874.
  * [10] S. Fallat and L. Hogben. Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs. In Handbook of Linear Algebra, $2^{\text{nd}}$ ed., pp. 46-1–46-36, CRC Press, Boca Raton, FL, 2014.
  * [11] J. Geneson, R. Haas, and L. Hogben. Reconfiguration graphs of zero forcing sets. https://arxiv.org/abs/2009.00220.
  * [12] R. Haas, K. Seyffarth. The $k$-Dominating graph. _Graphs and Combin._ 30 (2014), 609–617.
  * [13] Richard P. Stanley. _Enumerative Combinatorics_ , Volume 1, $2^{\text{nd}}$ ed. Cambridge University Press, 2012.