# A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets

David Avis1 Duc A. Hoang2

( 1 Graduate School of Informatics, Kyoto University, Japan
School of Computer Science, McGill University, Canada
<EMAIL_ADDRESS>
2 Graduate School of Informatics, Kyoto University, Japan
<EMAIL_ADDRESS>)

###### Abstract

We continue the study of token sliding reconfiguration graphs of independent
sets initiated by the authors in an earlier paper (arXiv:2203.16861). Two of
the topics in that paper were to study which graphs $G$ are token sliding
graphs and which properties of a graph are inherited by a token sliding graph.
In this paper we continue this study specializing on the case of when $G$
and/or its token sliding graph $\mathsf{TS}_{k}(G)$ is a tree or forest, where
$k$ is the size of the independent sets considered. We consider two problems.
The first is to find necessary and sufficient conditions on $G$ for
$\mathsf{TS}_{k}(G)$ to be a forest. The second is to find necessary and
sufficient conditions for a tree or forest to be a token sliding graph. For
the first problem we give a forbidden subgraph characterization for the cases
of $k=2,3$. For the second problem we show that for every $k$-ary tree $T$
there is a graph $G$ for which $\mathsf{TS}_{k+1}(G)$ is isomorphic to $T$. A
number of other results are given along with a join operation that aids in the
construction of $\mathsf{TS}_{k}(G)$-graphs.

##  1 Introduction

In a _reconfiguration variant_ of a computational problem (e.g.,
Satisfiability, Independent Set, Vertex-Coloring, etc.), a _transformation
rule_ that describes an _adjacency relation_ between _feasible solutions_
(e.g., satisfying truth assignments, independent sets, proper vertex-
colorings, etc.) of the problem is given. One of the main goals is to decide
whether there is a sequence of adjacent feasible solutions that “reconfigures”
one given solution into another. Another way of looking at these
reconfiguration problems is via the so-called _reconfiguration graph_ —a graph
whose nodes are feasible solutions and two nodes are adjacent if one can be
obtained from the other by applying the given rule exactly once. The mentioned
question now becomes deciding whether there is a path between two given nodes
in the reconfiguration graph. Recently, _reconfiguration problems_ have been
intensively studied from different perspectives [8, 6, 7, 2].

One of the most well-studied reconfiguration variants of Independent Set is
the so-called Token Sliding problem, which was first introduced by Hearn and
Demaine [4] in 2005. We refer readers to [8, 7, 2] and the references therein
for more details. Surprisingly, though Token Sliding has been well-
investigated, the realizability and structural properties of its corresponding
reconfiguration graph—the one which we will refer to as the _$\mathsf{TS}_{k}$
-graph_ (which stands for _Token Sliding (Reconfiguration) graph_)—have not
been studied until recently [1]. On the other hand, when considering either
general vertex subsets, dominating sets, or proper vertex-colorings of a graph
as the “input feasible solutions”, their corresponding reconfiguration graphs
have been very well-characterized [5, 6].

For any graph-theoretic terminology and notation not defined here, we refer
readers to [3]. Given a graph $G=(V,E)$ and an integer $k\geq 2$. For two sets
$X,Y$, we sometimes use $X+Y$ and $X-Y$ to indicate $X\cup Y$ and $X\setminus
Y$. We abbreviate $X\cup\\{u\\}$ (resp., $X\setminus\\{u\\}$) by $X+u$ (resp.,
$X-u$). We use $N_{G}(u)$, or simply just $N(u)$ when the graph $G$ is clear
from the context, to denote the _(open) neighbors_ of $u$, i.e., set of all
vertices in $G$ that are adjacent to $u$. The _closed neighbors_ of $u$,
denoted by $N_{G}[u]$ or simply $N[u]$, is the set $N_{G}(u)+u$. The _degree_
of $u$, denoted by $\deg_{G}(u)$, is nothing but the size of $N_{G}(u)$. An
_independent set_ (or _stable set_) of $G$ is a vertex subset $I$ such that
for every $u,v\in I$ we have $uv\notin E(G)$. The _$\mathsf{TS}_{k}$ -graph_
of $G$, denoted by $\mathsf{TS}_{k}(G)$, takes all size-$k$ independent sets
of $G$ as its nodes and two nodes $I,J$ are _adjacent (under Token Sliding (
$\mathsf{TS}$))_ if there exist two vertices $u,v\in V(G)$ such that
$I-J=\\{u\\}$, $J-I=\\{v\\}$, and $uv\in E(G)$. Two graphs $G$ and $H$ are
_isomorphic_ , denoted by $G\simeq H$, if there exists a bijective mapping
$f:V(G)\to V(H)$ such that $uv\in E(G)$ if and only if $f(u)f(v)\in E(H)$. A
graph $G$ is called a _$\mathsf{TS}_{k}$ -graph_ if there exists a graph $H$
such that $G\simeq\mathsf{TS}_{k}(H)$. A _forest_ is a graph having no cycles
(i.e., it is _acyclic_) and a connected forest is a _tree_. A
_$\mathsf{TS}_{k}$ -tree/forest_ is a $\mathsf{TS}_{k}$-graph which is also a
tree/forest. Figure 1 illustrates a $\mathsf{TS}_{2}$-tree on six vertices
(right).

$ab$$ac$$bd$$ae$$ef$$ce$$\mathsf{TS}_{2}(G)$$a$$b$$c$$d$$e$$f$$G$ Figure 1: A
graph $G$ with $\mathsf{TS}_{2}(G)=D_{1,3,2}$. Each node $ab$ represents a
size-$2$ stable set of $G$.

In [1], the authors studied various properties of the family of
$\mathsf{TS}_{k}$-graphs. For a graph $G$, two of the questions studied were:

  * (Q1)

What are necessary and sufficient conditions for $G$ so that
$\mathsf{TS}_{k}(G)$ is a forest?

  * (Q2)

What are necessary and sufficient conditions for $G$ to be a
$\mathsf{TS}_{k}$-graph?

In this paper, we study these two questions for the case when $G$ is a tree or
a forest.

The _union_ $G\cup H$ of two (labelled) graphs $G$ and $H$ is the graph with
$V(G\cup H)=V(G)\cup V(H)$ and $E(G\cup H)=E(G)\cup E(H)$. When vertices and
edges of $G$ and $H$ are considered distinct regardless of their labels, we
say that $G\cup H$ is the _disjoint union_ of $G$ and $H$, and write $G+H$
instead of $G\cup H$ to distinguish from their union. We respectively denote
by $K_{n}$, $P_{n}$, and $C_{n}$ the _complete graph_ , _path_ , and _cycle_
on $n$ vertices. $K_{m,n}$ ($m\leq n$) is the _complete bipartite graph_ whose
two partite sets are of sizes $m$ and $n$ respectively. $K_{1,n}$ is also
called a _star_ —a tree obtained by attaching $n$ leaves to a central vertex.
A family of graphs that we will use in the sequel generalizes stars and paths.
For fix integers $n,r,s\geq 1$, let $D_{r,n,s}$ be the tree obtained from
$P_{n}$ by appending $r$ leaves at one end and $s$ leaves at the other. Note
that $D_{1,1,s}$ is the star $K_{1,s+1}$ and $D_{1,n,1}$ is the path
$P_{n+2}$. Figure 1 illustrates $D_{1,3,2}$ (right). An _$n$ -ary tree_ is a
rooted tree in which each node has at most $n$ children. Any tree with maximum
degree at most $n+1$ can be rooted at a vertex with degree at most $n$ (e.g.,
a leaf) to produce a $n$-ary tree. In particular, a $2$-ary tree is nothing
but the well-known binary tree.

In the next section, we begin by partially answering (Q1) when $G$ is a
tree/forest and $k\in\\{2,3\\}$ and conclude the section by conjecturing for
$k\geq 4$. Then, before addressing (Q2) for some trees/forests, in particular
$k$-ary trees and $D_{r,n,s}$, we define an important graph operation which,
under certain conditions, can be used for combining two
$\mathsf{TS}_{k}$-graphs by taking their union to obtain a new one. The final
section of the paper gives some concluding remarks.

##  2 Results on (Q1)

$G$$\mathsf{TS}_{2}(G)$ $\mathsf{TS}_{2}(G)$ Figure 2: A list $\mathcal{G}$ of
$n$-vertex graphs $G$ ($4\leq n\leq 7$) excluding $\overline{C_{n}}$ ($n\geq
5$) such that if $\mathsf{TS}_{2}(G^{\prime})$ has no cycle then $G^{\prime}$
does not contain any member $G$ of $\mathcal{G}$ as an induced subgraph.

In this section, we prove the necessary and sufficient conditions on a
tree/forest $G$ such that $\mathsf{TS}_{k}(G)$ is acyclic for $k\in\\{2,3\\}$,
partially answering (Q1).

We begin with some definitions and observations. The _complement_
$\overline{G}$ of a graph $G$ is the graph with $V(\overline{G})=V(G)$ and
$E(\overline{G})=\\{uv:uv\notin E(G)\\}$. The _size- $m$ matching_, denoted by
$mK_{2}$, is the graph obtained by taking the disjoint union of $m$ copies of
$K_{2}$. Observe that $\mathsf{TS}_{2}(2K_{2})\simeq C_{4}$. We label vertices
in a $D_{r,n,s}$ ($r,s\geq 1$) as follows: Vertices of $P_{n}$ are labelled
$p_{1},\dots,p_{n}$. The $r$ leaves attached to $p_{1}$ are
$u_{1},\dots,u_{r}$ and the $s$ leaves attached to $p_{n}$ are
$v_{1},\dots,v_{n}$. $D_{2,2,2}$ is shaped like an H and
$\mathsf{TS}_{2}(D_{2,2,2})$ contains a cycle $C_{8}$ whose vertex-set is
$\\{u_{1}v_{1},u_{1}p_{2},u_{1}v_{2},p_{1}v_{2},u_{2}v_{2},u_{2}p_{2},u_{2}v_{1},p_{1}v_{1}\\}$.
Indeed, respectively from Lemma 1 of [1] and Figure 2, if a $n$-vertex graph
$G$ is either $\overline{C_{n}}$ ($n\geq 5$) or a graph in the list
$\mathcal{G}$ described in Figure 2 (which includes $2K_{2}$ and $D_{2,2,2}$),
the graph $\mathsf{TS}_{2}(G)$ contains a cycle. Additionally, we have:

######  Lemma 1.

  * (a)

For $k\geq 2$, $\mathsf{TS}_{k}(2K_{2}+nK_{1})$ contains a cycle $C_{4}$ if
$n\geq k-2$ otherwise it is acyclic.

  * (b)

For $k\in\\{2,3\\}$, $s\geq 1$, $\mathsf{TS}_{k}(D_{1,n,s})$ contains a cycle
$C_{4}$ if $n\geq 2k-1$ otherwise it is acyclic.

  * (c)

For $k\in\\{2,3\\}$ and $r,s\geq 2$, $\mathsf{TS}_{k}(D_{r,n,s})$ contains a
cycle $C_{8}$ if $n\geq 2k-2$ otherwise it is acyclic.

###### Proof.

  * (a)

If $n<k-2$, there is no size-$k$ independent set in $2K_{2}+nK_{1}$, thus its
$\mathsf{TS}_{k}$-graph is obviously acyclic. Otherwise, let $I\subseteq
V(nK_{1})$ be an arbitrary independent set of size $k-2$, and let
$E(2K_{2})=\\{ab,cd\\}$. Then, $\\{I+a+c,I+a+d,I+b+c,I+b+d\\}$ induce a
$C_{4}$ in $\mathsf{TS}_{k}(2K_{2}+nK_{1})$.

  * (b)

Observe that if $n\geq 2k-1$, $D_{1,n,s}$ contains an induced
$2K_{2}+(k-2)K_{1}$, which can be obtained by taking $u_{1}p_{1}$ and
$p_{n}v_{1}$ as edges of $2K_{2}$ and the remaining $k-2$ independent vertices
from the path
$D_{1,n,s}-\\{u_{1},p_{1},p_{2},p_{n-1},p_{n},v_{1},\dots,v_{s}\\}$ on $n-4$
vertices. (Since $n\geq 2k-1$, this path has an independent set of size at
least $\lceil(n-4)/2\rceil\geq\lceil(2k-5)/2\rceil=k-2$.) Then, using a
similar argument as in (a) we have $\mathsf{TS}_{k}(D_{1,n,s})$ contains a
$C_{4}$.

On the other hand, if $n\leq 2k-2$ for $k\in\\{2,3\\}$, since $D_{1,n-1,s}$ is
always an induced subgraph of $D_{1,n,s}$ for $n\geq 2$, it follows that if
$\mathsf{TS}_{2}(D_{1,n-1,s})$ has a cycle then so is
$\mathsf{TS}_{2}(D_{1,n,s})$. Therefore, it suffices to show that
$\mathsf{TS}_{k}(D_{1,2k-2,s})$ is acyclic for $k\in\\{2,3\\}$. Indeed, based
on the number of tokens placed on the path $u_{1}p_{1}\dots p_{n}$ (which is
at most three), one can verify that each component of
$\mathsf{TS}_{k}(D_{1,2k-2,s})$ is either an isolated vertex, a path, or a
star.

  * (c)

Observe that if $n\geq 2k-2$, $D_{r,n,s}$ contains the independent sets
$I+u_{1}+v_{1}$, $I+u_{1}+p_{n}$, $I+u_{1}+v_{s}$, $I+p_{1}+v_{1}$,
$I+p_{1}+v_{s}$, $I+u_{r}+v_{1}$, $I+u_{r}+p_{n}$, and $I+u_{r}+v_{s}$, where
$I=\emptyset$ when $n=2$ and otherwise $I$ is an independent set of the path
$p_{2}\dots p_{n-1}$ of size $k-2$. (Note that $p_{2}\dots p_{n-1}$ has an
independent set of size at most $\lceil(n-2)/2\rceil\geq k-2$.) They indeed
induce a $C_{8}$ in $\mathsf{TS}_{k}(D_{r,n,s})$.

On the other hand, if $n\leq 2k-3$ for $k\in\\{2,3\\}$, using a similar case-
analysis as in (b), one can verify that each component of
$\mathsf{TS}_{k}(D_{r,n,s})$ is either an isolated vertex, a path, or a star,
and therefore it is acyclic.

∎

We are now ready to show the necessary and sufficient conditions for a
tree/forest $G$ such that $\mathsf{TS}_{k}(G)$ is acyclic, where
$k\in\\{2,3\\}$.

######  Proposition 2.

Let $T$ be a tree. Then $\mathsf{TS}_{2}(T)$ is acyclic if and only if $T$ is
$\\{2K_{2},D_{2,2,2}\\}$-free.

###### Proof.

  * ($\Rightarrow$)

Suppose to the contrary that either $2K_{2}$ or $D_{2,2,2}$ is an induced
subgraph of $T$. In the first case it follows from the discussion above that
$\mathsf{TS}_{2}(T)$ contains a $C_{4}$ and in the second case that it
contains a $C_{8}$.

  * ($\Leftarrow$)

We assume that $\mathsf{TS}_{2}(T)$ contains a cycle and show that it must
contain one of the two forbidden subgraphs. Firstly, suppose that $T$ is a
path $P_{n}$. Since $\mathsf{TS}_{2}(T)$ contains a cycle, it follows from
Lemma 1(b) that $n\geq 5$ and so $T$ contains an induced $2K_{2}$.

We now assume $T$ has a vertex of at least degree 3. We will construct a copy
$T^{\prime}$ of $T$ by initially choosing a vertex $a$ of maximum degree in
$T$ and letting $T^{\prime}=N[a]$. Note that $\mathsf{TS}_{2}(T^{\prime})$ is
acyclic. We add edges from $T$ to $T^{\prime}$ and show after each addition
that either $T^{\prime}$ contains a forbidden subgraph, so we are done, or
that $\mathsf{TS}_{2}(T^{\prime})$ remains acyclic so that $T\neq T^{\prime}$.

Let $b$ be a child of $a$ of highest degree, $c$ be a child of next highest
degree, and $d$ be any other child. Since $\mathsf{TS}_{2}(T^{\prime})$ is
acyclic $T\neq T^{\prime}$ and $b$ must have $r\geq 1$ children. Let $e$ be a
child of $b$ with maximum degree. We add $N[b]$ to $T^{\prime}$ obtaining a
copy of $D_{r,2,s}$, where $s=\deg_{T}(a)-1\geq 2$. If $r\geq 2$, we have the
required forbidden induced subgraph. If $r=1$ then by Lemma 1(b)
$\mathsf{TS}_{2}(T^{\prime})$ is acyclic, so there must be extra edges to add
to $T^{\prime}$. If $c$ has a child $y$ then $\\{b,c,e,y\\}$ induce a
$2K_{2}$. Otherwise, $e$ must have at least one child $g$. Adding $eg$ to
$T^{\prime}$ we obtain $2K_{2}$ as an induced subgraph on $\\{a,d,e,g\\}$.
This completes the proof.

Figure 3: Illustration for Proposition 2: Some trees $T^{\prime}$ containing
$N[b]$ whose $\mathsf{TS}_{2}$-graphs have a cycle. Here $r$ is the number of
children of $b$. Copies of $2K_{2}$ and $D_{2,2,2}$ are marked by red color.

∎

######  Corollary 3.

Let $T$ be a tree. Then $\mathsf{TS}_{2}(T)$ is acyclic if and only if $T$ is
either $K_{1,s}$ or $D_{1,2,s}$ for some positive integer $s$.

###### Proof.

The proof of Proposition 2 can be viewed as an algorithm that takes a tree $T$
and either terminates with $T=T^{\prime}$ being one of the trees in the
corollary or finds a forbidden induced graph in $T$. ∎

######  Corollary 4.

Let $F$ be a forest. Then $\mathsf{TS}_{2}(F)$ is a acyclic if and only if $F$
is $\\{2K_{2},D_{2,2,2}\\}$-free.

###### Proof.

We prove that $\mathsf{TS}_{2}(F)$ contains a cycle if and only if $F$
contains one of the graphs in $\\{2K_{2},D_{2,2,2}\\}$ as an induced subgraph.

Suppose that $\mathsf{TS}_{2}(F)$ contains a cycle. Since the independent sets
have size two, both vertices of each independent set must lie in the same
connected component $T$ of $F$. By Proposition 2, the tree $T$ must have
either $2K_{2}$ or $D_{2,2,2}$ as an induced subgraph.

Conversely if $F$ contains $2K_{2}$ or $D_{2,2,2}$ as an induced subgraph then
$\mathsf{TS}_{2}(F)$ contains respectively a $C_{4}$ or a $C_{8}$. ∎

Moving to the case of stable sets of size three, the conditions for trees and
forests differ slightly. We deal with the tree case first.

######  Proposition 5.

Let $T$ be a tree. Then $\mathsf{TS}_{3}(T)$ is acyclic if and only if $T$ is
$\\{2K_{2}+K_{1},D_{2,4,2}\\}$-free.

###### Proof.

The structure of the proof is the same as for Proposition 2. However, there
are more cases to consider.

  * ($\Rightarrow$)

Suppose to the contrary that either $2K_{2}+K_{1}$ or $D_{2,4,2}$ is an
induced subgraph of $T$. In the first case it follows that
$\mathsf{TS}_{3}(T)$ contains a $C_{4}$ and in the second case that it
contains a $C_{8}$.

  * ($\Leftarrow$)

We assume that $\mathsf{TS}_{3}(T)$ contains a cycle and show that it must
contain one of the two forbidden subgraphs. The first part of the proof is
essentially the same as for Proposition 2 with minor modifications. Firstly
suppose that $T$ is a path $P_{n}$. Since $\mathsf{TS}_{3}(T)$ contains a
cycle it follows from Lemma 1(b) that $n\geq 7$ and so $T$ contains an induced
$2K_{2}+K_{1}$.

We now assume $T$ has a vertex of at least degree 3. We will construct a copy
$T^{\prime}$ of $T$ by initially choosing a vertex $a$ of maximum degree in
$T$ and letting $T^{\prime}=N[a]$. Note that $\mathsf{TS}_{3}(T^{\prime})$ is
acyclic. We add edges from $T$ to $T^{\prime}$ showing after each addition
that either $T^{\prime}$ contains a forbidden subgraph, so we are done, or
that $\mathsf{TS}_{3}(T^{\prime})$ remains acyclic so that $T\neq T^{\prime}$.

Let $b$ be a child of $a$ of highest degree, $c$ be a child of next highest
degree, and $d$ be any other child. Since $\mathsf{TS}_{3}(T^{\prime})$ is
acyclic $T\neq T^{\prime}$ and $b$ must have $r\geq 1$ children. Let $e$ be a
child of $b$ with maximum degree. If $c$ has a child $y$ then
$\\{b,c,d,e,y\\}$ induce a $2K_{2}+K_{1}$ and we are done. Otherwise we add
$N[b]$ to $T^{\prime}$ obtaining a copy of $D_{r,2,s}$, where
$s=\deg_{T}(a)-1\geq 2$. By Lemma 1(c), $\mathsf{TS}_{3}(T^{\prime})$ is
acyclic and so $T\neq T^{\prime}$. There are two cases:

    * ($r\geq 2$)

Let $f$ be a second child of $b$ and let $g$ be a child of $e$. Adding $eg$ to
$T^{\prime}$ we obtain $2K_{2}+K_{1}$ as an induced subgraph on
$\\{a,d,e,f,g\\}$.

    * ($r=1$)

Since $e$ is the only child of $b$ it must have children. Let $t\geq 1$ be the
number of children of $e$ and let $h$ be the child of $e$ of maximum degree.
We add $N[e]$ to $T^{\prime}$ obtaining a copy of $D_{t,3,s}$ and
$\mathsf{TS}_{3}(T^{\prime})$ is acyclic by Lemma 1(c). There are two
subcases:

      * ($t\geq 2$)

Let $i$ be any other child of $e$. Since $\mathsf{TS}_{3}(T^{\prime})$ is
acyclic $h$ must have at least one child $j$. We have now constructed an
induced $2K_{2}+K_{1}$ on $\\{a,d,h,i,j\\}$.

      * ($t=1$)

If $h$ has a single child $k$ add $hk$ to $T^{\prime}$ which is a copy of
$D_{1,4,s}$ and again by Lemma 1(c) $\mathsf{TS}_{3}(T^{\prime})$ is acyclic.
So $k$ has a child $l$. Adding $kl$ to $T^{\prime}$ it contains an induced
$P_{7}$ and we find the forbidden subgraph $2K_{2}+K_{1}$ on vertices
$\\{a,d,e,k,l\\}$. Otherwise, $h$ has at least two children including vertices
$k$ and $m$. Adding edges $hk$ and $hm$ to $T^{\prime}$ we obtain the
forbidden subgraph $D_{2,4,2}$. This completes the proof.

Figure 4: Illustration for Proposition 5: Some trees $T^{\prime}$ containing
$N[b]$ whose $\mathsf{TS}_{3}$-graphs have a cycle. Here $r$ and $t$ are
respectively the number of children of $b$ and its child $e$. Copies of
$2K_{2}+K_{1}$ and $D_{2,4,2}$ are marked by red color.

∎

######  Corollary 6.

Let $T$ be a tree. Then $\mathsf{TS}_{3}(T)$ is a acyclic if and only if for
some positive integer $s$, $T$ is either $K_{1,s}$, $D_{1,n,s}$ where $n\leq
4$, or $D_{r,n,s}$ where $r\geq 2$ and $n\leq 3$.

###### Proof.

The proof of Proposition 5 can be viewed as an algorithm that takes a tree $T$
and either terminates with $T=T^{\prime}$ being one of the trees in the
corollary or finds a forbidden induced graph in $T$ showing that
$\mathsf{TS}_{3}(T)$ has a cycle. ∎

######  Corollary 7.

Let $F$ be a forest. Then $\mathsf{TS}_{3}(F)$ is a forest if and only if $F$
is $\\{2K_{2}+K_{1},D_{2,2,2}+K_{1},D_{2,4,2}\\}$-free.

###### Proof.

We prove that $\mathsf{TS}_{3}(F)$ contains a cycle if and only if $F$
contains one of the graphs in $\\{2K_{2}+K_{1},D_{2,2,2}+K_{1},D_{2,4,2}\\}$
as an induced subgraph.

Suppose that $\mathsf{TS}_{3}(F)$ contains a cycle $C$. Since the independent
sets have size three, there are three cases to consider. Firstly, if the three
vertices of each independent set in $C$ lie in the same connected component
$T$ of $F$, by Proposition 5, the tree $T$ must have either $2K_{2}+K_{1}$ or
$D_{2,4,2}$ as an induced subgraph. Secondly, suppose two of the vertices of
each stable set lie in the same connected component $T$ of $F$, which must
have at least two connected components. Thus, $C$ induces a cycle in
$\mathsf{TS}_{2}(T)$. So by Proposition 2, the tree $T$ must have either
$2K_{2}$ or $D_{2,2,2}$ as an induced subgraph. Since $F$ has at least two
components, $F$ contains $2K_{2}+K_{1}$ or $D_{2,2,2}+K_{1}$. Finally, suppose
each vertex of each stable set lies in a different component of $F$, which
therefore has at least three components. At least two of these components must
be non-trivial, i.e., contain an edge. Therefore, $F$ contains an induced
$2K_{2}+K_{1}$.

Conversely, suppose $F$ contains $2K_{2}+K_{1}$, $D_{2,2,2}+K_{1}$ or
$D_{2,4,2}$ as an induced subgraph. Then $\mathsf{TS}_{3}(F)$ contains a
$C_{4}$ in the first instance or a $C_{8}$ in the other two. ∎

For $k\geq 4$, we have the following proposition.

######  Proposition 8.

Let $F$ be a forest. For $k\geq 4$, if $F$ contains either
$2K_{2}+(k-2)K_{1}$, or $D_{2,2,2}+(k-2)K_{1}$, or $D_{2,4,2}+(k-3)K_{1}$ as
an induced subgraph, $\mathsf{TS}_{k}(F)$ has a cycle.

###### Proof.

One can verify that $\mathsf{TS}_{2}(2K_{2})$ contains a $C_{4}$, and
$\mathsf{TS}_{2}(D_{2,2,2})$ and $\mathsf{TS}_{3}(D_{2,4,2})$ both contain a
$C_{8}$. As a result, so do $\mathsf{TS}_{k}(2K_{2}+(k-2)K_{1})$,
$\mathsf{TS}_{k}(D_{2,2,2}+(k-2)K_{1})$, and
$\mathsf{TS}_{k}(D_{2,4,2}+(k-3)K_{1})$, respectively. Consequently,
$\mathsf{TS}_{k}(F)$ has a cycle, as desired. ∎

We conclude this section with the following conjecture for $k\geq 4$.

######  Conjecture 9.

Let $F$ be a forest. For $k\geq 4$, if $\mathsf{TS}_{k}(F)$ is a forest, $F$
is $\\{2K_{2}+(k-2)K_{1},D_{2,2,2}+(k-2)K_{1},D_{2,4,2}+(k-3)K_{1}\\}$-free.

##  3 $H$-join and $H$-decomposition

Before considering (Q2), in this section, we describe an operation for
combining $\mathsf{TS}_{k}$-graphs to produce new ones. We first define a
family of _base graphs_ as follows. Let $V$ be a set of $k+1$ vertices
including two labelled $u$ and $v$. Then $B_{k}(V,uv)$ is the graph with
vertex set $V$ and single edge $uv$. We have
$\mathsf{TS}_{k}(B_{k}(V,uv))=K_{2}$ whose two vertices are labelled by the
independent sets $V-u$ and $V-v$. Next, we define the _$H$ -join_ operation
and its inverse.

######  Definition 10.

Vertex-labelled graphs $G_{1}$ and $G_{2}$ are _$H$ -consistent_ if the
(possibly empty) intersection of their vertex sets define the same (possibly
empty) common induced subgraph $H$. The _$H$ -join_ of $H$-consistent graphs
$G_{1}$ and $G_{2}$ is the graph $H(G_{1},G_{2})$ with
$V(H(G_{1},G_{2}))=V(G_{1})\cup V(G_{2})$. The edges $E(H(G_{1},G_{2}))$
consist of $E(G_{1})\cup E(G_{2})$ plus all edges $vw$ with $v\in
V(G_{1})\setminus V(H)$ and $w\in V(G_{2})\setminus V(H)$.

Recall that a _(vertex) cut-set_ in a connected graph $G$ is a vertex set $W$
such that $G-W$ is disconnected. We extend this definition to the case where
$G$ is disconnected by allowing $W=\emptyset$. We say that $W$ decomposes $G$
into two (not necessarily connected) induced subgraphs $G_{1}$ and $G_{2}$ for
which $V(G_{1})\cap V(G_{2})=W$ and $V(G_{1})\cup V(G_{2})=V(G)$. If $G-W$ has
more than two (connected) components, the decomposition is not unique.

######  Definition 11.

Let $G$ be a vertex-labelled graph. Let $W\subset V(\overline{G})=V(G)$
decompose the complement $\overline{G}$ into $\overline{G_{1}}$ and
$\overline{G_{2}}$. Let $H$ be the subgraph of $G$ induced by $W$. We say that
$G$ can be _$H$ -decomposed_ into $G_{1}$ and $G_{2}$.

It follows from the definitions that if $G=H(G_{1},G_{2})$ then $G$ can be
$H$-decomposed into $G_{1}$ and $G_{2}$, and vice versa. It is easy to verify
that the size-$k$ independent sets of $H(G_{1},G_{2})$ are the union of those
of $G_{1}$ and those of $G_{2}$.

As an example consider the two $4$-vertex graphs $G_{1}$ and $G_{2}$ that are
paths with edge sets $E(G_{1})=\\{ad,bc,cd\\}$ and $E(G_{2})=\\{ad,ae,eb\\}$.
These share a common induced subgraph $H$ with $V(H)=\\{a,b,d\\}$ and
$E(H)=\\{ad\\}$. We have $V(H(G_{1},G_{2}))=\\{a,b,c,d,e\\}$ and
$E(H(G_{1},G_{2}))=\\{ad,ae,bc,cd,ce,be\\}$. Note that
$\mathsf{TS}_{2}(G_{1})$ is the path with edges $\\{ac-ab,ab-bd\\}$ and that
$\mathsf{TS}_{2}(G_{2})$ is the path with edges $\\{ab-bd,bd-de\\}$. It can be
verified that $\mathsf{TS}_{2}(H(G_{1},G_{2}))$ is the path with edges $\\{ac-
ab,ab-bd,bd-de\\}$ which is the union of two paths $\mathsf{TS}_{2}(G_{1})$
and $\mathsf{TS}_{2}(G_{2})$. (See Figure 5.)

$a$$b$$c$$d$$G_{1}$$a$$b$$e$$d$$G_{2}$$c$$e$$a$$b$$d$$H(G_{1},G_{2})$$ab$$ac$$bd$$\mathsf{TS}_{2}(G_{1})$$ab$$de$$bd$$\mathsf{TS}_{2}(G_{2})$$ab$$ac$$de$$bd$$\mathsf{TS}_{2}(H(G_{1},G_{2}))$

Figure 5: The graphs $G_{1}$, $G_{2}$, $H(G_{1},G_{2})$, and their
corresponding $\mathsf{TS}_{2}$-graphs. Here
$\mathsf{TS}_{2}(H(G_{1},G_{2}))=\mathsf{TS}_{2}(G_{1})\cup\mathsf{TS}_{2}(G_{2})$.

Now consider the graph $G_{3}$ which is the path with edges $\\{ad,cd,ce\\}$.
$G_{1}$ and $G_{3}$ share a common induced subgraph $H$ with
$V(H)=\\{a,c,d\\}$ and $E(H)=\\{ad,cd\\}$. We have
$E(H(G_{1},G_{3}))=\\{ad,bc,be,cd,ce\\}$. Note that $\mathsf{TS}_{2}(G_{3})$
is the path with edges $\\{ac-ae,ae-de\\}$. In this case,
$\mathsf{TS}_{2}(H(G_{1},G_{3}))$ is the graph with edges $\\{ab-ac,ac-ae,ae-
de,de-bd,bd-ab,ab-ae\\}$ which is the union of $\mathsf{TS}_{2}(G_{1})$,
$\mathsf{TS}_{2}(G_{3})$, and the two additional edges $de-bd,ab-ae$. (See
Figure 6.)

$a$$b$$c$$d$$G_{1}$$a$$e$$c$$d$$G_{3}$$b$$e$$a$$c$$d$$H(G_{1},G_{3})$$ab$$ac$$bd$$\mathsf{TS}_{2}(G_{1})$$ac$$ae$$ed$$\mathsf{TS}_{2}(G_{3})$$ab$$ac$$ae$$bd$$ed$$\mathsf{TS}_{2}(H(G_{1},G_{3}))$

Figure 6: The graphs $G_{1}$, $G_{3}$, $H(G_{1},G_{3})$, and their
corresponding $\mathsf{TS}_{2}$-graphs. Here
$\mathsf{TS}_{2}(H(G_{1},G_{3}))\neq\mathsf{TS}_{2}(G_{1})\cup\mathsf{TS}_{2}(G_{3})$.

As the last example in this section, consider the graphs $G_{4}$ and $G_{5}$
as follows. $G_{4}$ is the cycle with edges $\\{ae,eb,bc,cd,ad\\}$ and $G_{5}$
is the graph with edges $\\{ae,eb,bc,ag,eg,bg\\}$. $G_{4}$ and $G_{5}$ shares
a common induced subgraph $H$ with $V(H)=\\{a,e,b,c\\}$ and
$E(H)=\\{ae,eb,bc\\}$. We have
$E(H(G_{4},G_{5}))=\\{ae,eb,bc,cd,ad,ag,eg,bg,dg\\}$. In this case,
$\mathsf{TS}_{2}(H(G_{4},G_{5}))$ is the (non-acyclic) graph with edges
$\\{ab-ac,ac-ce,ce-de,de-bd,ab-bd,ac-cg,ce-cg\\}$ which is the union of
$\mathsf{TS}_{2}(G_{4})$ and $\mathsf{TS}_{2}(G_{5})$. (See Figure 7.)

$a$$e$$b$$c$$d$$G_{4}$$a$$e$$b$$c$$g$$G_{5}$$d$$g$$a$$e$$b$$c$$H(G_{4},G_{5})$$ab$$ac$$ce$$de$$bd$$\mathsf{TS}_{2}(G_{4})$$ab$$ac$$ce$$cg$$\mathsf{TS}_{2}(G_{5})$$ab$$ac$$ce$$de$$bd$$cg$$\mathsf{TS}_{2}(H(G_{4},G_{5}))$

Figure 7: The graphs $G_{4}$, $G_{5}$, $H(G_{4},G_{5})$ and their
corresponding (non-acyclic) $\mathsf{TS}_{2}$-graphs. Here
$\mathsf{TS}_{2}(G_{4},G_{5})=\mathsf{TS}_{2}(G_{4})\cup\mathsf{TS}_{2}(G_{5})$.

In the next proposition, we show how to compute the $\mathsf{TS}_{k}$-graph of
an $H$-join, generalizing the examples given above.

######  Proposition 12.

Let $k\geq 2$ and let $G_{1}$ and $G_{2}$ be two $H$-consistent graphs.
$\mathsf{TS}_{k}(H(G_{1},G_{2}))$ is the union of $\mathsf{TS}_{k}(G_{1})$,
$\mathsf{TS}_{k}(G_{2})$ and for every pair of $k$-element independent sets
$S_{1}$ in $G_{1}$ and $S_{2}$ in $G_{2}$ satisfying

$|S_{1}\cap V(H)|=|S_{2}\cap V(H)|=|S_{1}\cap S_{2}|=k-1,$ (1)

the edge between $S_{1}$ and $S_{2}$.

###### Proof.

As remarked, the $k$-element independent sets of $H(G_{1},G_{2})$ are the same
as the union of those of $G_{1}$ and $G_{2}$. Therefore,
$V(\mathsf{TS}_{k}(H(G_{1},G_{2})))=V(\mathsf{TS}_{k}(G_{1}))\cup
V(\mathsf{TS}_{k}(G_{2}))$. Next, consider an edge in
$E(\mathsf{TS}_{k}(G_{1}))$ (respectively, $E(\mathsf{TS}_{k}(G_{2}))$). It is
a token-slide between two independent sets $S_{1}$ and $S_{2}$ in $G_{1}$
(respectively, $G_{2}$). This remains as a token-slide in $H(G_{1},G_{2})$.
Therefore, $E(\mathsf{TS}_{k}(G_{1}))\cup E(\mathsf{TS}_{k}(G_{2}))\subseteq
E(\mathsf{TS}_{k}(H(G_{1},G_{2})))$. Now, consider an edge in
$E(\mathsf{TS}_{k}(H(G_{1},G_{2})))$ between two independent sets $S_{1}$ and
$S_{2}$. If both of these are independent sets are in $G_{1}$ (respectively,
$G_{2}$) then the edge is also present in $E(\mathsf{TS}_{k}(G_{1}))$
(respectively, $E(\mathsf{TS}_{k}(G_{2})$)). Otherwise, we may assume the edge
in $E(\mathsf{TS}_{k}(H(G_{1},G_{2})))$ has as endpoints an independent set
$S_{1}$ in $G_{1}$ (but not $G_{2}$) and an independent set $S_{2}$ in $G_{2}$
(but not $G_{1}$). We have $S_{1}\cap S_{2}\subset V(H)$ and since $S_{1}$ and
$S_{2}$ are adjacent $|S_{1}\cap S_{2}|=k-1$. It follows that $|S_{1}\cap
V(H)|=|S_{2}\cap V(H)|=k-1$ and so condition (1) is satisfied. We have shown
that each edge in $E(\mathsf{TS}_{k}(H(G_{1},G_{2})))$ is either in
$\mathsf{TS}_{k}(G_{1})$, $\mathsf{TS}_{k}(G_{2})$ or satisfies condition (1),
proving the proposition. ∎

For two $H$-consistent graphs $G_{1}$ and $G_{2}$, we say that
$H(G_{1},G_{2})$ is _$k$ -crossing free_ if there are no $k$-element
independent sets satisfying condition (1) of Proposition 12. For example, one
can verify that the graphs $H(G_{1},G_{2})$ in Figure 5 and $H(G_{4},G_{5})$
in Figure 7 are both $k$-crossing free, while the graph $H(G_{1},G_{3})$ in
Figure 6 is not. The following result will be used for constructing
$\mathsf{TS}_{k}$-trees/forests.

######  Corollary 13.

Let $k\geq 2$ and let $G_{1}$ and $G_{2}$ be two $H$-consistent graphs.
$H(G_{1},G_{2})$ is $k$-crossing free if and only if

$\mathsf{TS}_{k}(H(G_{1},G_{2}))=\mathsf{TS}_{k}(G_{1})\cup\mathsf{TS}_{k}(G_{2}).$
(2)

###### Proof.

If $H(G_{1},G_{2})$ is $k$-crossing free then (2) follows from Proposition 12.
Otherwise their exist $k$-element independent sets $S_{1}$ is in $G_{1}$ and
$S_{2}$ is in $G_{2}$ satisfying (1). This implies that
$\mathsf{TS}_{k}(H(G_{1},G_{2}))$ contains an additional edge between $S_{1}$
and $S_{2}$. ∎

Therefore, if $H(G_{1},G_{2})$ is $k$-crossing free and both
$\mathsf{TS}_{k}(G_{1})$ and $\mathsf{TS}_{k}(G_{2})$ are acyclic, then so is
$\mathsf{TS}_{k}(H(G_{1},G_{2}))$. The reason for allowing $H$ to be empty in
defining an $H$-join is that the corollary then applies to vertex disjoint
graphs $G_{1}$ and $G_{2}$, since in this case $H(G_{1},G_{2})$ is trivially
$k$-crossing free. Therefore, we can create reconfiguration graphs that are
forests from reconfiguration graphs that are trees (or forests).

The following result follows from the relationship between $H$-join and
$H$-decomposition discussed above.

######  Corollary 14.

If $G$ can be $H$-decomposed into $G_{1}$ and $G_{2}$ and $H(G_{1},G_{2})$ is
$k$-crossing free then $\mathsf{TS}_{k}(G)$ can be decomposed into
$\mathsf{TS}_{k}(G_{1})\cup\mathsf{TS}_{k}(G_{2})$.

##  4 Results on (Q2)

We currently have no general necessary and sufficient conditions for when a
forest $F$ is a $\mathsf{TS}_{k}$-graph, but we present some partial results
in this section. Firstly, we recall that in [1] it is shown that $P_{n}$ is a
$\mathsf{TS}_{k}$-graph for all $n\geq 1$ and $k\geq 2$ and $K_{1,n}$ is a
$\mathsf{TS}_{k}$-graph if and only if $n\leq k$. In this section, we show how
to construct acyclic $\mathsf{TS}_{k}$-graphs from graphs that have a single
edge using the join operation that was introduced in Section 3. We show that
it gives an alternate method of constructing $\mathsf{TS}_{k}$-graphs which
are paths and stars. Moreover, this operation can also be applied to construct
more general $\mathsf{TS}_{k}$ trees/forests, especially members of the
classes $k$-ary trees and $D_{r,n,s}$.

###  4.1 Paths and stars revisited

Using just the base graphs and the $H$-join operation defined in Section 3, we
can obtain large families of $\mathsf{TS}_{k}$ trees/forests. We begin with
paths. For any $k\geq 2$, let $J_{k}=\\{b_{1},\dots,b_{k}\\}$ be an
independent set of size $k$ and define the base graph
$B_{k}^{i}=B_{k}(J_{k-2}\cup\\{a_{i},a_{i+1},a_{i+2}\\},a_{i}a_{i+2})$ and let
$G_{2}=B_{k}^{i}$.

######  Proposition 15.

For $i\geq 2$, $G_{i}$ and $B_{k}^{i}$ are $H$-consistent with $H$ being the
independent set $J_{k-2}\cup\\{a_{i},a_{i+1}\\}$. Define
$G_{i+1}:=H(G_{i},B_{k}^{i})$. Then

$\mathsf{TS}_{k}(G_{i+1})=\mathsf{TS}_{k}(G_{i})\cup\mathsf{TS}_{k}(B_{k}^{i})\simeq
P_{i+1}.$

###### Proof.

We will prove by induction, for $i\geq 2$, that $\mathsf{TS}_{k}(G_{i})$ is
the path $P_{i}$ with vertices labelled
$J_{k-2}\cup\\{a_{j},a_{j+1}\\},j=1,\dots,i$. For the base case $i=2$, we
observe that indeed $\mathsf{TS}_{k}(B_{k}^{i})$ is a $P_{2}$ with vertices
labelled $J_{k-2}\cup\\{a_{1},a_{2}\\}$ and $J_{k-2}\cup\\{a_{2},a_{3}\\}$.

For the inductive step we observe that, for $i\geq 2$, $G_{i}$ and $B_{k}^{i}$
are $H$-consistent with $H$ the independent set
$J_{k-2}\cup\\{a_{i},a_{i+1}\\}$. To verify that $H(G_{i},B^{i}_{k})$ is
$k$-crossing free, note that the only independent set we need to consider in
$B_{k}^{i}$ is $J_{k-2}\cup\\{a_{i+1},a_{i+2}\\}$. In the path $P_{i}$ which
is $\mathsf{TS}_{k}(G_{i})$, the candidate independent sets are
$J_{k-2}\cup\\{a_{j},a_{j+1}\\},j=1,\dots,i$. Their intersection with
$B_{k}^{i}$ is $J_{k-2}$ which has cardinality $k-2$. Therefore condition (1)
of Proposition 12 is not satisfied, which indeed confirms that
$H(G_{i},B^{i}_{k})$ is $k$-crossing free. We define
$G_{i+1}:=H(G_{i},B_{k}^{i})$. By Corollary 13, $\mathsf{TS}_{k}(G_{i+1})$ is
the union of the above labelled $P_{i}$ with a $P_{2}$ with endpoints
$J_{k-2}\cup\\{a_{i},a_{i+1}\\}$ and $J_{k-2}\cup\\{a_{i+1},a_{i+2}\\}$. This
is the required $P_{i+1}$. ∎

An easy inductive argument based on the $H$-join in the proposition shows
that, for $i\geq 2$, $G_{i}$ is isomorphic to $\overline{P}_{n+1}\cup
J_{k-2}$, a result proved in Corollary 5(a) of [1]. (Observe that the vertex
$a_{i+1}$ in $G_{i}$ is adjacent to every $a_{j}$ for $1\leq j\leq i-1$.)

Next we consider graphs $G_{i}$ such that $\mathsf{TS}_{k}(G_{i})$ is the star
$K_{1,i}$. For $k\geq 2$ and $1\leq i\leq k$, let
$I_{k}=\\{a_{1},\dots,a_{k}\\}$ be an independent set of size $k$, define the
base graph $C_{k}^{i}=B_{k}(I_{k}+b_{i},a_{i}b_{i})$ and let
$G_{1}=C_{k}^{1}$.

######  Proposition 16.

For $k\geq 2$ and $1\leq i\leq k$, $G_{i}$ and $C_{k}^{i+1}$ are
$H$-consistent with $H$ being the independent set $I_{k}$. Define
$G_{i+1}:=H(G_{i},C_{k}^{i+1})$. Then

$\mathsf{TS}_{k}(G_{i+1})=\mathsf{TS}_{k}(G_{i})\cup\mathsf{TS}_{k}(C_{k}^{i+1})\simeq
K_{1,i+1}.$

###### Proof.

We will prove by induction, for $i\geq 1$, that $\mathsf{TS}_{k}(G_{i})$ is
the star $K_{1,i}$ with centre labelled $I_{k}$ and leaves labelled
$I_{k}+b_{j}-a_{j},j=1,\dots,i$. For the base case $i=1$, we observe that
indeed $\mathsf{TS}_{k}(C_{k}^{i})$ is a $K_{1,1}$ with centre labelled
$I_{k}$ and leaf labelled $I_{k}+b_{1}-a_{1}$.

For the inductive step we observe that, for $i\geq 1$, $G_{i}$ and
$C_{k}^{i+1}$ are $H$-consistent with $H$ the independent set $I_{k}$. To
verify that $H(G_{i},C_{k}^{i+1})$ is $k$-crossing free, note that the only
independent set we need to consider in $C_{k}^{i+1}$ is
$I_{k}+b_{i+1}-a_{i+1}$. In the above labelled $K_{1,i}$ which is
$\mathsf{TS}_{k}(G_{i})$, the candidate independent sets for condition (1) of
Proposition 12 are $I_{k}+b_{j}-a_{j},j=1,\dots,i$. Their intersection with
$I_{k}+b_{i+1}-a_{i+1}$ has cardinality $k-2$. Therefore, condition (1) is not
satisfied. We define $G_{i+1}:=H(G_{i},C_{k}^{i+1})$. By Corollary 13,
$\mathsf{TS}_{k}(G_{i+1})$ is the union of the above labelled $K_{1,i}$ and a
$K_{1,1}$ with centre also labelled $I_{k}$ and leaf labelled
$I_{k}+b_{i+1}-a_{i+1}$. This is the required $K_{1,i+1}$. ∎

###  4.2 $k$-ary trees

In this section, we show that for each $k\geq 2$, every $k$-ary tree is a
$\mathsf{TS}_{k+1}$-graph (Proposition 19). Next, we show that any tree $T$ is
an induced subgraph of some _$\mathsf{TS}_{2}$ -forest_ (Proposition 22).
Moreover, we state and prove the necessary and sufficient conditions for $T$
to be an induced subgraph of some _$\mathsf{TS}_{2}$ -tree_ (Proposition 23).
Additionally, when $T=K_{1,n}$, we describe a sufficient condition for $T$ to
be an induced subgraph of some $\mathsf{TS}_{k}$-tree (Proposition 24).

We begin by defining a canonical vertex labelling. In this subsection, for any
integer $n$, define $I_{n}:=\\{a_{1},\dots,a_{n}\\}$ and
$J_{n}:=\\{b_{1},\dots,b_{n}\\}$.

######  Definition 17.

Let $k\geq 2$ and $G$ be a graph for which $T:=\mathsf{TS}_{k+1}(G)$ is a
$k$-ary tree. We say that $G$ and $T$ are _canonically labelled_ if

  * (a)

the root of $T$ is labelled $I_{k+1}$,

  * (b)

the $d\leq k$ children of the root are labelled
$I_{k+1}-a_{i}+b_{i},i=1,\dots,d$,

  * (c)

the labels $b_{j},~{}j=d+1,\dots,k$ (if any) are not used, and

  * (d)

all other nodes in $T$ receive a label $S$ such that $|I_{k+1}\cap S|\leq
k-1$.

It is clear that labelling $K_{1,d},~{}d\leq k$ according to (a) and (b) with
root the centre of the star is a canonical labelling. In this subsection, we
will show that every $k$-ary tree has canonical labelling hence proving it is
a $\mathsf{TS}_{k+1}$-graph. First, we give a lemma that shows how to combine
canonically labelled $k$-ary trees to get a larger $k$-ary tree that is
canonically labelled.

######  Lemma 18.

For integers $k\geq 2$ and $1\leq i\leq d\leq k$, let $G_{i}$ be a graph for
which $\mathsf{TS}_{k+1}(G_{i})$ a canonically labelled $k$-ary tree. We can
construct a canonically labelled $k$-ary tree $T$ isomorphic to the tree
formed by choosing a new root and adjoining it to the root of each $T_{i}$.

###### Proof.

The proof consists of showing that we can make a series of $H$-joins between
the leaves of a canonically labelled $K_{1,d}$ and the roots of the
canonically labelled trees $T_{i},i=1,\dots,d$, after a suitable relabelling.
Suppose the root of $T_{i}$ has $n_{i}\leq k$ children. We relabel the
vertices in the underlying graphs as follows:

  * (i)

relabel vertices of the $G_{i}$ not in $I_{k+1}\cup J_{k}$ to be distinct, ie,
for $1\leq i\leq j\leq d$, we have $V(G_{i})\cap V(G_{j})\subseteq I_{k+1}\cup
J_{k}$,

  * (ii)

for $i=1,\ldots d,~{}j=1,\dots,n_{i}$ set $b_{j}\leftarrow b_{j}^{i}$, where
the $b_{j}^{i}$ were previously unused, and

  * (iii)

for $i=1,\ldots d$, set $a_{i}\leftarrow a_{k+1}$ and $a_{k+1}\leftarrow
b_{i}$.

By an abuse of notation, for simplicity we let for $i=1,\ldots,d$, $G_{i}$ and
$T_{i}$ refer to the relabelled graphs and trees. Item (i) ensures that the
only labels shared between two trees are in $I_{k+1}\cup J_{k}$, (ii) ensures
that all labels from $J_{k}$ in the $T_{i}$ are given unique labels to avoid
clashes, and (iii) gives the root of $T_{i}$ a correct label to be a child of
a new root labelled $I_{k}$. We note that after relabelling $b_{i}$ only
appears in $T_{i}$, $a_{i}$ does not appear in $T_{i}$ and the only labels
shared between the $T_{i}$ are in $I_{k}$. Furthermore all tree vertices have
unique labels.

Next take a canonically labelled graph $G^{0}$ such that
$\mathsf{TS}_{k+1}(G^{0})\simeq K_{1,d}$, with the centre of the star labelled
$I_{k+1}$. For $i=1,\ldots,d$, we claim that the $H$-join
$G^{i}:=H(G^{i-1},G_{i})$ is well-defined, $k$-crossing free, and
$\mathsf{TS}_{k+1}(G^{i})$ is canonically labelled. To see this, note at that
iteration $i$, $V(G^{i-1})\cap V(G_{i})=I_{k+1}-a_{i}+b_{i}$ which is the
label of the root of $T_{i}$ and a leaf of $\mathsf{TS}_{k+1}(G^{i-1})$.
Definition 17(d) implies that condition (1) of Proposition 12 is not
satisfied. Therefore by Corollary 13, $\mathsf{TS}_{k+1}(G^{i})$ is obtained
from $\mathsf{TS}_{k+1}(G^{i-1})$ by appending $T_{i}$ to the corresponding
leaf in $\mathsf{TS}_{k+1}(G^{i-1})$. The conditions of Definition 17 are
satisfied so $\mathsf{TS}_{k+1}(G^{i})$ is canonically labelled. At the end of
iteration $d$, $T:=\mathsf{TS}_{k+1}(G^{d})$ is the required tree. ∎

The construction described in the proof is illustrated in Figure 8.

Figure 8: Construction of $D_{2,3,2}$ from two $K_{1,2}$.

We may now prove the main result of this section.

######  Proposition 19.

For every $k$-ary tree $T$, there is a canonically labelled graph $G$ such
that $T\simeq\mathsf{TS}_{k+1}(G)$.

###### Proof.

Suppose that the root $r$ of $T$ has $d\leq k$ children. We prove the
proposition by induction on the height $t$ of $T$, which is the length of the
longest path to a leaf from the root. If $t=1$ then $T\simeq K_{1,d}$ and so
has a canonically representation as described following Definition 17.
Otherwise, by deleting $r$ we obtain $d$ subtrees $T_{i},i=1,\ldots,d$, which
are also $k$-ary trees, with height less than $t$. Therefore, by induction
each $T_{i}$ can be represented by a canonically labelled graph $G_{i}$. It
follows from Proposition 18 that we can perform $d$ $H$-joins to obtain a
canonically labelled graph $G$ for which $T\simeq\mathsf{TS}_{k+1}(G)$. ∎

As noted in Section 4 of [1], $K_{1,{k+1}}$ is an example of a $k$-ary tree
that is not an $\mathsf{TS}_{k}$-graph so the proposition is tight.
Nevertheless, if we add a sufficient number of isolated vertices to $K_{1,t}$,
for $t>k$, it becomes a $\mathsf{TS}_{2}$-graph—a result we will now prove in
general. We will need a special labelling of a tree that will be defined next.

######  Definition 20.

A tree $T$ is _well-labelled_ if

  * (a)

the root $r$ of $T$ is labelled $ab$,

  * (b)

the $d$ children of $r$ have roots labelled $r_{i}=bc_{i},i=1,\dots,d-1$ and
$r_{d}=ac_{d}$,

  * (c)

the only labels containing $a$ and $b$ are $ab,ac_{d},bc_{i},1\leq i\leq d-1$,
and

  * (d)

for $i=1,\ldots,d$ label $c_{i}$ only occurs in the subtree with root $r_{i}$.

We note that there is nothing special about the ordering of the subtrees of
$r$. The subtree rooted at $r_{i}$ can play the role of $r_{d}$ by relabelling
those two subtrees with the exchanges $a\leftrightarrow b$ and
$c_{i}\leftrightarrow c_{d}$, which leaves $T$ well-labelled. As an example,
for $d\geq 1$ we can well-label $K_{1,d}$ simply by using (a) and (b).
Consider the graph $G$ defined by $V(G)=\\{a,b\\}\cup\\{c_{i}:1\leq i\leq
d\\}$ and $E(G)=\\{ac_{i},c_{i}c_{d}:1\leq i\leq d-1\\}\cup\\{bc_{d}\\}$.
Furthermore let $J=\\{c_{i}c_{j}:1\leq i<j\leq d-1\\}$. Then it is not hard to
verify that $\mathsf{TS}_{2}(G)\simeq K_{1,d}+(d-1)(d-2)K_{1}$, where the
$K_{1,d}$ is well-labelled and the $K_{1}$ are labelled by the set $J$. This
motivates the following definition.

######  Definition 21.

A tree $T$ is _well-labelled by a labelled graph $G$_ if there is an integer
$n$ such that $\mathsf{TS}_{2}(G)\simeq T+nK_{1}$ and $T$ is well-labelled.

We now show the following general result.

######  Proposition 22.

For every tree $T$ there is a graph $G$ and integer $n$ such that $T$ is well-
labelled by $G$ and $\mathsf{TS}_{2}(G)\simeq T+nK_{1}$.

###### Proof.

The proof is by induction on $N$, the number of nodes in a given tree $T$. As
noted above, the proposition is true for all stars $K_{1,t}$ and these act as
base cases. For the inductive step, assume the proposition is true for all
trees on $N$ nodes and consider a tree $T$ with $N+1$ nodes. If $T$ is a star
we are done. Otherwise, let $r$ be the root of $T$ and assume $r$ has degree
$d$ with its children $r_{i}$ being roots of subtrees $T_{i},1,\dots,d$. We
may also assume that $T_{d}$ is a subtree of $T$ with height at least one. We
now construct two trees from $T$. The first, $T^{1}$ consists of $T$ with
subtree $T_{d}$ deleted and a pendant vertex added to its root $r$. The
second, $T^{2}$ consists of $T_{d}$ with a pendant vertex added to its root
$r_{d}$. By induction, there are integers $n_{1},n_{2}$ and graphs
$G^{1},G^{2}$ which well-label $T^{1}$ and $T^{2}$ such that
$\mathsf{TS}_{2}(G^{1})\simeq T^{1}+n_{1}K_{1}$ and
$\mathsf{TS}_{2}(G^{2})\simeq T^{2}+n_{2}K_{1}$. Apart from the vertex labels
used in Definition 20, we may assume the vertex labels in $G^{1}$ and $G^{2}$
are different.

We will show that $G^{1}$ and a relabelled $G^{2}$ can be $H$-joined and that
this will identify the pendant edges added to $T^{1}$ and $T^{2}$ to give us
back $T$. In $T^{1}$ we note that root $r$ is labelled $ab$, and by
relabelling subtree roots if necessary, that the added pendent vertex can be
labelled $ac_{d}$. In $T^{2}$ the root $r_{d}$ is also labelled $ab$ and we
can again assume the added pendant vertex is labelled $ac_{d}$. In $T^{2}$ we
interchange the labels $b\leftrightarrow c_{d}$ and set $c_{i}\leftarrow
c_{i}^{\prime},i=1,\ldots,d-1$, for labels $c_{i}^{\prime}$ that are unused in
either $T^{1}$ or $T^{2}$. Let $G^{3}$ and $T^{3}$ denote the relabelled
$G^{2}$ and $T^{2}$. Setting $H=\\{a,b,c_{d}\\}$, we have $V(G^{1})\cap
V(G^{3})=H$. $H$ induces the same subgraph, containing the single edge
$bc_{d}$, in both $G^{1}$ and $G^{3}$. $G^{1}$ and $G^{3}$ are $H$-consistent
and since $k=2$ and their vertex sets are otherwise disjoint, condition (1) of
Proposition 12 is not satisfied. Let $G^{4}=H(G^{1},G^{3})$. Applying
Corollary 13 we have that

$T^{4}:=\mathsf{TS}_{2}(G^{4})\simeq\mathsf{TS}_{2}(G^{1})\cup\mathsf{TS}_{2}(G^{3})\simeq\\{T^{1}+n_{1}K_{1}\\}\cup\\{T^{3}+n_{2}K_{1}\\}\simeq
T+(n_{1}+n_{2})K_{1}.$

is well-labelled by $G^{4}$. This proves the proposition. ∎

The proof of the proposition is illustrated in Figure 9.

Figure 9: Illustrating Proposition 22.

The proposition tells us that for every tree $T$ there is a graph $G$ for
which $\mathsf{TS}_{2}(G)$ is forest containing $T$ as an induced subgraph.
Therefore, there can be no forbidden induced subgraph characterization of
which _forests_ are $\mathsf{TS}_{2}$-graphs. However, this does not imply
that there can be no forbidden induced subgraph characterization of which
_trees_ are $\mathsf{TS}_{2}$-graphs. Indeed, in the next propositions, we
present some of such characterizations.

Figure 10: Taking $H$-join of two copies of $G^{2}$, where $H$ is the path
$adcb$, results a graph $G^{3}$ such that $\mathsf{TS}_{2}(G^{3})$ is
isomorphic to a $P_{7}$ with two pendant vertices attached to the midpoint of
the path.

######  Proposition 23.

Let $T$ be a tree. Then there exists a $\mathsf{TS}_{2}$-tree containing $T$
if and only if $T$ is a $3$-ary tree.

###### Proof.

  * ($\Leftarrow$)

In the proof of Proposition 22, we see that isolated vertices are only added
when the base case of a star appears as a subproblem. Therefore, it suffices
to consider only the case $T=K_{1,t},1\leq t\leq 4$. As we have noted, neither
$K_{1,3}$ nor $K_{1,4}$ are $\mathsf{TS}_{2}$-graphs. It is not hard to see
that there is a $G^{1}$ such that $\mathsf{TS}_{2}(G^{1})\simeq
K_{1,3}+K_{1}$. However, by adding an extra vertex to $G^{1}$, we can
construct a graph $G^{2}$ such that $\mathsf{TS}_{2}(G^{2})\simeq D_{1,3,2}$.
Furthermore, we can construct a graph $G^{3}$ by applying $H$-join to two
copies of $G^{2}$ with slightly different vertex-labellings such that
$\mathsf{TS}_{2}(G^{3})$ is isomorphic to a $P_{7}$ with two pendant vertices
attached to the midpoint of the path. (See Figure 10.) Thus, if follows that
when $T=K_{1,t},1\leq t\leq 4$, we can embed it as an induced subgraph of a
tree $T^{\prime}=\mathsf{TS}_{2}(G)$, for some graph $G$ (see Figure 10). Our
proof of the if direction is complete.

  * ($\Rightarrow$)

We show that if $T$ is a $k$-ary tree but not a $3$-ary tree for $k\geq 4$
then there does not exist any $\mathsf{TS}_{2}$-tree $T^{\prime}$ containing
$T$ (as an induced subgraph). (By definition, any $k$-ary tree is also a
$\ell$-ary tree for $\ell\geq k$.) Let $x$ be a vertex of $T$ whose degree is
at least five. (Since $T$ is a $k$-ary tree but not a $3$-ary tree, such a
vertex $x$ exists.)

Suppose to the contrary that $T^{\prime}$ exists, i.e., there exists a graph
$G^{\prime}$ such that $T^{\prime}\simeq\mathsf{TS}_{2}(G^{\prime})$ contains
$T$. Without loss of generality, assume that $x$ is labelled by $ab$, where
$\\{a,b\\}$ is a size-$2$ stable set of $G^{\prime}$. By the pigeonhole
principle, we may further assume that three neighbors $x_{1}$, $x_{2}$, and
$x_{3}$ of $x$ are labelled $ac$, $ad$, and $ae$, respectively. Since
$T^{\prime}$ is a tree, it follows that $cd$, $ce$, and $de$ are respectively
the labels of $y_{1}$, $y_{2}$, and $y_{3}$ where $y_{i}$ is not adjacent to
any of $\bigcup_{j}\\{x_{j}\\}+x+\bigcup_{j\neq i}\\{y_{j}\\}$ for $1\leq
i,j\leq 3$.

$ab$$ac$$ad$$ae$$cd$$ce$$de$$F$$a$$b$$c$$d$$e$$G$

Figure 11: The graphs $F$ and $G$ in the proof of Proposition 23.

It follows that $T^{\prime}$ contains the labelled graph $F\simeq
K_{1,3}+3K_{1}$ and therefore $G^{\prime}$ must contain the labelled graph
$G\simeq K_{1,3}+K_{1}$, both described in Figure 11, as an induced subgraph.

Since $T^{\prime}\simeq\mathsf{TS}_{2}(G^{\prime})$ is a tree and $G^{\prime}$
contains $G$, it follows that $G^{\prime}$ has exactly one non-trivial
component $C$ (having more than two vertices) and $C$ contains $G$, otherwise
$G^{\prime}$ must contain an induced $2K_{2}$ and by Proposition 2 its
$\mathsf{TS}_{2}$-graph is not a tree, a contradiction.

    * –

Case 1: $a\in V(C)$. By definition, the distance from $a$ to any of $b,c,d,e$
in $G^{\prime}$ must be at least two. If there is a path of length at least
two between $a$ and one of $c,d,e$ not passing through $b$, the graph
$G^{\prime}$ contains a $2K_{2}$, a contradiction. Thus, any path between $a$
and one of $c,d,e$ must go through $b$. Moreover, if there is a path of length
at least three between $a$ and $b$ not passing through any of $c,d,e$, again
the graph $G^{\prime}$ contains a $2K_{2}$, a contradiction. Since $a\in
V(C)$, it follows that $a$ and $b$ must have a common neighbor in
$G^{\prime}$, say $f$. Observe that for each $y\in V(C)-\\{a,b,c,d,e,f\\}$,
$y$ must be adjacent to $b$ in $G^{\prime}$, otherwise $G^{\prime}$ either
contains $2K_{2}$ or $D_{2,2,2}$ and again by Proposition 2 its
$\mathsf{TS}_{2}$-graph is not a tree, a contradiction. However, this implies
that $\mathsf{TS}_{2}(C)$ must be a forest and since $G^{\prime}$ has exactly
one non-trivial component $C$, we have $\mathsf{TS}_{2}(G^{\prime})$ is also a
forest, a contradiction.

    * –

Case 2: $a\notin V(C)$. In this case, there are two types of size-$2$ stable
sets of $G^{\prime}$: those containing $a$ and those do not. Since
$G^{\prime}$ contains $G$, each type has at least one member. Moreover, since
$a$ is isolated (the only non-trivial component is $C$ and $a$ is not in it),
no member from one type is adjacent to a member from another type in
$\mathsf{TS}_{2}(G^{\prime})$, which means $\mathsf{TS}_{2}(G^{\prime})$ is
indeed disconnected, a contradiction.

In the above cases, we proved that some contradiction must happen. Our proof
is complete.

∎

Indeed, for $K_{1,n}$, in general we have

######  Proposition 24.

There exists a $\mathsf{TS}_{k}$-ary tree $T$ containing $K_{1,n}$ if $n\leq
2k$.

###### Proof.

From either [1] or Proposition 16, the proposition holds for $n\leq k$.
(Indeed, in this case, $T=K_{1,n}$.) Thus, it suffices to consider $k+1\leq
n\leq 2k$. For each $i\in\\{1,\dots,n-k\\}$, let $A_{i}=\\{1,\dots,k\\}-i$.

Let $I_{k}=\\{a_{1},\dots,a_{k}\\}$ and $B_{n}=\\{b_{1},\dots,b_{n}\\}$. We
construct a graph $G^{0}$ such that $\mathsf{TS}_{k}(G^{0})\simeq
K_{1,n}+(n-k)(k-1)K_{1}$. Let $I_{k}=\\{a_{1},\dots,a_{k}\\}$ and
$B_{n}=\\{b_{1},\dots,b_{n}\\}$. Let $V(G)=I_{k}+B_{n}$. Vertices in $B_{n}$
form a graph $K_{n}-M$ where $M$ is the matching that contains $b_{i}b_{k+i}$
for $1\leq i\leq n-k$. Additionally, for each $i\in\\{1,\dots,k\\}$, we add an
edge in $G^{0}$ between $a_{i}$ and both $b_{i}$ and $b_{k+i}$. Observe that
$V(\mathsf{TS}_{k}(G^{0}))$ consists of $I_{k}$, the sets $I_{k}-a_{i}+b_{i}$
($1\leq i\leq k$), $I_{k}-a_{i}+b_{k+i}$ ($1\leq i\leq n-k$), and
$(I_{k}-a_{i}+b_{i})-a_{j}+b_{k+i}$ ($1\leq i\leq n-k$ and $j\in A_{i}$).
Moreover, one can verify that the independent sets
$(I_{k}-a_{i}+b_{i})-a_{j}+b_{k+i}$ are isolated in $\mathsf{TS}_{k}(G^{0})$
and the remaining independent sets form a $K_{1,n}$ in which $I_{k}$ is
adjacent to every other set. In short, $G^{0}$ is indeed our desired graph.

For each $i\in\\{1,\dots,n-k\\}$, we construct a graph $G^{i}$ whose
$\mathsf{TS}_{k}$-graph is a star $K_{1,k-1}$ as follows. Let
$V(G^{i})=(I_{k}-a_{i}+b_{i})+\bigcup_{j\in\\{1,\dots,k\\}-i}\\{c^{i}_{j}\\}$.
Vertices in $\bigcup_{j\in A_{i}}\\{c^{i}_{j}\\}$ form a clique in $G^{i}$ of
size $k-1$. We also add an edge in $G^{i}$ between $a_{j}$ and $c^{i}_{j}$ for
each $j\in A_{i}$. From either [1] or Proposition 16, one can verify that
$\mathsf{TS}_{k}(G^{i})\simeq K_{1,k-1}$ as desired. For each
$i\in\\{1,\dots,n-k\\}$ and $j\in A_{i}$, we construct a graph $G^{i}_{j}$
whose $\mathsf{TS}_{k}$-graph is a $K_{2}$ as follows. Let
$V(G^{i}_{j})=(I_{k}-a_{i}+b_{i})-a_{j}+b_{k+i}+c^{i}_{j}$. The only edge in
$G^{i}_{j}$ is the one joining $c^{i}_{j}$ and $b_{k+i}$. From either [1] or
Proposition 15, one can verify that $\mathsf{TS}_{k}(G^{i}_{j})\simeq K_{2}$
as desired.

Figure 12: Construction of a graph $G$ such that $\mathsf{TS}_{4}(G)$ is a
tree containing $K_{1,8}$. Vertices of $G$ in the yellow box form a clique
having all dashed edges removed. The red induced subgraph of $G$ forms a graph
$G^{0}$ whose $\mathsf{TS}_{4}(G^{0})\simeq K_{1,8}+12K_{1}$.

Now, we construct a graph $G$ whose $\mathsf{TS}_{k}$-graph is a tree
containing $K_{1,n}$ as follows. For convenience, we assume that for each
$i\in\\{1,\dots,n-k\\}$ the set $A_{i}=\\{1,\dots,k\\}-i$ can be enumerated as
$\\{j_{1},\dots,j_{k-1}\\}$. We define $\mathcal{K}^{i}_{j_{0}}=G^{i}$ and
$\mathcal{K}^{i}_{j_{p}}=H_{j_{p}}(\mathcal{K}^{i}_{j_{p-1}},G^{i}_{j_{p}})$
for $j_{p}\in A_{i}$ where $H_{j_{p}}$ is the stable set
$(I_{k}-a_{i}+b_{i})-a_{j_{p}}+c^{i}_{j_{p}}$ for $p\in\\{1,\dots,k-1\\}$.
Observe that the graphs $\mathcal{K}^{i}_{j_{p-1}}$ and $G^{i}_{j_{p}}$ are
$H_{j_{p}}$-consistent, which implies that $\mathcal{K}^{i}_{j_{p}}$ are well-
defined. Moreover, one can also directly verify that the sets
$(I_{k}-a_{i}+b_{i})-a_{j}+c^{i}_{j}$ and
$(I_{k}-a_{i^{\prime}}+b_{i^{\prime}})-a_{j^{\prime}}+c^{i^{\prime}}_{j^{\prime}}$
always differ in at least two members, which means the condition (1) of
Proposition 12 is not satisfied. In short, for each $i\in\\{1,\dots,n-k\\}$,
we obtain the graph $\mathcal{K}^{i}_{j_{k-1}}$ whose $\mathsf{TS}_{k}$-graph
is isomorphic to the one obtained from $K_{1,k-1}$ by replacing each edge with
a $P_{3}$. Next, we define $\mathcal{K}^{0}=G^{0}$ and
$\mathcal{K}^{i}=H^{i}(\mathcal{K}^{i-1},G^{i})$ where $i\in\\{1,\dots,n-k\\}$
and $H^{i}$ is the subgraph induced by $(I_{k}-a_{i}+b_{i})+b_{k+i}$. Observe
that the graphs $\mathcal{K}^{i}$ are well-defined because $\mathcal{K}^{i-1}$
and $G^{i}$ are $H^{i}$-consistent. Moreover, we have $I_{k}$ and each
$(I_{k}-a_{i}+b_{i})-a_{j}+c^{i}_{j}$ for $1\leq i\leq n-k$ and $j\in A_{i}$
always differ in at least two members. It follows that the condition (1) of
Proposition 12 is not satisfied. In short, we finally obtain the graph
$G=\mathcal{K}^{n-k}$ whose $\mathsf{TS}_{k}$-graph is indeed a tree
containing $K_{1,n}$ as desired. ∎

Unfortunately, we have not been able to show whether the reverse statement of
Proposition 24 also holds. We conclude this section with the following open
problems:

######  Problem 25.

For every $k\geq 3$ and tree $T$, is there a graph $G$ such that
$\mathsf{TS}_{k}(G)$ is a forest containing $T$ as an induced subgraph?

######  Problem 26.

For every $k\geq 3$ and $(k+1)$-ary tree $T$, is there a graph $G$ such that
$\mathsf{TS}_{k}(G)$ is a tree containing $T$ as an induced subgraph?

######  Problem 27.

Does there exist a $\mathsf{TS}_{k}$-tree $T$ containing $K_{1,n}$ for $n>2k$?

###  4.3 $D_{r,n,s}$

We now consider graphs in the $D_{r,n,s}$ family for whose
$\mathsf{TS}_{k}$-graphs are trees and show how they can be constructed by the
$H$-join operation. We remark that when $n=1$, $D_{r,n,s}$ is nothing but a
star $K_{1,r+s}$ and this case was considered in [1] and revisited in
Proposition 16. Furthermore, it follows from Proposition 19 that for $n,k\geq
2$ and $1\leq r\leq s\leq k-1$, $D_{r,n,s}$ is a $k$-ary tree and so by
Proposition 19 it is a $\mathsf{TS}_{k}$-graph. The reverse statement does not
hold in general: there exists a $\mathsf{TS}_{k}$-graph $D_{r,n,s}$ even when
$s\geq k$. For example, one of such graphs, as already proved in [1], is
$D_{1,3,2}$ ($r=1$, $s=k=2$, and $n=3$). (See also Figure 1.) Indeed, as we
will see in Proposition 29, it is the unique $\mathsf{TS}_{2}$-graph among all
trees $D_{1,n,2}$ for $n\geq 1$. Additionally, for the sake of completeness,
we will also show in Proposition 30 that the reverse statement indeed holds
when $n=2$.

We are now characterizing which $D_{1,n,2}$-graphs are
$\mathsf{TS}_{2}$-graphs and show that this property is non-hereditary for
this simple class of trees. We then consider the $D_{r,2,s}$-graphs
characterizing those that are $\mathsf{TS}_{k}$-graphs.

Assume for some $G$, $\mathsf{TS}_{2}(G)$ is a forest containing a $K_{1,3}$.
There are four stable sets in $G$ corresponding to the vertices of the
$K_{1,3}$. There are two ways of labelling the $K_{1,3}$ but in each case
there are five vertices, say $a,\dots,e$, of $G$ involved. Up to permutations
of the labels, the corresponding stable sets in $G$ are either
$\\{ab,ac,bd,ae\\}$ or $\\{ab,ac,ad,ae\\}$. Using these definitions we have
the following lemma.

######  Lemma 28.

Let $H$ be the subgraph of $G$ induced by $a,b,\dots,e$. The edges of $H$ are

  * (a)

$ad,de,eb,bc,cd$, if the $K_{1,3}$ is labelled $\\{ab,ac,bd,ae\\}$, or

  * (b)

$bc,bd,be$ if the $K_{1,3}$ is labelled $\\{ab,ac,ad,ae\\}$.

Figure 13: If $\mathsf{TS}_{2}(G)$ is a forest containing a $K_{1,3}$ then $G$
must contain one of the induced subgraphs $H$.

###### Proof.

  * (a)

This labelling of $K_{1,3}$ immediately gives edges $ad,bc,be$ and non-edges
$ab,ac,ae,bd$. That leaves three edges of $H$ to be decided:

    * (i)

$ce$ must be a non-edge else there is an edge $ae,ac$ in the $K_{1,3}$.

    * (ii)

$cd$ is an edge else there is a cycle $ab,bd,cd,ad$ in $\mathsf{TS}_{2}(G)$,
so it is not a tree.

    * (iii)

$de$ is an edge else there is a cycle $de,bd,ab,ae$ in $\mathsf{TS}_{2}(G)$.

Note that $ce$ must also be a vertex in $\mathsf{TS}_{2}(G)$.

  * (b)

This labelling of $K_{1,3}$ immediately gives edges $bc,bd,be$ and non-edges
$ab,ac,ad,ae$. There are no other edges in $H$ as $c,d,e$ form a stable set.
This implies that $\mathsf{TS}_{2}(G)$ must also contain vertices $cd,ce$ and
$de$.

∎

Using the lemma we show that precisely one of the $D_{1,n,2}$-graphs is a
$\mathsf{TS}_{2}$-graph, incidentally proving the non-hereditary property
mentioned above for this class of graphs.

######  Proposition 29.

$D_{1,n,2}$ is a $\mathsf{TS}_{2}$-graph if and only if $n=3$.

###### Proof.

We first consider $1\leq n\leq 3$ and show that $D_{1,3,2}$ is a
$\mathsf{TS}_{2}$-graph while $D_{1,1,2}=K_{1,3}$ and $D_{1,2,2}$ are not. (We
note that the results for the first two graphs have also been proved in [1].)
According to Lemma 28, if $D_{1,n,2}$ is a $\mathsf{TS}_{2}$-graph of some
graph $G$, the unique star $K_{1,3}$ in $D_{1,n,2}$ can be labelled in one of
two ways. However, we may immediately eliminate the possibility of the
labelling in Lemma 28(b). This is because, as pointed out in the proof, there
must be additional vertices in $D_{1,n,2}=\mathsf{TS}_{2}(G)$ labelled $cd,ce$
and $de$ which are non-adjacent since $c,d,e$ form a stable set in $G$. This
implies that $n\geq 6$. So we may assume that if $D_{1,n,2}$ is a
$\mathsf{TS}_{2}$-graph, the $K_{1,3}$ must be labelled as in Lemma 28(a) with
corresponding induced subgraph $H$ of $D_{1,n,2}$. From the proof of Lemma
28(a) there must be an additional vertex $ce$ in $D_{1,n,2}$ however this
cannot be adjacent to any of the other four vertices. This implies that $n\geq
3$ and so neither $D_{1,1,2}$ nor $D_{1,2,2}$ can be $\mathsf{TS}_{2}$-graphs.
However we may extend $H$ to $G$ by adding a vertex $f$ adjacent to all
vertices except $e$, as illustrated in Figure 1. This introduces the new
stable set $ef$ which is adjacent to both $ae$ and $ce$. Therefore $D_{1,3,2}$
is isomorphic to $\mathsf{TS}_{2}(G)$. We note that $G$ is the unique graph
(up to label permutations) for which this is true, due to the uniqueness of
the labelling of $K_{1,3}$.

It remains to consider $n\geq 4$ and show that $D_{1,n,2}$ is not a
$\mathsf{TS}_{2}$-graph. Suppose to the contrary that there exists a graph $G$
such that $D_{1,n,2}=\mathsf{TS}_{2}(G)$. Again, $D_{1,n,2}$ must contain a
copy of $K_{1,3}$ with exactly two ways of labelling (up to label
permutations) by size-$2$ independent sets of $G$.

  * •

Case 1: $K_{1,3}$ is labelled $\\{ab,ac,bd,ae\\}$. Since $ac$ and $ae$ are not
adjacent, $ce$ must be a vertex of $D_{1,n,2}=\mathsf{TS}_{2}(G)$. We consider
the following cases:

    * –

Case 1.1: the distance between $ce$ and any vertex of $\\{ac,bd,ae\\}$ is at
least three. Since the roles of $c$ and $e$ are equal, we assume without loss
of generality that $ce$ is adjacent to some vertex $cf$. Observe that $a$ and
$f$ are not adjacent in $G$, otherwise $ac$ and $cf$ are adjacent, which means
the distance between $ac$ and $ce$ is two, a contradiction. Since $ce$ and
$cf$ are adjacent, so are $ae$ and $af$. Moreover, $bf$ must be a vertex,
otherwise there is an edge between $ab$ and $af$ in
$D_{1,n,2}=\mathsf{TS}_{2}(G)$ which creates a $C_{3}$ having $\\{ab,ae,af\\}$
as its vertex-set, a contradiction. Since $ab$ and $ac$ are adjacent, so are
$cf$ and $bf$. Now, $df$ must be a vertex, otherwise $bd$ and $bf$ are
adjacent which contradicts $D_{1,n,2}=\mathsf{TS}_{2}(G)$. Since $ab$ and $bd$
are adjacent, so are $af$ and $df$. From the proof of Lemma 28(a)(ii) $c$ and
$d$ are adjacent in $G$, so $df$ and $cf$ are adjacent, which again
contradicts $D_{1,n,2}=\mathsf{TS}_{2}(G)$.

    * –

Case 1.2: the distance between $ce$ and one of $\\{ac,bd,ae\\}$ is exactly
two. Observe that $bd$ and $ce$ has no common neighbor, otherwise that
neighbor must be labelled as one of $\\{bc,be,dc,de\\}$: the first two can be
ignored because $ab$ and $ac$ (resp., $ab$ and $ae$) are adjacent, the last
two can be ignored because $ab$ and $bd$ are adjacent. Again, since the roles
of $c$ and $e$ are equal, we assume without loss of generality that $ae$ and
$ce$ has a common neighbor $ef$. Since $n\geq 4$, $ce$ must have another
neighbor which is different from $ef$, which can be either $cg$ or $eg$ for
some vertex $g$ of $G$.

      * *

If it is $cg$ then $ag$ must be a vertex, otherwise $cg$ and $ac$ must be
adjacent, which creates a $C_{6}$ whose vertex-set is
$\\{ac,ab,ae,ef,ce,cg\\}$, a contradiction. Since $ce$ and $cg$ are adjacent,
so are $ae$ and $ag$, which contradicts $D_{1,n,2}=\mathsf{TS}_{2}(G)$.

      * *

If it is $eg$ then $ag$ must be a vertex, otherwise $eg$ and $ae$ must be
adjacent, which creates a $C_{4}$ whose vertex-set is $\\{ae,ef,ce,eg\\}$, a
contradiction. Since $ce$ and $eg$ are adjacent, so are $ag$ and $ac$, which
contradicts $D_{1,n,2}=\mathsf{TS}_{2}(G)$.

  * •

Case 2: $K_{1,3}$ is labelled $\\{ab,ac,ad,ae\\}$. As before, $cd$, $ce$, and
$de$ must be vertices in $D_{1,n,2}$. Without loss of generality, since the
roles of $c,d,e$ are equal, we may assume that only $ae$ is adjacent to
another vertex of $D_{1,n,2}$. As shown in the proof of Lemma 28(b),
$D_{1,n,2}$ must also contain vertices $cd,ce,de$. Let $P$ be the path between
$ae$ and $cd$. Since the roles of $c$ and $d$ are equal, we can assume without
loss of generality that $cd$ is adjacent to a vertex $cf$ in $P$. Observe that
if $af$ is not a vertex $ac$ and $cf$ are adjacent contradicting the choice of
$ae$. So $af$ is a vertex and since $cd$ and $cf$ are adjacent so are $ad$ and
$af$, which contradicts $D_{1,n,2}=\mathsf{TS}_{2}(G)$.

∎

We remark that if we add a vertex $g$ to $G$ in Figure 1 joining it to all
vertices except $d$ the corresponding $\mathsf{TS}_{2}$-graph is obtained by
adding the edge between $bd$ and $dg$ to $\mathsf{TS}_{2}(G)$. Note that this
tree is not in the class $D_{r,n,s}$.

In the next proposition we consider two arbitrary stars whose centers are
connected by an edge.

######  Proposition 30.

$D_{r,2,s}$ ($1\leq r\leq s$) is a $\mathsf{TS}_{k}$-graph if and only if
$s\leq k-1$.

###### Proof.

  * ($\Leftarrow$)

It follows directly from Proposition 19.

  * ($\Rightarrow$)

Suppose that $D_{r,2,s}$ ($r\leq s$) is obtained from $P_{2}=p_{1}p_{2}$ by
attaching $r$ leaves $u_{1},\dots,u_{r}$ at $p_{1}$ and $s$ leaves
$v_{1},\dots,v_{s}$ at $p_{2}$ for some $s\geq k$. We show that this graph is
not a $\mathsf{TS}_{k}$-graph for any fixed $k\geq 2$. Suppose to the contrary
that there exists a graph $G$ such that $D_{r,2,s}\simeq\mathsf{TS}_{k}(G)$,
i.e., there exists a bijective mapping $f:V(D_{r,2,s})\to
V(\mathsf{TS}_{k}(G))$ such that $uv\in E(D_{r,2,s})$ if and only if
$f(u)f(v)\in E(\mathsf{TS}_{k}(G))$. Without loss of generality, let
$f(p_{2})=I=\\{a_{1},\dots,a_{k}\\}$, where $I$ is a size-$k$ independent set
of $G$. Since $p_{2}$ has $s+1$ neighbors, from the pigeonhole principle, it
follows that there must be some $i\in\\{1,\dots,k\\}$ such that
$f(u)=I-a_{i}+x$ and $f(v)=I-a_{i}+y$, where $u,v\in N(p_{2})$. Observe that
$J=(I-a_{i}-a_{j})+x+y\notin\\{f(p_{2}),f(u),f(v)\\}$ must be a size-$k$
independent set of $G$, where $j\in\\{1,\dots,k\\}-i$ and therefore there
exists $z\in V(D_{r,2,s})-\\{p_{2},u,v\\}$ such that $f(z)=J$. We consider the
following cases:

    * –

Neither $u$ nor $v$ is $p_{1}$. In this case, we must have $z\notin N(p_{2})$,
otherwise it must be adjacent to $p_{2}$, but then $f(z)=J$ and $f(p_{2})=I$
must be adjacent in $\mathsf{TS}_{k}(G)$, a contradiction. It follows that
$z\in N(p_{1})-p_{2}$ and thus $f(p_{1})$ must be in
$\\{I-a_{i}+x,I-a_{i}+y,I-a_{j}+x,I-a_{j}+y\\}$. Since neither $u$ nor $v$ is
$p_{1}$, the first two can be ignored. Now, if $f(p_{1})=I-a_{j}+x$, the
vertices $x$ and $a_{j}$ must be adjacent in $G$, which contradicts the fact
that $f(u)\in\mathsf{TS}_{k}(G)$. A similar contradiction can be derived for
the case $f(p_{1})=I-a_{j}+y$. Thus, $f(p_{1})$ cannot be defined.

    * –

$u$ is $p_{1}$. Again, $z\notin N(p_{2})$. Thus, $z\in N(p_{1})-p_{2}$, which
implies that $y$ and $a_{j}$ must be adjacent in $G$. This contradicts
$f(v)\in\mathsf{TS}_{k}(G)$. Thus, $f(z)$ cannot be defined.

In both cases, we showed that some contradiction must occur. Our proof is
complete.

∎

##  5 Conclusions

In this paper, we considered two token sliding problems for trees and forests.
The two questions studied seem remarkably complicated, even for this simple
class of graphs. For the first question, finding necessary and sufficient
conditions on $G$ for $\mathsf{TS}_{k}(G)$ to be a forest, we could only get a
complete solution for $k=2,3$. For the second question, finding necessary and
sufficient conditions for a tree or forest to be a token sliding graph, we
could get more general results. Nevertheless, as noted in Section 4 several
interesting important questions remain. We expect the join and decomposition
operations introduced there will be of use for similar questions for more
general graphs.

## Acknowledgments

Avis’ research is partially supported by the Japan Society for the Promotion
of Science (JSPS) KAKENHI Grants JP18H05291, JP20H00579, and JP20H05965 (AFSA)
and Hoang’s research by JP20H05964 (AFSA).

## References

  * [1] David Avis and Duc A. Hoang.  On reconfiguration graphs of independent sets under token sliding.  arXiv preprint, 2022.  arXiv:2203.16861.
  * [2] Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, and Sebastian Siebertz.  A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems.  arXiv preprint, 2022.  arXiv:2204.10526.
  * [3] Reinhard Diestel.  Graph Theory, volume 173 of Graduate Texts in Mathematics.  Springer, 5th edition, 2017.
  * [4] Robert A. Hearn and Erik D. Demaine.  PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation.  Theoretical Computer Science, 343(1-2):72–96, 2005.
  * [5] Ruy Fabila Monroy, David Flores-Peñaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, and David R. Wood.  Token graphs.  Graphs and Combinatorics, 28(3):365–380, 2012.
  * [6] C.M. Mynhardt and S. Nasserasr.  Reconfiguration of colourings and dominating sets in graphs.  In Fan Chung, Ron Graham, Frederick Hoffman, Ronald C. Mullin, Leslie Hogben, and Douglas B. West, editors, 50 years of Combinatorics, Graph Theory, and Computing, pages 171–191. CRC Press, 1st edition, 2019.
  * [7] Naomi Nishimura.  Introduction to reconfiguration.  Algorithms, 11(4):52, 2018.
  * [8] Jan van den Heuvel.  The complexity of change.  In Surveys in Combinatorics, volume 409 of London Mathematical Society Lecture Note Series, pages 127–160. Cambridge University Press, 2013.