NICER | 17 | 3200360140 | 59177.14 | 6892 | 2-10* | 5.31e-08 | 4.93e-11 | 3 | 0.72 | 784
NICER | 18 | 3200360141 | 59179.66 | 2447 | 1-10 | 4.88e-08 | 3.36e-11 | 3 | 1.92 | 884
NICER | 19 | 3200360142 | 59180.04 | 3683 | 2-10 | 4.87e-08 | 3.13e-11 | 3 | 1.61 | 784
NICER | 20 | 3200360143 | 59181.46 | 5783 | 2-10 | 4.32e-08 | 2.26e-11 | 3 | 1.82 | 784
NICER | 21 | 3200360144 | 59182.24 | 5438 | 2-10 | 4.17e-08 | 2.42e-11 | 3 | 1.83 | 784
NICER | 22 | 3200360145 | 59183.27 | 1718 | 1-10 | 3.82e-08 | 3.52e-11 | 3 | 1.52 | 884
NICER | 23 | 3200360147 | 59186.05 | 2559 | 1-10 | 3.30e-08 | 2.65e-11 | 3 | 1.44 | 884
NICER | 24 | 3200360148 | 59187.08 | 2518 | 1-10 | 3.07e-08 | 1.66e-11 | 3 | 1.42 | 884
NICER | 25 | 3200360149 | 59188.11 | 3086 | 1-10 | 2.86e-08 | 2.21e-11 | 3 | 1.48 | 884
NICER | 26 | 3200360150 | 59189.08 | 1786 | 1-10 | 2.76e-08 | 2.86e-11 | 3 | 1.24 | 884
NICER | 27 | 3200360151 | 59190.05 | 3234 | 1-10 | 2.48e-08 | 1.98e-11 | 3 | 1.44 | 884
NICER | 28 | 3200360152 | 59191.47 | 3560 | 1-10 | 2.39e-08 | 1.85e-11 | 3 | 1.37 | 884
NICER | 29 | 3200360153 | 59192.37 | 1662 | 1-10 | 1.96e-08 | 2.42e-11 | 3 | 1.12 | 884
NICER | 30 | 3200360154 | 59193.09 | 1445 | 1-10 | 2.05e-08 | 2.66e-11 | 3 | 1.10 | 884
NICER | 31 | 3200360155 | 59194.18 | 852 | 1-10 | 1.83e-08 | 3.15e-11 | 3 | 1.07 | 884
NICER | 32 | 3200360156 | 59206.93 | 949 | 1-10 | 2.22e-09 | 9.68e-12 | 3 | 1.04 | 884
NICER | 33 | 3200360157 | 59206.99 | 1635 | 1-10 | 1.94e-09 | 6.91e-12 | 3 | 1.05 | 884
NICER | 34 | 3200360158 | 59208.8 | 901 | 1-10 | 1.26e-09 | 7.12e-12 | 3 | 0.97 | 884
NICER | 35 | 3200360159 | 59209.17 | 1948 | 1-10 | 8.81e-10 | 4.44e-12 | 3 | 1.09 | 884
NICER | 36 | 3200360160 | 59210.85 | 1609 | 1-10 | 4.71e-10 | 3.08e-12 | 3 | 1.17 | 884
NICER | 37 | 3200360161 | 59213.3 | 378 | 1-10 | 1.71e-10 | 5.97e-12 | 3 | 0.97 | 884
NICER | 38 | 3200360162 | 59214.27 | 7263 | 1-10 | 2.57e-10 | 1.12e-12 | 3 | 1.03 | 884
NICER | 39 | 3200360163 | 59214.99 | 3617 | 1-10 | 1.86e-10 | 1.28e-12 | 3 | 1.08 | 884
NICER | 40 | 3200360164 | 59216.34 | 12302 | 1-10 | 2.16e-10 | 7.70e-13 | 3 | 1.05 | 884
NICER | 41 | 3200360165 | 59217.37 | 6975 | 1-10 | 2.60e-10 | 1.15e-12 | 3 | 1.06 | 884
NICER | 42 | 3200360166 | 59218.21 | 3513 | 1-10 | 1.96e-10 | 1.38e-12 | 3 | 1.08 | 884
NICER | 43 | 3200360167 | 59219.0 | 6149 | 1-10 | 3.67e-07 | 3.61e-05 | 3 | 1.09 | 884
NICER | 44 | 3200360168 | 59220.08 | 1881 | 1-10 | 1.27e-10 | 1.41e-12 | 1 | 1.23 | 890
NICER | 45 | 3200360169 | 59221.05 | 5712 | 1-10 | 1.23e-10 | 9.17e-13 | 1 | 1.09 | 890
NICER | 46 | 3200360170 | 59222.21 | 2535 | 1-10 | 1.63e-10 | 1.36e-12 | 1 | 1.05 | 890
NICER | 47 | 3200360171 | 59223.05 | 3151 | 1-10 | 1.34e-10 | 1.12e-12 | 1 | 1.03 | 890
NICER | 48 | 3200360172 | 59224.02 | 2134 | 1-10 | 1.12e-10 | 1.27e-12 | 1 | 0.94 | 890
NICER | 49 | 3200360173 | 59225.05 | 3180 | 1-10 | 1.56e-10 | 1.32e-12 | 1 | 1.09 | 890
NICER | 50 | 3200360174 | 59226.21 | 2187 | 1-10 | 2.05e-10 | 1.71e-12 | 0 | 1.17 | 893
NICER | 51 | 3200360175 | 59227.05 | 3519 | 1-10 | 1.07e-10 | 9.54e-13 | 1 | 1.00 | 890
NICER | 52 | 3200360176 | 59228.73 | 885 | 1-10 | 1.33e-10 | 2.29e-12 | 1 | 1.00 | 890
NICER | 53 | 3200360177 | 59229.31 | 4755 | 1-10 | 1.10e-10 | 9.29e-13 | 1 | 1.10 | 890
NICER | 54 | 3200360178 | 59230.73 | 1380 | 1-10 | 1.11e-10 | 1.58e-12 | 1 | 0.89 | 890
NICER | 55 | 3200360179 | 59231.31 | 5382 | 1-10 | 9.47e-11 | 7.24e-13 | 1 | 1.15 | 890
NICER | 56 | 3200360180 | 59232.54 | 2473 | 1-10 | 1.13e-10 | 1.16e-12 | 1 | 0.98 | 890
NICER | 57 | 3200360181 | 59233.06 | 4095 | 1-10 | 1.08e-10 | 8.86e-13 | 1 | 1.09 | 890

Table 4: Continuation of Table 3. * The exceptionally low $\chi^{2}_{\nu}$ value is caused by the short, $15$ second exposure and resulting over-fitting of the spectrum. Observatory | Obs. # | ObsID/mode | MJD | Exposure | Fitted band | Flux | Error | Gaussians | $\chi^{2}_{\nu}$ | DOF
---|---|---|---|---|---|---|---|---|---|---
[second] | [keV] | [0.5-10 keV; erg/s/cm2]
NICER | 58 | 3200360182 | 59234.28 | 2712 | 1-10 | 1.01e-10 | 1.15e-12 | 1 | 1.05 | 890
NICER | 59 | 3200360183 | 59234.99 | 8227 | 1-10 | 9.52e-11 | 6.94e-13 | 1 | 1.04 | 890
NICER | 60 | 3200360184 | 59236.03 | 4121 | 1-10 | 8.12e-11 | 7.73e-13 | 1 | 1.00 | 890
NICER | 61 | 3200360185 | 59237.38 | 2583 | 1-10 | 7.09e-11 | 9.16e-13 | 1 | 1.02 | 890
NICER | 62 | 3200360186 | 59238.09 | 3829 | 1-10 | 9.06e-11 | 8.76e-13 | 1 | 1.14 | 890
NICER | 63 | 3200360187 | 59240.67 | 703 | 1-10 | 7.09e-11 | 2.12e-12 | 1 | 0.81 | 890
NICER | 64 | 3200360188 | 59241.13 | 4247 | 1-10 | 8.09e-11 | 7.93e-13 | 1 | 1.07 | 890
NICER | 65 | 3200360189 | 59242.29 | 2938 | 1-10 | 7.87e-11 | 9.01e-13 | 1 | 1.08 | 890
NICER | 66 | 3200360190 | 59243.0 | 4707 | 1-10 | 9.09e-11 | 7.60e-13 | 1 | 1.03 | 890
NICER | 67 | 3200360191 | 59246.23 | 1420 | 1-10 | 8.77e-11 | 1.45e-12 | 1 | 1.01 | 890
NICER | 68 | 3200360192 | 59248.03 | 847 | 1-10 | 2.00e-10 | 3.74e-12 | 1 | 1.07 | 890
NICER | 69 | 3200360193 | 59250.03 | 989 | 1-10 | 1.39e-10 | 2.17e-12 | 1 | 1.05 | 890
NICER | 70 | 3200360194 | 59251.97 | 1410 | 1-10 | 3.44e-10 | 4.18e-12 | 3 | 1.27 | 884
NICER | 71 | 3200360195 | 59252.16 | 1176 | 1-10 | 2.50e-10 | 2.85e-12 | 3 | 1.05 | 884
NICER | 72 | 3200360196 | 59253.59 | 6149 | 1-10 | 6.96e-10 | 1.88e-12 | 3 | 0.98 | 884
NICER | 73 | 3200360197 | 59254.04 | 1441 | 1-10 | 9.24e-10 | 4.85e-12 | 3 | 1.04 | 884
NICER | 74 | 3200360198 | 59256.04 | 1413 | 1-10 | 9.65e-10 | 5.18e-12 | 3 | 1.03 | 884
NICER | 75 | 3200360199 | 59257.07 | 1496 | 1-10 | 8.99e-10 | 4.61e-12 | 3 | 1.15 | 884
NICER | 76 | 3200360201 | 59259.72 | 1402 | 1-10 | 1.00e-09 | 5.52e-12 | 3 | 1.09 | 884
NICER | 77 | 3200360202 | 59262.17 | 695 | 1-10 | 6.67e-10 | 6.05e-12 | 3 | 1.07 | 884
NICER | 78 | 3200360203 | 59263.01 | 1144 | 1-10 | 4.67e-10 | 3.46e-12 | 3 | 1.19 | 884
NICER | 79 | 3200360204 | 59264.37 | 298 | 1-10 | 6.03e-10 | 8.10e-12 | 0 | 1.07 | 893
Swift | 1 | 00035066077/pc | 59162.31 | 2964 | 1-10 | 1.25e-08 | 1.86e-10 | 0 | 1.03 | 811
Swift | 2 | 00035066078/wt | 59174.07 | 344 | 1-10 | 6.43e-08 | 6.42e-10 | 0 | 1.36 | 863
Swift | 3 | 00035066080/wt | 59180.84 | 908 | 1-10 | 5.11e-08 | 2.61e-10 | 0 | 1.16 | 891
Swift | 4 | 00089186001/wt | 59186.8 | 1380 | 1-10 | 3.06e-08 | 1.46e-10 | 0 | 1.29 | 894
Swift | 5 | 00013945001/wt | 59202.61 | 1053 | 1-10 | 5.12e-09 | 3.32e-11 | 0 | 1.13 | 884
Swift | 6 | 00013945002/wt | 59205.87 | 554 | 1-10 | 2.72e-09 | 2.78e-11 | 0 | 1.06 | 814
Swift | 7 | 00013945003/wt | 59208.53 | 898 | 1-10 | 1.15e-09 | 1.55e-11 | 0 | 1.08 | 774
Swift | 8 | 00013945004/wt | 59214.7 | 903 | 1-10 | 1.64e-10 | 7.34e-12 | 0 | 0.81 | 623
Swift | 9 | 00013945005/wt | 59217.15 | 1053 | 1-10 | 2.22e-10 | 7.15e-12 | 0 | 0.97 | 649
Swift | 10 | 00013945006/wt | 59220.33 | 1098 | 1-10 | 2.10e-10 | 1.14e-11 | 0 | 0.93 | 606
Swift | 11 | 00013945007/wt | 59223.33 | 953 | 1-10 | 1.11e-10 | 5.41e-12 | 0 | 0.84 | 549
Swift | 12 | 00013945008/wt | 59226.65 | 354 | 1-10 | 6.77e-10 | 6.86e-11 | 0 | 0.63 | 324
Swift | 13 | 00013945010/wt | 59232.76 | 1038 | 1-10 | 4.52e-11 | 1.88e-12 | 0 | 0.81 | 431
Swift | 14 | 00013945011/wt | 59235.01 | 1099 | 1-10 | 6.45e-11 | 3.27e-12 | 0 | 0.74 | 512
Swift | 15 | 00013945012/wt | 59237.06 | 1043 | 1-10 | 4.51e-11 | 3.72e-12 | 0 | 0.74 | 436
Swift | 16 | 00013945013/wt | 59241.58 | 1128 | 1-10 | 4.54e-11 | 2.21e-12 | 0 | 0.67 | 489
Swift | 17 | 00013945014/wt | 59244.31 | 963 | 1-10 | 2.75e-10 | 8.65e-11 | 0 | 0.63 | 559
Swift | 18 | 00013945015/wt | 59247.02 | 668 | 1-10 | 7.28e-11 | 4.50e-12 | 0 | 0.78 | 396
Swift | 19 | 00013945016/wt | 59250.61 | 1048 | 1-10 | 2.16e-10 | 2.28e-11 | 0 | 0.86 | 614
Swift | 20 | 00013945017/wt | 59253.4 | 858 | 1-10 | 2.65e-10 | 8.46e-12 | 0 | 0.97 | 647
Swift | 21 | 00013945018/wt | 59256.26 | 917 | 1-10 | 7.79e-10 | 1.21e-11 | 0 | 1.05 | 751
Swift | 22 | 00013945019/wt | 59259.24 | 933 | 1-10 | 1.01e-09 | 1.15e-11 | 0 | 0.84 | 772
Swift | 23 | 00013945020/wt | 59263.43 | 790 | 1-10 | 3.58e-10 | 8.73e-12 | 0 | 0.99 | 645
Swift | 24 | 00013945021/wt | 59269.2 | 950 | 1-10 | 5.18e-10 | 9.78e-12 | 0 | 1.08 | 699
Swift | 25 | 00013945022/wt | 59272.58 | 908 | 1-10 | 5.59e-10 | 9.99e-12 | 0 | 0.92 | 739
Swift | 26 | 00013945023/wt | 59275.84 | 883 | 1-10 | 8.46e-10 | 1.18e-11 | 0 | 0.97 | 749
Swift | 27 | 00013945024/wt | 59278.95 | 1043 | 1-10 | 5.36e-10 | 7.67e-12 | 0 | 1.00 | 714
Swift | 28 | 00013945025/wt | 59281.35 | 15 | 1-10 | 1.00e-08 | 2.93e-09 | 0 | 0.11* | 248
Swift | 29 | 00013945026/wt | 59284.93 | 928 | 1-10 | 3.56e-10 | 1.01e-11 | 0 | 0.99 | 699
Swift | 30 | 00013945027/pc | 59292.1 | 350 | 1-10 | 1.34e-09 | 6.90e-11 | 0 | 0.80 | 345
Swift | 31 | 00013945027/wt | 59292.1 | 608 | 1-10 | 1.09e-09 | 2.12e-11 | 0 | 1.04 | 730
Swift | 32 | 00013945028/pc | 59298.27 | 567 | 1-10 | 9.52e-10 | 4.72e-11 | 0 | 0.67 | 380

Figure 11: Light curves of the parameters fitted to the Swift spectra of 1A
0535+262 up to MJD 59300. In order from top to bottom, the panels show: the
X-ray flux, absorption column; black body temperature and normalisation; power
law index and normalisation; and $\chi^{2}_{\nu}$ of the fit. Several
parameters show larger error bars, often cased by a relatively short exposure
(cf. MJD 59281.35). All parameter values are available in the machine-readable
parameter file. Figure 12: Light curves of the parameters fitted to all NICER
spectra of 1A 0535+262. In order from top to bottom, the panels show: the
X-ray flux, absorption column; black body temperature and normalisation; power
law index, exponential cut-off energy, and normalisation; Gaussian energy,
width, and normalisation of all three lines (in black, red, and blue); and
$\chi^{2}_{\nu}$ of the fit. Several parameters show larger error bars, often
cased by a relatively short exposure At the highest fluxes, early in the
outburst, instrumental residuals increase $\chi^{2}_{\nu}$ systematically. At
lower flux (i.e. after MJD 59200), several parameters are poorly constrained:
especially the Gaussian line parameters and cutoff energy show significant
uncertainties. All parameter values are available in the machine-readable
parameter file. Figure 13: The ratio between the NICER spectra measured for
ObsID 3200360135, modelled with standard and observation-specific response and
background files. Figure 14: top panels: posterior distributions of the offset
$\log\xi$ and slope $\beta$ for a single MCMC run. Bottom panels:
distributions of the 16th and 84th percentile (blue), as well as the mean
(black), of the offset and slope after 500 MCMC runs.


11institutetext: Graduate School of Informatics, Kyoto University, Japan
22institutetext: School of Computer Science, McGill University, Canada
22email<EMAIL_ADDRESS>
22email<EMAIL_ADDRESS>
# On Reconfiguration Graphs of Independent Sets under Token Sliding

David Avis 1122 Duc A. Hoang 11

###### Abstract

An independent set of a graph $G$ is a vertex subset $I$ such that there is no
edge joining any two vertices in $I$. Imagine that a token is placed on each
vertex of an independent set of $G$. The $\mathsf{TS}$\- ($\mathsf{TS}_{k}$-)
reconfiguration graph of $G$ takes all non-empty independent sets (of size
$k$) as its nodes, where $k$ is some given positive integer. Two nodes are
adjacent if one can be obtained from the other by sliding a token on some
vertex to one of its unoccupied neighbors. This paper focuses on the structure
and realizability of these reconfiguration graphs. More precisely, we study
two main questions for a given graph $G$: (1) Whether the
$\mathsf{TS}_{k}$-reconfiguration graph of $G$ belongs to some graph class
$\mathcal{G}$ (including complete graphs, paths, cycles, complete bipartite
graphs, connected split graphs, maximal outerplanar graphs, and complete
graphs minus one edge) and (2) If $G$ satisfies some property $\mathcal{P}$
(including $s$-partitedness, planarity, Eulerianity, girth, and the clique’s
size), whether the corresponding $\mathsf{TS}$\- ($\mathsf{TS}_{k}$-)
reconfiguration graph of $G$ also satisfies $\mathcal{P}$, and vice versa.
Additionally, we give a decomposition result for splitting a
$\mathsf{TS}_{k}$-reconfiguration graph into smaller pieces.

###### Keywords:

Token sliding Reconfiguration graph Independent set Structure Realizability
Geometric graph.

##  1 Introduction

Reconfiguration problems arise when we want to study the relationship between
solutions of some given computational problem (called a source problem) such
as Satisfiability, Independent Set, Dominating Set, Vertex-Coloring, and so
on. The main goal of reconfiguration problems is to study the so-called
reconfiguration graph—a graph whose nodes are solutions and their adjacency
can be defined via some given reconfiguration rule. A typical example is the
well-known classic Rubik’s cube puzzle, where each configuration of the
Rubik’s cube corresponds to a solution, and two configurations (solutions) are
adjacent if one can be obtained from the other by rotating a face of the cube
by either $90$, $180$, or $270$ degrees. The question is whether there exists
a path from an arbitrary node to the one where each face has only one color.
Reconfiguration graphs have been studied in the literature from three major
viewpoints: structural properties (connectivity, Hamiltonicity, planarity, and
so on), realizability (which graph can be realized as a certain type of
reconfiguration graph), and algorithmic properties (whether certain questions,
such as finding a (shortest) path between two given nodes, can be answered
efficiently, and if so, design an algorithm to do it). For an overview of this
research area, readers are referred to the surveys [11, 16, 17].

One of the classic reconfiguration rules is the so-called Token Sliding
($\mathsf{TS}$). Any vertex subset of a graph $G$ can be seen as a set of
tokens placed on some vertices of $G$. Under $\mathsf{TS}$, a token on some
vertex $v$ can only be moved to one of $v$’s unoccupied adjacent vertices. Two
vertex subsets are adjacent under $\mathsf{TS}$ if one can be obtained from
the other via a single $\mathsf{TS}$-move. The token graph $F_{k}(G)$ [15] is
a reconfiguration graph whose nodes are size-$k$ vertex subsets of $G$ and
edges are defined under $\mathsf{TS}$. The study of $F_{k}(G)$ dates back to
the 1990s, when Alavi, Behzad, Erdős, and Lick [1] considered several basic
structural properties (e.g., regularity, bipartitedness, Eulerianity, etc.) of
$F_{2}(G)$ (which they called the double vertex graph).  Other well-known
reconfiguration rules are Token Jumping ($\mathsf{TJ}$) and Token
Addition/Removal ($\mathsf{TAR}$), which respectively involve moving a token
to any unoccupied vertex and adding/removing a single token to/from some
unoccupied/occupied vertex.

In this paper, we take Independent Set as the source problem and consider two
types of reconfiguration graphs whose edges are defined under $\mathsf{TS}$:
the $\mathsf{TS}_{k}$-reconfiguration graphs, for some given positive integer
$k$, whose nodes are size-$k$ independent sets of $G$ (i.e., vertex subsets
whose members are pairwise non-adjacent, also called stable sets) and the
$\mathsf{TS}$-reconfiguration graphs whose nodes are independent sets of
arbitrary size. We denote these graphs by $\mathsf{TS}_{k}(G)$ and
$\mathsf{TS}(G)$, respectively. (Similar definitions hold for $\mathsf{TJ}$.)
In particular, each $\mathsf{TS}_{k}(G)$ is an induced subgraph of
$\mathsf{TS}(G)$ and also a subgraph of $F_{k}(G)$.

The focus of this paper is on purely graph theoretic properties of
$\mathsf{TS}(G)$ and $\mathsf{TS}_{k}(G)$ as opposed to algorithmic
properties, which have been well-studied in the literature. In particular, the
tractability/intractability of whether there is a path between two given nodes
and several subsequent questions (e.g., if yes, whether a shortest one can be
found efficiently; whether the statement holds for any pair of nodes; and so
on) have been well-investigated for several graphs $G$. Readers are referred
to [17, Sections 4–5] for a quick summary of the recent results. In
particular, some structural properties regarding the connectivity and diameter
of $\mathsf{TS}_{k}(G)$ can be derived from many of these algorithmic results
[4, 5, 6, 8, 10, 12, 13]. (See Appendix 0.A.) On the other hand, the
realizability and structural properties of
$\mathsf{TS}(G)$/$\mathsf{TS}_{k}(G)$ have not yet been systematically studied
and we initiate this study here. More precisely, given a graph $G$, we provide
some initial results regarding two main questions: (1) Whether the
$\mathsf{TS}_{k}$-reconfiguration graph of $G$ belongs to some graph class
$\mathcal{G}$ and (2) If $G$ satisfies some property $\mathcal{P}$, whether
$\mathsf{TS}(G)$/$\mathsf{TS}_{k}(G)$ also satisfies $\mathcal{P}$ too, and
vice versa.

The outline of this paper is as follows. In Section 2, we give an example of
$\mathsf{TS}_{k}$-reconfiguration graphs used as a model for a problem in
computational geometry. In Section 3, we define some terminology and notation
that are used throughout this paper. In Section 4, for different graph classes
$\mathcal{G}$ (including complete graphs, paths, cycles, complete bipartite
graphs, connected split graphs, maximal outerplanar graphs, and complete
graphs minus one edge), we study whether there is a graph $G$ whose
$\mathsf{TS}_{k}$-reconfiguration graph belongs to $\mathcal{G}$. (See Table
1.) In Section 5, for different graph properties $\mathcal{P}$ (including
$s$-partitedness, planarity, Eulerianity, girth, and the clique’s size), we
focus on answering the following question: if a graph $G$ satisfies
$\mathcal{P}$, whether $\mathsf{TS}(G)$ ($\mathsf{TS}_{k}(G)$) does too, and
vice versa. (See Table 2.) In Section 6, we present a simple way of
decomposing $\mathsf{TS}_{k}(G)$ into $\mathsf{TS}_{k}$-reconfiguration graphs
of $G$’s subgraphs, provided that $G$ contains certain structure. Finally, in
Section 7, we summarize our results and propose some problems and directions
for future study.

##  2 A Geometrical Example

Figure 1: Point set $P$ with its line segments. A triangulation is shown by
the black lines.

$13$$46$$25$$36$$15$$56$$24$$35$ Figure 2: Edge intersection graph $G$. Each
number $ab$ inside a node represents an intersecting line segment of $P$. The
stable set corresponds to the triangulation in Figure 2 is shaded grey.

Figure 3: Triangulations of $P$. The red edges correspond to edge flips. In
$T_{1}$ (the triangulation in Figure 2) the three possible edge flips,
corresponding to token slides 15-46, 56-13 and 36-25 in $G$ (Figure 2), are
shown in blue.

In this section we present an example of a $\mathsf{TS}$-reconfiguration graph
arising from a well studied problem in computational geometry: triangulations
on a set of planar points. For terminology and notation related to
computational geometry which are not defined here, readers are referred to
[18].

Given a set $P$ of $n$ points in the plane, no three collinear and no four co-
circular. Two line segments are intersecting if they cross each other at an
interior point of each segment, and non-intersecting otherwise. A
triangulation of $P$ is any maximal set of non-intersecting segments. It is
well known that all triangulations have the same number of edges. The edge
intersection graph $G$ of $P$ is the graph whose vertices $V$ are the line
segments with endpoints in $P$ that intersect at least one other line segment.
Let $L$ be the remaining set of line segments defined by $P$. Note that any
edge on the convex hull of $P$ is in $L$ and there may be other such line
segments. In Figure 2 we give a set of $6$ points and show the $15$ segments
they define. A triangulation is shown by the solid black lines. The set $L$
consists of the seven segments $\\{12,14,16,23,26,34,45\\}$. We see that the
edges $\\{16,26,45\\}$ are internal to the convex hull. Two vertices in $G$
are connected by an edge if their corresponding line segments intersect. In
Figure 2 we give the intersection graph $G$ for the example, which has
$\alpha(G)=4$. The triangulation appears in $G$ as the stable set
$\\{15,35,36,56\\}$.

Each vertex of $\mathsf{TS}_{k}(G)$ corresponds to a set of $k$ pairwise non-
intersecting line segments. Figure 3 shows $\mathsf{TS}_{4}(G)$ for the
example, where the independent sets are shown as their corresponding
triangulations. The top left triangulation corresponds to the stable set
$\\{15,35,36,56\\}$. By token sliding we see that it is adjacent in
$\mathsf{TS}_{4}(G)$ to stable sets $\\{15,35,25,56\\}$, $\\{46,35,36,56\\}$
and $\\{15,35,36,13\\}$ corresponding to the triangulations $T_{2}$, $T_{6}$
and $T_{7}$. Geometrically we see that token sliding corresponds to flipping
the diagonal of a convex quadrilateral in the triangulation. Lawson [14]
showed that flipping well-chosen intersecting diagonals of convex
quadrilaterals will lead to the unique Delaunay triangulation, which proves
that $\mathsf{TS}_{\alpha(G)}(G)$ is connected. This result was generalized by
Bern and Eppstein [3] to the case where a non-intersecting set of the line
segments can be specified and the triangulations are constrained to include
these segments. In this case we add these constrained segments and any
segments that intersect them to $L$. They were able to show that the
corresponding constrained Delaunay triangulation could be obtained after at
most $O(n^{2})$ diagonal flips, giving a corresponding bound on the diameter
of $\mathsf{TS}_{\alpha(G)}(G)$. Similar results on connectivity and diameter
for some other graph classes are given in the Appendix 0.A.

##  3 Preliminaries

For terminology and notation not defined here, readers are referred to [9].
Let $G$ be a simple, undirected graph. We use $V(G)$ and $E(G)$, respectively,
to denote its vertex-set and edge-set. For two sets $I,J$, we sometimes use
$I-J$ and $I+J$ to indicate $I\setminus J$ and $I\cup J$, respectively.
Additionally, if $J=\\{u\\}$, we sometimes write $I-u$ and $I+u$ instead of
$I-\\{u\\}$ and $I+\\{u\\}$, respectively. The symmetric difference of $I$ and
$J$, denoted by $I\Delta J$, is simply the set $(I-J)+(J-I)$. The neighborhood
of a vertex $v$ in $G$, denoted by $N_{G}(v)$, is the set $\\{w\in V(G):vw\in
E(G)\\}$. The closed neighborhood of $v$ in $G$, denoted by $N_{G}[v]$, is
simply the set $N_{G}(v)+v$. Similarly, for a vertex subset $I\subseteq V(G)$,
its neighborhood $N_{G}(I)$ and closed neighborhood $N_{G}[I]$ are
respectively $\bigcup_{v\in I}N_{G}(v)$ and $N_{G}(I)+I$. The degree of a
vertex $v$ in $G$, denoted by $\deg_{G}(v)$, is $|N_{G}(v)|$. For a vertex
subset $I$, we denote by $G[I]$ the subgraph of $G$ induced by vertices in
$I$. An independent set (or stable set) of $G$ is a vertex subset $I$ such
that for any $u,v\in I$, we have $uv\notin E(G)$. On the other hand, a clique
of $G$ is a vertex subset $K$ such that for any $u,v\in K$, we have $uv\in
E(G)$. The complement $\overline{G}$ of $G$ is the graph whose vertices are
$V(G)$ and two vertices are adjacent in $\overline{G}$ if they are not
adjacent in $G$. We denote by $\alpha(G)$ and $\omega(G)$ the maximum size of
an independent set and a clique of $G$, respectively. The girth of $G$,
denoted by $\text{girth}(G)$, is the smallest size of a cycle in $G$. In case
$G$ has no cycles, we define $\text{girth}(G)=\infty$, and say that it has
infinite girth, and otherwise $G$ has finite girth. Two graphs $G_{1}$ and
$G_{2}$ are isomorphic if there exists a bijection $f:V(G_{1})\to V(G_{2})$
such that $uv\in E(G_{1})$ if and only if $f(u)f(v)\in E(G_{2})$. For
isomorphic graphs $G_{1}$ and $G_{2}$, we write $G_{1}\simeq G_{2}$ or
$G_{1}\simeq_{f}G_{2}$ to emphasize that their isomorphism can be verified by
the bijection $f$. A graph is $H$-free if it has no graph $H$ as an induced
subgraph.

We respectively denote by $K_{n}$, $P_{n}$, and $C_{n}$ a complete graph, a
path, and a cycle on $n$ vertices. The graph $K_{3}\simeq C_{3}$ is also
called a triangle. $K_{n}-e$ is the graph obtained from $K_{n}$ by removing
exactly one edge. We denote by $K_{m,n}$ a complete bipartite graph whose
partite sets are of sizes $m$ and $n$, for some positive integers $m\leq n$.
The graph $K_{1,n}$ is also called a star. $G$ is a split graph if $V(G)$ can
be partitioned into two sets $K$ and $S$, called a $KS$-partition of $V(G)$,
such that $K$ is a clique and $S$ is a stable set of $G$. A $K$-max
$KS$-partition of $V(G)$ is a $KS$-partition where the size of $K$ is maximum,
that is, $|K|=\omega(G)$ (e.g., see [7]). It is well-known that any split
graph $G$ has a unique $K$-max $KS$-partition of $V(G)$. In this paper, we
assume that for any split graph $G$, the $K$-max $KS$-partition of $V(G)$ is
always given, and to emphasize this assumption, we write $G=(K\cup
S,E)_{\text{$K$-max}}$.

For a graph $G$ and a positive integer $k$, the
$\mathsf{TS}_{k}$-reconfiguration graph of $G$, denoted by
$\mathsf{TS}_{k}(G)$, takes all size-$k$ independent sets of $G$ as its nodes.
Similarly, the $\mathsf{TS}$-reconfiguration graph of $G$ takes all
independent sets of $G$ as its nodes. Two nodes (independent sets) $I$ and $J$
are adjacent in either $\mathsf{TS}(G)$ or $\mathsf{TS}_{k}(G)$ if there exist
$u,v\in V(G)$ such that $I-J=\\{u\\}$, $J-I=\\{v\\}$, and $uv\in E(G)$.
Naturally, we call a graph $F$ a $\mathsf{TS}_{k}$-reconfiguration graph if
there exists a graph $G$ such that $F\simeq\mathsf{TS}_{k}(G)$ or more
precisely $F\simeq_{f}\mathsf{TS}_{k}(G)$ where $f$ is some bijection that can
be used for verifying their isomorphism. One can think of $f$ as a way to
label vertices of $F$ by size-$k$ independent sets of $G$.

##  4 Graphs That Are (Not) $\mathsf{TS}_{k}$-Reconfiguration Graphs

In this section, we study the realizability of
$\mathsf{TS}_{k}$-reconfiguration graphs. It is trivial that any graph $G$ is
also a $\mathsf{TS}_{1}$-reconfiguration graph, since
$G\simeq\mathsf{TS}_{1}(G)$. Therefore, in this section, we always assume
$k\geq 2$.

For a graph $G$, let $L_{k}(G)$ be the graph whose nodes are size-$k$ cliques
of $G$ and two nodes are adjacent if they have exactly $k-1$ vertices in
common. In particular, $L_{2}(G)$ is also known as the line graph of $G$. The
following lemma describes a relationship between $L_{k}(G)$ and the
$\mathsf{TS}_{k}$-reconfiguration graph of its complement $\overline{G}$.
Figure 4 illustrates this relationship for $k=2$.

###### Lemma 1

Given a graph $G$. Then, $\mathsf{TS}_{k}(\overline{G})$ is a subgraph of
$L_{k}(G)$. Moreover, $L_{k}(G)\simeq\mathsf{TS}_{k}(\overline{G})$ if and
only if $G$ is $K_{k+1}$-free.

###### Proof

By definition, for any $I=\\{a_{1},\dots,a_{k}\\}\in
V(\mathsf{TS}_{k}(\overline{G}))$, we have $a_{i}a_{j}\notin E(\overline{G})$
and therefore $a_{i}a_{j}\in E(G)$ for $1\leq i<j\leq k$, which implies that
$a_{1}\dots a_{k}\in V(L_{k}(G))$. As a result, the mapping
$f:V(\mathsf{TS}_{k}(\overline{G}))\to V(L_{k}(G))$ defined by
$f(\\{a_{1},\dots,a_{k}\\})=a_{1}\dots a_{k}$ is bijective. Moreover, if
$I=\\{a_{1},\dots,a_{k}\\}$ and $J=\\{a_{1}^{\prime},\dots,a_{k}^{\prime}\\}$
are adjacent in $\mathsf{TS}_{k}(\overline{G})$, we must have $|I\cap J|=k-1$,
and therefore $a_{1}\dots a_{k}$ and $a_{1}^{\prime}\dots a_{k}^{\prime}$ are
adjacent in $L_{k}(G)$. Therefore, $\mathsf{TS}_{k}(\overline{G})$ is a
subgraph of $L_{k}(G)$.

We now claim that $\mathsf{TS}_{k}(\overline{G})\simeq_{f}L_{k}(G)$ if and
only if $G$ is $K_{k+1}$-free.

  * $(\Rightarrow)$

Suppose to the contrary that $\mathsf{TS}_{k}(\overline{G})\simeq_{f}L_{k}(G)$
and $G$ has a $K_{k+1}=a_{1}\dots a_{k}a_{k+1}$. Thus,
$I=\\{a_{1},\dots,a_{k-1},\allowbreak a_{k}\\}$ and
$J=\\{a_{1},\dots,a_{k-1},a_{k+1}\\}$ are vertices of
$\mathsf{TS}_{k}(\overline{G})$. Since $a_{1}\dots a_{k-1}a_{k}$ and
$a_{1}\dots a_{k-1}a_{k+1}$ are adjacent in $L_{k}(G)$, we have $IJ\in
E(\mathsf{TS}_{k}(\overline{G}))$. It follows that $a_{k}a_{k+1}\in
E(\overline{G})$, which means $a_{k}a_{k+1}\notin E(G)$, which is a
contradiction. Therefore, $G$ is $K_{k+1}$-free.

  * $(\Leftarrow)$

Suppose that $G$ is $K_{k+1}$-free. It suffices to show that $IJ\in
E(\mathsf{TS}_{k}(\overline{G}))$ if and only if $f(I)f(J)\in E(L_{k}(G))$.
Since $\mathsf{TS}_{k}(\overline{G})$ is a subgraph of $L_{k}(G)$, the only-if
direction is clear. We now show the if direction. Without loss of generality,
let $a_{1}\dots a_{k-1}a_{k}$ and $a_{1}\dots a_{k-1}a_{k+1}$ be two adjacent
vertices in $L_{k}(G)$. Since $G$ is $K_{k+1}$-free, $a_{k}a_{k+1}\notin
E(G)$, which means $a_{k}a_{k+1}\in E(\overline{G})$ and therefore $IJ\in
E(\mathsf{TS}_{k}(\overline{G}))$, where $I=f^{-1}(a_{1}\dots a_{k-1}a_{k})$
and $J=f^{-1}(a_{1}\dots a_{k-1}a_{k+1})$.

∎

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$G$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$\overline{G}$$12$$15$$23$$25$$34$$45$$L_{2}(G)$$12$$15$$23$$25$$34$$45$$\mathsf{TS}_{2}(\overline{G})$
Figure 4: A graph $G$, its complement $\overline{G}$, its line graph
$L_{2}(G)$, and the graph $\mathsf{TS}_{2}(\overline{G})$. Each number of the
form $ab$ inside a node represents a vertex subset $\\{v_{a},v_{b}\\}$ which
forms both a node in $L_{2}(G)$ and an independent set of $\overline{G}$.

In Figure 4 we see that $G$ contains a triangle and indeed $L_{2}(G)$ is not
isomorphic to $\mathsf{TS}_{2}(\overline{G})$. If we break the triangle by
deleting the edge $v_{1}v_{2}$ this corresponds to deleting the vertex $12$ in
$L_{2}(G)$ and $\mathsf{TS}_{2}(\overline{G})$ along with adding the edge from
$15$ to $25$. We now see that $L_{2}(G)\simeq\mathsf{TS}_{2}(\overline{G})$.

In the rest of this section, for some graph class $\mathcal{G}$, we answer the
following question: Does there exist a graph $G$ such that
$\mathsf{TS}_{k}(G)\in\mathcal{G}$, for some $k\geq 2$? Our results are
described in Table 1.

Table 1: Does $G$ such that $\mathsf{TS}_{k}(G)\in\mathcal{G}$ exist ($k\geq 2$)? $\mathcal{G}$ | Does $G$ exist? | Ref.
---|---|---
$K_{n}$ | yes | Cor. 1
$|V(G)|=n+k-1$
$|E(G)|=n(n-1)/2$
$P_{n}$ | yes | Cor. 2
$|V(G)|=(n+1)+k-2=n+k-1$
$|E(G)|=n(n-1)/2$
$C_{n}$ | yes
$|V(G)|=n+k-2$
$|E(G)|=n(n-3)/2$
$K_{m,n}$ ($m\leq n$) | yes, iff $m=1$ and $n\leq k$ or $m=n=2$ | Prop. 4
$|V(G)|=n+k$ or $|V(G)|=k+2$
$|E(G)|=n(n+1)/2$ or $|E(G)|=2$
connected $F=(K\cup S,E)_{\text{$K$-max}}$ |  | yes, iff $|N_{F}(v)\cap S|\leq k-1$ and $|N_{F}(w)|=1$
---
for every $v\in K$ and $w\in S$
Prop. 5
$|V(G)|=|K|+|S|+k-1$
| $|E(G)|=\binom{|K|}{2}+\binom{|S|}{2}+\sum_{v\in K}|N_{F}(v)\cap S|+$
---
$+\sum_{\begin{subarray}{c}v\in K\\\ |N_{F}(v)\cap S|\neq
0\end{subarray}}(|K|-1)$
maximal outerplanar | yes, iff $n\leq 3$ | Prop. 6
$K_{n}-e$

We now prove some useful observations.

###### Proposition 1

If $H$ is an induced subgraph of $G$, then $\mathsf{TS}_{k}(H)$ is an induced
subgraph of $\mathsf{TS}_{k}(G)$. The reverse does not hold for any $k\geq 2$.

###### Proof

Suppose that there exist $I,J\in V(\mathsf{TS}_{k}(H))$ such that $IJ\in
E(\mathsf{TS}_{k}(G))$. Since $IJ\in E(\mathsf{TS}_{k}(G))$, there exists
$u,v\in V(G)$ such that $I-J=\\{u\\}$, $J-I=\\{v\\}$, and $uv\in E(G)$. Since
$I,J\in V(\mathsf{TS}_{k}(H))$, it follows that $u,v\in V(H)$. As $H$ is an
induced subgraph of $G$ and $uv\in E(G)$, we must have $uv\in E(H)$.
Therefore, $IJ\in E(\mathsf{TS}_{k}(H))$.

Now, if $H=C_{2k}$ and $G=K_{1,k+1}$, one can readily verify that
$\mathsf{TS}_{k}(H)$ is an induced subgraph of $\mathsf{TS}_{k}(G)$ but $H$ is
clearly not an induced subgraph of $G$. ∎

###### Proposition 2

Given a graph $H$, let $G=\mathsf{TS}_{\alpha(H)}(H)$. Then, for every
$k\geq\alpha(H)$, $G$ is a $\mathsf{TS}_{k}$-reconfiguration graph. More
precisely, there exists a graph $H^{\prime}$ having $|V(H)|+k-\alpha(H)$
vertices and $|E(H)|$ edges such that $G\simeq\mathsf{TS}_{k}(H^{\prime})$.

###### Proof

Let $H^{\prime}$ be the graph obtained by adding a set $X$ of $(k-\alpha(H))$
new vertices to $H$. Any size-$k$ independent set in $H^{\prime}$ is a
disjoint union of $X$ and a maximum independent set in $H$. Then,
$G=\mathsf{TS}_{\alpha(H)}(H)\simeq\mathsf{TS}_{k}(H^{\prime})$. ∎

A direct consequence of Proposition 2 when $H=K_{n}$ is as follows.

###### Corollary 1

$K_{n}$ is a $\mathsf{TS}_{k}$-reconfiguration graph, for any integers $k\geq
2$ and $n\geq 2$.

A direct consequence of Lemma 1 and Proposition 2 is as follows.

###### Corollary 2

  * (a)

$P_{n}$ is a $\mathsf{TS}_{k}$-reconfiguration graph, for any integers $k\geq
2$ and $n\geq 1$.

  * (b)

$C_{n}$ is a $\mathsf{TS}_{k}$-reconfiguration graph, for any integers $k\geq
2$ and $n\geq 3$.

###### Proof

  * (a)

Since $P_{n}$ is triangle-free, from Lemma 1 we have

$P_{n}\simeq L_{2}(P_{n+1})\simeq\mathsf{TS}_{2}(\overline{P_{n+1}}).$

This settles the case $k=2$. For $k=3$, note that
$\alpha(\overline{P_{n+1}})=\omega(P_{n+1})=2$, therefore it follows from
Proposition 2 that $P_{n}$ is a $\mathsf{TS}_{k}$-reconfiguration graph for
every $k\geq 2$.

  * (b)

Since $C_{3}\simeq K_{3}$, Corollary 1 settles the case $n=3$. For $n\geq 4$,
again, since $C_{n}$ ($n\geq 4$) is triangle-free, from Lemma 1 we have

$C_{n}\simeq L_{2}(C_{n})\simeq\mathsf{TS}_{2}(\overline{C_{n}}).$

This settles the case $k=2$. Again, for $k=3$, note that
$\alpha(\overline{C_{n}})=\omega(C_{n})=2$, therefore it follows from
Proposition 2 that $C_{n}$ ($n\geq 4$) is a $\mathsf{TS}_{k}$-reconfiguration
graph for every $k\geq 2$.

Under certain conditions, one can construct a new
$\mathsf{TS}_{k}$-reconfiguration graph from a known one, as in the following
proposition.

###### Proposition 3

Let $I$ be an independent set of a given graph $G$. Let $k=|I|+1$. Let
$G^{\prime}$ be the graph obtained from $G$ by adding a new vertex $v_{G}$ and
joining it to every vertex in $V(G)-I$. Then, $\mathsf{TS}_{k}(G^{\prime})$ is
obtained from $\mathsf{TS}_{k}(G)$ by adding a new node $I+v_{G}$ and all
incident edges.

###### Proof

By definition, $G$ is an induced subgraph of $G^{\prime}$, and therefore by
Proposition 1, $\mathsf{TS}_{k}(G)$ is an induced subgraph of
$\mathsf{TS}_{k}(G^{\prime})$. It suffices to show that $I+v_{G}$ is the
unique node in $V(\mathsf{TS}_{k}(G^{\prime}))-V(\mathsf{TS}_{k}(G))$. Observe
that for any $J\in V(\mathsf{TS}_{k}(G^{\prime}))-V(\mathsf{TS}_{k}(G))$, we
must have $v_{G}\in J$. Now, if $J\neq I+v_{G}$, there must be some $w\in
V(G)-I$ such that $w\in J$. However, by definition of $G^{\prime}$, we have
$wv_{G}\in E(G^{\prime})$, which contradicts $\\{w,v_{G}\\}\subseteq J\in
V(\mathsf{TS}_{k}(G^{\prime}))$. Therefore, $J=I+v_{G}$. Our proof is
complete. ∎

###### Proposition 4

$K_{m,n}$ is a $\mathsf{TS}_{k}$-reconfiguration graph for some integers
$k\geq 2$ and $n\geq m\geq 1$ if and only if $m=1$ and $n\leq k$ or $m=n=2$.

###### Proof

  * ($\Leftarrow$)

Corollary 2 settles the case $m=n=2$, since $K_{2,2}\simeq C_{4}$. It remains
to consider the case $m=1$ and $n\leq k$. In this case, we claim that there
exists a graph $G$ such that $\mathsf{TS}_{k}(G)\simeq K_{1,n}$. Let
$I_{1}=\\{a_{1},\dots,a_{k}\\}$ be an independent set of size $k$, and let
$K_{n}$ be a clique whose vertices are $b_{1},\dots,b_{n}$. We construct $G$
by joining each $a_{i}$ with $b_{i}$, for $1\leq i\leq n$.

It remains to show that $\mathsf{TS}_{k}(G)\simeq K_{1,n}$. Note that
$V(\mathsf{TS}_{k}(G))=I_{1}\cup\bigcup_{i=1}^{n}J_{i}$, where
$J_{i}=I_{1}-a_{i}+b_{i}$ for $1\leq i\leq n$. It follows that
$\mathsf{TS}_{k}(G)$ has exactly $n+1$ vertices. Additionally, from the
construction of $G$, the set $I_{1}$ is adjacent to every $J_{i}$ ($1\leq
i\leq n$) in $\mathsf{TS}_{k}(G)$, and for every $1\leq i<j\leq n$, we always
have $|J_{j}-J_{i}|=|J_{i}-J_{j}|=2$, which implies that $J_{i}J_{j}\notin
E(\mathsf{TS}_{k}(G))$. Therefore, $\mathsf{TS}_{k}(G)\simeq K_{1,n}$.

  * ($\Rightarrow$)

We first show that if $m=1$ and $n\geq k+1$, there does not exist any $G$ such
that $\mathsf{TS}_{k}(G)\simeq K_{m,n}$, where $k\geq 2$. Suppose to the
contrary that $n\geq k+1$ and $G$ exists. Let
$V(\mathsf{TS}_{k}(G))=\\{I_{1},J_{1},\dots,J_{n}\\}$ and assume without loss
of generality that $I_{1}$ is adjacent to $J_{i}$ in $\mathsf{TS}_{k}(G)$ for
$1\leq i\leq n$. Since $n\geq k+1$, by the pigeonhole principle, there must be
some vertex $u\in I_{1}$ such that sliding the token on $u$ results at least
two different size-$k$ independent sets of $G$, say $J_{1}$ and $J_{2}$, that
are both adjacent to $I_{1}$. Then, we can write $I_{1}=I+x+u$, $J_{1}=I+x+v$,
and $J_{2}=I+x+w$, for some size-$(k-2)$ independent set $I$ of $G$ such that
none of the distinct vertices $u,v,w,x$ is in $I$. By definitions of $J_{1}$
and $J_{2}$, both $v$ and $w$ are not in $I_{1}$. Now, let $J_{3}=I+v+w$. One
can verify that $J_{3}\in V(\mathsf{TS}_{k}(G))$ and therefore must be
adjacent to $I_{1}$ in $\mathsf{TS}_{k}(G)$, which implies $|J_{3}-J_{1}|=1$.
However, note that $\\{v,w\\}\subseteq J_{3}-I_{1}$, which is a contradiction.

$I+x+a_{1}$$I_{1}$$I+x+b_{1}$$J_{1}$$I+x+a_{2}$$I_{2}$$I+x+b_{2}$$J_{2}$(a)$I+a_{1}+a_{2}$$I_{1}$$I+b_{1}+a_{2}$$J_{1}$$I+b_{1}+b_{2}$$I_{2}$$I+a_{1}+b_{2}$$J_{2}$(b)
Figure 5: Two possible forms of the $4$-cycle $I_{1}J_{1}I_{2}J_{2}$ in the
proof of Proposition 4. Here $I$ is a size-$(k-2)$ independent set of a graph
$G$.

It remains to show that if $m\geq 2$ and $n>2$, there does not exist any $G$
such that $\mathsf{TS}_{k}(G)\simeq K_{m,n}$. Again, suppose to the contrary
that $m\geq 2$, $n>2$, and $G$ exists. Suppose that $\mathsf{TS}_{k}(G)$ has
the partite sets $X=\\{I_{1},\dots,I_{m}\\}$ and $Y=\\{J_{1},\dots,J_{n}\\}$,
where $I_{i}$ ($1\leq i\leq m$) and $J_{j}$ ($1\leq j\leq n$) are size-$k$
independent sets of $G$. Let consider the length-$4$ cycle
$I_{1}J_{1}I_{2}J_{2}$, and suppose that we initially slide tokens in $I_{1}$.
To form such a cycle, at most two tokens in $I_{1}$ can be moved from their
original positions, otherwise we need to perform more than four token-slides
to obtain a cycle. More formally, for some size-$(k-2)$ independent set $I$ of
$G$, the sets $I_{1},J_{1},I_{2},J_{2}$ can only be in one of the following
two forms (see Figure 5):

    * (a)

$I_{i}=I+x+a_{i}$ and $J_{i}=I+x+b_{i}$ ($1\leq i\leq 2$). Intuitively, this
corresponds to sliding a single token in $I_{1}$ along the cycle
$a_{1}b_{1}a_{2}b_{2}$ of $G$.

    * (b)

$I_{1}=I+a_{1}+a_{2}$, $J_{1}=I+b_{1}+a_{2}$, $I_{2}=I+b_{1}+b_{2}$, and
$J_{2}=I+a_{1}+b_{2}$. Intuitively, this corresponds to sliding tokens “back
and forth” along the edges $a_{1}b_{1}$ and $a_{2}b_{2}$ of $G$.

In both cases, none of $x$, $a_{i}$ and $b_{i}$ is in $I$, for $1\leq i\leq
2$. It remains to show that both cases lead to some contradiction. Now, if (a)
happens, let $J=I+a_{1}+a_{2}$. One can verify that $J\in\mathsf{TS}_{k}(G)$.
By definition of $J$, it cannot be adjacent to $I_{1}$ in
$\mathsf{TS}_{k}(G)$, otherwise $xa_{2}\in E(G)$, which contradicts
$I_{2}=I+x+a_{2}\in V(\mathsf{TS}_{k}(G))$. Additionally, $J$ cannot be
adjacent to $J_{1}$, because $\\{a_{1},a_{2}\\}\subseteq J-J_{1}$. However,
since $\mathsf{TS}_{k}(G)\simeq K_{m,n}$, it follows that $J$ must be adjacent
to either $I_{1}$ or $J_{1}$, which is a contradiction.

It remains to consider the case (b) happens. In this case, let
$J\in\mathsf{TS}_{k}(G)$ be such that $J$ is adjacent to both $I_{1}$ and
$I_{2}$ and $J\notin\\{J_{1},J_{2}\\}$. Since $n>2$, such a set $J$ exists.
Now, if $\\{a_{1},a_{2}\\}\subseteq J$, we also have
$\\{a_{1},a_{2}\\}\subseteq J-I_{2}=J-(I+b_{1}+b_{2})$. (Both $a_{1}$ and
$a_{2}$ are not in $I$.) This contradicts the adjacency of $J$ and $I_{2}$.
Therefore, $\\{a_{1},a_{2}\\}\nsubseteq J$, and similarly, so does
$\\{b_{1},b_{2}\\}$. Since $J$ is adjacent to both $I_{1}$ and $I_{2}$, it
contains at least one member of $\\{a_{1},a_{2}\\}$ and $\\{b_{1},b_{2}\\}$,
respectively. It follows that either $\\{a_{1},b_{2}\\}$ or
$\\{a_{2},b_{1}\\}$ is in $J$. Now, if $\\{a_{1},b_{2}\\}\subseteq J$, it
follows that $J=I+a_{1}+x=I+b_{2}+y$ for some $x,y\in V(G)$ such that
$xa_{2},yb_{1}\in E(G)$. Then, it follows that $x=b_{2}$ and $y=a_{1}$, that
is, $J=I+a_{1}+b_{2}=J_{1}$, a contradiction. The case
$\\{a_{2},b_{1}\\}\subseteq J$ can be showed similarly. Our proof is complete.

∎

###### Lemma 2

Given a graph $G$. Then, if $\mathsf{TS}_{k}(G)$ has a $K_{n}$, so does $G$,
for integers $k\geq 2$ and $n\geq 3$.

###### Proof

We first consider the case $n=3$, fix any $k\geq 2$ and suppose that
$\mathsf{TS}_{k}(G)$ has a triangle labelled by independent sets
$I_{1},I_{2},I_{3}$. Without loss of generality we may assume
$I_{1}=\\{a_{1},\dots,a_{k-1},w\\}$ and $I_{2}=\\{a_{1},\dots,a_{k-1},x\\}$,
where $wx\in E(G)$. Now, there are two possibilities for $I_{3}$: either (1)
$I_{3}=\\{a_{1},\dots,a_{k-1},y\\}$ where $xy\in E(G)$ or (2)
$I_{3}=\\{a_{1},\dots,a_{i-1},y,a_{i+1},\dots,a_{k-1},x\\}$ where $a_{i}y\in
E(G)$ for some $i\in\\{1,\dots,k-1\\}$. Since $I_{1}$ and $I_{3}$ are adjacent
in $\mathsf{TS}_{k}(G)$, only (1) can happen. Therefore, we must have $yw\in
E(G)$ and so $w,x,y$ define a triangle in $G$. ∎

To conclude this section, we show that a connected split graph is a
$\mathsf{TS}_{k}$-reconfiguration graph if and only if it satisfies certain
restricted conditions, as described in the following lemma.

###### Proposition 5

Fix $k\geq 2$. A connected split graph $F=(K\cup S,E)_{\text{$K$-max}}$ is a
$\mathsf{TS}_{k}$-reconfiguration graph if and only if $|N_{F}(v)\cap S|\leq
k-1$ and $|N_{F}(w)|=1$ for every $v\in K$ and $w\in S$.

###### Proof

  * $(\Leftarrow)$

For a connected split graph $F=(K\cup S,E)_{\text{$K$-max}}$ suppose that
$|N_{F}(v)\cap S|\leq k-1$ and $|N_{F}(w)|=1$ for every $v\in K$, $w\in S$.
Additionally, let $m=|K|$ and $n=|S|$. Suppose that
$K=\\{v_{1},\dots,v_{m}\\}$ and let $n_{i}=|N_{F}(v_{i})\cap
S|=|\\{w^{i}_{1},\dots,w^{i}_{n_{i}}\\}|$ for $1\leq i\leq m$. Observe that
$n=\sum_{i=1}^{m}n_{i}$ and by assumption $n_{i}\leq k-1$ for every $1\leq
i\leq m$. We construct a graph $G$ such that $\mathsf{TS}_{k}(G)\simeq F$ as
follows. (See Figure 6.)

    * –

Let $I=\\{a_{1},\dots,a_{k-1}\\}$ be an independent set. Let $K_{m}$ be a
size-$m$ complete graph with $V(K_{m})=\\{b_{1},\dots,b_{m}\\}$. Let $K_{n}$
be a size-$n$ complete graph with
$V(K_{n})=\bigcup_{i=1}^{m}\bigcup_{j=1}^{n_{i}}\\{x^{i}_{j}\\}$.

    * –

The graph $G$ has $V(G)=I\cup V(K_{n})\cup V(K_{m})$. The edges of $G$ are
defined by joining each $x^{i}_{j}\in V(K_{n})$ to $a_{j}\in I$ ($1\leq j\leq
n_{i}$) and every vertex in $V(K_{m})-b_{i}$.

$K$$S$$I$$K_{n}$$K_{m}$$a_{1}a_{2}\dots a_{k-1}b_{1}$$a_{1}a_{2}\dots
a_{k-1}b_{2}$$a_{1}a_{2}\dots a_{k-1}b_{m}$$x^{1}_{1}a_{2}\dots a_{n_{1}}\dots
b_{1}$$a_{1}x^{1}_{2}\dots a_{n_{1}}\dots b_{1}$$a_{1}a_{2}\dots
x^{1}_{n_{1}}\dots b_{1}$$x^{m}_{1}a_{2}\dots a_{n_{m}}\dots
b_{m}$$a_{1}a_{2}\dots x^{m}_{n_{m}}\dots b_{m}$ $F=(K\cup
S,E)_{\text{$K$-max}}$
$a_{1}$$a_{2}$$a_{n_{1}}$$a_{n_{m}}$$a_{k-1}$$x^{1}_{1}$$x^{1}_{2}$$x^{1}_{n_{1}}$$x^{m}_{1}$$x^{m}_{2}$$x^{m}_{n_{m}}$$b_{1}$$b_{2}$$b_{m-1}$$b_{m}$
$G$ Figure 6: Construction of a graph $G$ such that
$F\simeq\mathsf{TS}_{k}(G)$, where $F$ is a connected split graph satisfying
Proposition 5. Vertices of $F$ are labeled by size-$k$ stable sets of $G$.
Vertices in a light gray (resp., dashed) box forms a clique (resp., stable
set).

Let $f:V(F)\to V(\mathsf{TS}_{k}(G))$ be such that $f(v_{i})=K^{i}=I+b_{i}$
and $f(w^{i}_{j})=K^{i}-a_{j}+x^{i}_{j}$, for $1\leq i\leq m$ and $1\leq j\leq
n_{i}$. One can verify that $f$ is well-defined and bijective. We claim that
$F\simeq_{f}\mathsf{TS}_{k}(G)$, i.e., $uv\in E(F)$ if and only if
$f(u)f(v)\in E(\mathsf{TS}_{k}(G))$.

    * $(\Rightarrow)$

Suppose that $uv\in E(F)$, i.e., either both $u,v$ are in $K$ or $u\in K$ and
$v\in S$. If $u=v_{i}\in K$ and $v=v_{j}\in K$, since $K_{m}$ is a complete
subgraph of $G$, we have $f(u)f(v)=K^{i}K^{j}\in E(\mathsf{TS}_{k}(G))$.
Otherwise, if $u=v_{i}\in K$ and $v=w^{i}_{j}\in S$, since $a_{j}$ is the only
vertex in $\\{a_{1},\dots,a_{k-1}\\}$ adjacent to $x^{i}_{j}$ in $G$, we have
$f(u)f(v)=K^{i}(K^{i}-a_{j}+x^{i}_{j})\in E(\mathsf{TS}_{k}(G))$.

    * $(\Leftarrow)$

Suppose that $f(u)f(v)\in E(\mathsf{TS}_{k}(G))$, i.e., either both
$f(u),f(v)$ are in $\bigcup_{i=1}^{m}K^{i}$ or $f(u)\in\bigcup_{i=1}^{m}K^{i}$
and $f(v)\in\bigcup_{i=1}^{m}\bigcup_{j=1}^{n_{i}}(K^{i}-a_{j}+x^{i}_{j})$. If
$f(u)=K^{i}$ and $f(v)=K^{j}$, by definition, we have $uv=v_{i}v_{j}\in E(F)$.
Otherwise, if $f(u)=K^{i}$ and
$f(v)\in\bigcup_{i=1}^{m}\bigcup_{j=1}^{n_{i}}(K^{i}-a_{j}+x^{i}_{j})$, since
$f(u)f(v)\in E(\mathsf{TS}_{k}(G))$, we must have $f(v)=K^{i}-a_{j}+x^{i}_{j}$
for some $j\in\\{1,\dots,n_{i}\\}$, and therefore $uv=v_{i}w^{i}_{j}\in E(F)$.

  * $(\Rightarrow)$

Suppose that either (1) there exists $w\in S$ such that $|N_{F}(w)|\geq 2$ or
(2) $|N_{F}(w)|=1$ for every $w\in S$ and there exists $v\in K$ such that
$|N_{F}(v)\cap S|\geq k$. We claim that $F$ is not a
$\mathsf{TS}_{k}$-reconfiguration graph. Suppose to the contrary that there
exists a graph $G$ such that $F\simeq_{f}\mathsf{TS}_{k}(G)$. Since $F$ is
connected, so is $\mathsf{TS}_{k}(G)$. From Lemma 2, we must have
$f(v_{i})=I+b_{i}$ ($1\leq i\leq m$) where $\bigcup_{i=1}^{m}\\{b_{i}\\}$
forms a complete subgraph $K_{m}$ of $G$ and $I=\\{a_{1},\dots,a_{k-1}\\}$ is
an independent set of $G-N_{G}[V(K_{m})]$.

If (1) holds, since $|K|=\omega(F)$, there exists $i\in\\{1,\dots,m\\}$ such
that $v_{i}w\notin E(F)$, otherwise $K+w$ forms a clique in $F$ of size
$\omega(F)+1$, which is a contradiction. Lemma 2 also implies that $f(w)=I+x$
for some $x\in V(G)-V(K_{m})-I$. Since $v_{i}w\notin E(F)$, we also have
$f(v_{i})f(w)=(I+b_{i})(I+x)\notin E(\mathsf{TS}_{k}(G))$, which implies
$b_{i}x\notin E(G)$. Then, one can verify that $J=(I-a_{1})+b_{i}+x\in
V(\mathsf{TS}_{k}(G))$. Note that $b_{i}\notin f(v_{j})=I+b_{j}$ for $j\neq i$
and $1\leq j\leq m$. Since $b_{i}x\notin E(G)$, we have $x\neq b_{j}$.
Additionally, since $x\notin I$, we must also have $x\notin f(v_{j})$. Since
$\mathsf{TS}_{k}(G)$ is connected, $J$ must be adjacent to some $f(v_{j})$
($1\leq j\leq m$), which is a contradiction since $\\{b_{i},x\\}\subseteq
J-f(v_{j})$ for $j\neq i$ (i.e., $J$ is not adjacent to any $f(v_{j})$ for
$j\neq i$) and $a_{1}x\notin E(G)$ (i.e., $J$ is not adjacent to
$f(v_{i})=I+b_{i}$).

If (2) holds, suppose that $v=v_{i}$ for some $i\in\\{1,\dots,m\\}$. As
before, one can show that if $f(w)=I+x$ for some $w\in N_{F}(v)\cap S$, there
must be some contradiction. Therefore, for every $w\in N_{F}(v)\cap S$, we
must have $f(w)=(I-a_{j})+x+b_{i}$ for some $j\in\\{1,\dots,k-1\\}$. Since
$|N_{F}(v)\cap S|\geq k$, by the pigeonhole principle, there exists
$j\in\\{1,\dots,k-1\\}$ such that $f(v)=f(v_{i})=I+b_{i}$ has two distinct
non-adjacent neighbors $J_{1}=(I-a_{j})+x_{1}+b_{i}$ and
$J_{2}=(I-a_{j})+x_{2}+b_{i}$. Again, both $x_{1}$ and $x_{2}$ are not in $I$,
and since none of them are adjacent to $b_{i}$, they are also not in
$\\{b_{1},\dots,b_{m}\\}$. This implies $\\{x_{1},x_{2}\\}\cap
f(v_{i})=\emptyset$ for $1\leq i\leq m$. One can verify that
$J=(I-a_{j})+x_{1}+x_{2}\in V(\mathsf{TS}_{k}(G))$ and it is not adjacent to
any $f(v_{i})$ ($1\leq i\leq m$) since $\\{x_{1},x_{2}\\}\subseteq
J-f(v_{i})$. This contradicts the connectivity of $\mathsf{TS}_{k}(G)$.

∎

We conclude this section with a general result that applies to all graphs.
$K_{1,3}$ is also known as the claw and adding an edge between any two of its
degree-$1$ vertices results the paw. $K_{4}-e$ is also known as the diamond.
(See Figure 7.) An outerplanar graph is a graph that has a planar drawing for
which all vertices belong to the outer face of the drawing. A maximal
outerplanar graph is an outerplanar graph in which adding a single edge breaks
outerplanarity.

$K$$S$$I$$K_{n}$$K_{m}$$P_{4}$clawpaw$C_{4}$diamond$K_{4}$

Figure 7: Connected graphs on four vertices.

###### Proposition 6

  * (a)

Let $G$ be a graph whose components are $G_{1},G_{2},\dots,G_{p}$, for some
$p\geq 1$. Suppose that all $G_{i}$ ($1\leq i\leq p$) are
$\mathsf{TS}_{k}$-reconfiguration graphs for some fixed integer $k\geq 2$.
Then, so is $G$.

  * (b)

The diamond $K_{4}-e$ is the unique smallest graph that is not a
$\mathsf{TS}_{k}$-reconfiguration graph for any $k\geq 2$.

  * (c)

The following generalized graphs on $n\geq 4$ vertices of the diamond are not
$\mathsf{TS}_{k}$-reconfiguration graphs for any $k\geq 2$: Maximal
outerplanar graphs and $K_{n}-e$.

  * (d)

There exists a disconnected $\mathsf{TS}_{k}$-reconfiguration graph $G$ such
that one of its components is not a $\mathsf{TS}_{k}$-reconfiguration graph
for any $k\geq 2$.

###### Proof

  * (a)

Let $H_{i}$ ($1\leq i\leq p$) be such that $G_{i}=\mathsf{TS}_{k}(H_{i})$. Let
$H$ be the graph obtained by joining each vertex of $H_{i}$ to all vertices of
$H_{j}$, for every $1\leq i<j\leq p$. From the above construction, any
size-$k$ independent set of $H$ must be also an independent set of $H_{i}$,
for some $i\in\\{1,\dots,p\\}$. As a result, $\mathsf{TS}_{k}(H)$ is the
disjoint union of $\mathsf{TS}_{k}(H_{i})$ for all $i$, that is,
$G=\mathsf{TS}_{k}(H)$.

  * (b)

Graphs on at most three vertices are disjoint union of paths and cycles, and
since any path or cycle is a $\mathsf{TS}_{k}$-reconfiguration graph for
$k\geq 2$ (Corollary 2), it follows from (a) that so are their disjoint
unions. If a graph on four vertices is disconnected, each of its components
has at most three vertices, and we are done.

Thus, it suffices to consider six connected graphs on four vertices described
in Figure 7. Among these graphs, $P_{4}$, $C_{4}$, and $K_{4}$ are always
$\mathsf{TS}_{k}$-reconfiguration graphs for $k\geq 2$ and the claw $K_{1,3}$
is a $\mathsf{TS}_{k}$-reconfiguration graph for $k\geq 3$. Let $H$ be the
kite—the graph obtained from a diamond by attaching a leaf to one of its
degree-$2$ vertices. One can verify that $\mathsf{TS}_{2}(H)$ is indeed a paw,
and since $\alpha(H)=2$, it follows from Proposition 2 that
$\mathsf{TS}_{k}(H+(k-2)K_{1})$ is also a paw, i.e., the paw is always a
$\mathsf{TS}_{k}$-reconfiguration graph for $k\geq 2$.

It remains to show that the diamond is not a $\mathsf{TS}_{k}$-reconfiguration
graph for any $k\geq 2$. Suppose to the contrary that there exists a graph $Q$
such that $K_{4}-e=\mathsf{TS}_{k}(Q)$. It follows from Lemma 2 that vertices
of $K_{4}-e$ must be of the form $I_{1}=I+a$, $I_{2}=I+b$, $I_{3}=I+c$,
$I_{4}=I+d$, where $I$ is a size-$(k-1)$ independent set of $Q$ and
$\\{a,b,c,d\\}\subseteq V(Q)-I$ induce a diamond in which, say $a$ and $c$ are
non-adjacent. However, for any $x\in I$, note that $J=(I-x)+a+c$ is a size-$k$
independent set of $Q$, and therefore it must be a vertex of $K_{4}-e$, which
is a contradiction since $J\notin\\{I_{1},\dots,I_{4}\\}$.

  * (c)

Use a similar argument as in the proof for the diamond.

  * (d)

Take $G=\mathsf{TS}_{k}(\text{diamond}+(k-1)K_{1})$. It is not hard to verify
that the diamond is a component of $G$ and from (b) it is not a
$\mathsf{TS}_{k}$-reconfiguration graph for any $k\geq 2$.

##  5 Properties of Reconfiguration Graphs

In this section we study various graph properties to see if they are inherited
by their $\mathsf{TS}$-reconfiguration graphs, and vice versa. The notation
$\mathcal{P}(G)\Rightarrow\mathcal{P}(\mathsf{TS}(G))$ means: if you assume a
property $\mathcal{P}$ holds for $G$ (in certain cases, the property always
holds, but in some other cases, it may or may not hold), is it true (and under
which conditions) that $\mathcal{P}$ also holds for $\mathsf{TS}(G)$?
Conversely, $\mathcal{P}(\mathsf{TS}(G))\Rightarrow\mathcal{P}(G)$ means that
if $\mathcal{P}$ holds for $\mathsf{TS}(G)$ then when does it hold for $G$?
For any fixed $k$ we define similar notations
$\mathcal{P}(G)\Rightarrow\mathcal{P}(\mathsf{TS}_{k}(G))$ and
$\mathcal{P}(\mathsf{TS}_{k}(G))\Rightarrow\mathcal{P}(G)$. Since
$G\simeq\mathsf{TS}_{1}(G)$, the case $k=1$ is uninteresting and therefore we
only consider $k\geq 2$.

For example, suppose that $G$ is $P_{n}$ and $\mathcal{P}$ is “connected”.
What we want to know is: if $P_{n}$ is connected (which is obviously true), is
it true (and under which conditions) that $\mathsf{TS}(P_{n})$ is also
connected? This question is trivial for $\mathsf{TS}(P_{n})$, because by
definition it contains all stable sets of $G$ as vertices, and one cannot, for
example, join a stable set of size $k$ and a stable set of size $k+1$ by an
edge. This means $\mathsf{TS}(P_{n})$ is not connected. Even for
$\mathsf{TS}_{k}(P_{n})$ with some fixed $k$, this question is not much
harder, since one can verify that any two size-$k$ stable sets of $P_{n}$ can
be connected by a path in $\mathsf{TS}_{k}(P_{n})$ (just pushing tokens toward
one endpoint of the path), which means the graph is clearly connected. These
questions are more challenging with respect to different graphs $G$ and
properties $\mathcal{P}$. Our results are summarized in Table 2.

Table 2: Some properties of (reconfiguration) graphs. Here $n=|V(G)|$. There are four cases: (a) $\mathcal{P}(G)\Rightarrow\mathcal{P}(\mathsf{TS}(G))$, (b) $\mathcal{P}(\mathsf{TS}(G))\Rightarrow\mathcal{P}(G)$, (c) $\mathcal{P}(G)\Rightarrow\mathcal{P}(\mathsf{TS}_{k}(G))$, and (d) $\mathcal{P}(\mathsf{TS}_{k}(G))\Rightarrow\mathcal{P}(G)$. $\mathcal{P}$ | $G$ | (a) | (b) | (c) | (d) | Ref.
---|---|---|---|---|---|---
$s$-partite | general | yes | no | Prop. 7
planar | $P_{n}$ | yes, iff $n\leq 8$ |  | yes, iff $k=2$, $n\geq 3$
---
or $k\geq 3$, $n\leq 8$
Prop. 8
tree | yes, iff $n\leq 7$ | Prop. 9
$C_{n}$ | yes, iff $n\leq 6$ | Prop. 10
connected
Eulerian | $C_{n}$ | no | yes | yes, iff $1\leq k<n/2$ | Prop. 11
general | no | yes | no | no | Prop. 12
infinite girth | $P_{n}$ | yes, iff $n\leq 4$ | yes, iff $n\leq 2k$ | Prop. 13
finite girth | $C_{n}$ | yes | yes, iff $1\leq k<n/2$ | Prop. 14
having $K_{s}$ | general | yes | no | yes | Prop. 15

###  5.1 $s$-Partitedness

A proper $s$-coloring of a graph $G$ is a mapping $f:V(G)\to\\{0,\dots,s-1\\}$
such that $f(u)\neq f(v)$ if $uv\in E(G)$, where $u,v\in V(G)$ and $s$ is a
positive integer. If $G$ has a proper $s$-coloring, we call it a $s$-partite
graph. The chromatic number of a graph $G$, denoted by $\chi(G)$, is the
smallest number $s$ such that $G$ has a proper $s$-coloring.

###### Proposition 7

  * (a)

$G$ is $s$-partite if and only if $\mathsf{TS}(G)$ is $s$-partite. In other
words, $\chi(G)=\chi(\mathsf{TS}(G))$.

  * (b)

For each $s\geq 2$, one can construct a graph $G$ such that
$\chi(\mathsf{TS}_{k}(G))<\chi(G)=s$, for every $2\leq k\leq\alpha(G)$.

###### Proof

  * (a)

(by Masahiro Takahashi.) The if direction follows directly from
$G\simeq\mathsf{TS}_{1}(G)$. It remains to show that if $G$ is $s$-partite, so
is $\mathsf{TS}(G)$. Since $G$ is $s$-partite, there exists a proper
$s$-coloring $f:V(G)\to\\{0,\dots,s-1\\}$ of vertices of $G$. For each
independent set $I$ of $G$, let $g(I)=\big{(}\sum_{v\in I}f(v)\big{)}\mod s$.
Since $G$ is $s$-partite, each $\mathsf{TS}$-step only slides a token from one
color class to another, and therefore if $I$ and $J$ are adjacent in
$\mathsf{TS}(G)$, $g(I)\neq g(J)$. As a result, $g$ is a $s$-coloring of
$\mathsf{TS}(G)$, which means $\mathsf{TS}(G)$ is $s$-partite.

To see that $\chi(G)=\chi(\mathsf{TS}(G))$, note that since
$G\simeq\mathsf{TS}_{1}(G)$ is a subgraph of $\mathsf{TS}(G)$, we have
$\chi(G)\leq\chi(\mathsf{TS}(G))$. On the other hand, if $G$ has a
$\chi(G)$-coloring, so does $\mathsf{TS}(G)$, i.e.,
$\chi(\mathsf{TS}(G))\leq\chi(G)$.

  * (b)

Fix $s\geq 2$. Let $G^{\prime}$ be any graph with $\chi(G^{\prime})=s$ and
construct $G$ from $G^{\prime}$ by adding an additional vertex $x$ adjacent to
all vertices in $V(G^{\prime})$. We have $\alpha(G)=\alpha(G^{\prime})$ and
since a new colour is required for $x$, $\chi(G)=\chi(G^{\prime})+1$. For each
$2\leq k\leq\alpha(G)$ the stable sets of size $k$ in $G$ and $G^{\prime}$ are
identical and so is their adjacency, hence
$\mathsf{TS}_{k}(G)\simeq\mathsf{TS}_{k}(G^{\prime})$. Since
$\mathsf{TS}_{k}(G^{\prime})$ is a subgraph of $\mathsf{TS}(G^{\prime})$ we
may use part (a) to obtain:
$\chi(\mathsf{TS}_{k}(G))=\chi(\mathsf{TS}_{k}(G^{\prime}))\leq\chi(\mathsf{TS}(G^{\prime}))=\chi(G^{\prime})=\chi(G)-1$.

∎

###  5.2 Planarity

A graph is planar if one can draw it in the plane such that its edges
intersect only at their endpoints. The well-known Kuratowski’s Theorem says
that a graph $G$ is planar if and only if it does not contain any subdivision
of $K_{5}$ or $K_{3,3}$ as a subgraph.

###### Proposition 8

  * (a)

$\mathsf{TS}_{2}(P_{n})$ is planar for every $n\geq 3$.

  * (b)

$\mathsf{TS}_{3}(P_{n})$ is planar for every $n\leq 8$ and non-planar
otherwise.

  * (c)

$\mathsf{TS}(P_{n})$ is planar for $n\leq 8$ and non-planar otherwise.

###### Proof

  * (a)

Suppose that $P_{n}=v_{1}\dots v_{n}$ ($n\geq 3$). For each node
$\\{v_{i},v_{j}\\}\in V(\mathsf{TS}_{2}(P_{n}))$ ($1\leq i,j\leq n$ and
$|i-j|\geq 2$), its neighbors form a non-empty subset of
$\big{\\{}\\{v_{i-1},v_{j}\\},\\{v_{i+1},v_{j}\\},\allowbreak\\{v_{i},v_{j-1}\\},\\{v_{i},v_{j+1}\\}\big{\\}}$.
Therefore, $\mathsf{TS}_{2}(P_{n})$ can be embedded into a $n\times n$ planar
grid graph, which means it is also planar.

  * (b)

In Figure 8, we show a planar embedding of $\mathsf{TS}_{3}(P_{8})$. In Figure
9 we show a subdivision of $K_{3,3}$ that is contained in
$\mathsf{TS}_{3}(P_{9})$.

  * (c)

$\mathsf{TS}_{1}(P_{8})\simeq P_{8}$ and it can readily be verified that
$\mathsf{TS}_{4}(P_{8})\simeq P_{5}$. From (a), $\mathsf{TS}_{2}(P_{8})$ is
planar. From (b), $\mathsf{TS}_{3}(P_{8})$ is planar and
$\mathsf{TS}_{3}(P_{9})$ is not.

$K$$S$$I$$K_{n}$$K_{m}$$135$$136$$137$$138$$146$$147$$148$$157$$158$$168$$246$$247$$248$$257$$258$$268$$357$$358$$368$$468$
Figure 8: A planar drawing of $\mathsf{TS}_{3}(P_{8})$. Each number of the
form $abc$ inside a node represents an independent set
$\\{v_{a},v_{b},v_{c}\\}$ of $P_{8}=v_{1}\dots v_{8}$.
$K$$S$$I$$K_{n}$$K_{m}$$259$$369$$268$$249$$359$$269$$358$$368$$248$$258$$257$$157$$158$$168$$149$$159$$169$$179$$279$$379$$479$$469$
Figure 9: A subdivision of $K_{3,3}$ that is contained in
$\mathsf{TS}_{3}(P_{9})$. Each number of the form $abc$ inside a node
represents an independent set $\\{v_{a},v_{b},v_{c}\\}$ of $P_{9}=v_{1}\dots
v_{9}$.

∎

###### Proposition 9

$\mathsf{TS}(T)$ is planar for all trees $T$ having at most seven vertices and
non-planar otherwise.

###### Proof

A computer search showed that:

  * •

All eleven trees $T$ on seven vertices satisfy $\mathsf{TS}(T)$ is planar.

  * •

Among twenty-three trees $T$ on eight vertices, seven of them satisfy
$\mathsf{TS}(T)$ is non-planar.

See https://hoanganhduc.github.io/graphs/ for a list of the mentioned graphs
and their corresponding $\mathsf{TS}$-reconfiguration graphs. ∎

###### Proposition 10

  * (a)

$\mathsf{TS}(C_{n})$ is planar for $n\leq 6$ and non-planar otherwise.

  * (b)

With respect to the number of vertices, $C_{7}$ is the unique smallest graph
$G$ for which $\mathsf{TS}(G)$ is non-planar.

  * (c)

With respect to the number of edges, including $C_{7}$, there are eight
smallest graphs $G$ for which $\mathsf{TS}(G)$ is non-planar.

###### Proof

A computer search showed that

  * (i)

For each of the $99$ connected planar graphs $G$ on six vertices,
$\mathsf{TS}(G)$ is planar.

  * (ii)

There are seven trees $T$ on eight vertices whose $\mathsf{TS}(T)$ is non-
planar. (Proposition 9.)

  * (iii)

$\mathsf{TS}_{2}(C_{7})$ is non-planar. (Figure 10)

See https://hoanganhduc.github.io/graphs/ for a list of the mentioned graphs
and their corresponding $\mathsf{TS}$-reconfiguration graphs.

$K$$S$$I$$K_{n}$$K_{m}$$74$$52$$62$$73$$63$$51$$31$$41$$42$$72$$53$$64$$75$$61$
Figure 10: A subdivision of $K_{3,3}$ that is contained in
$\mathsf{TS}_{2}(C_{7})$. Each number of the form $ab$ inside a node
represents an independent set $\\{v_{a},v_{b}\\}$ of $C_{7}=v_{1}\dots
v_{7}v_{1}$.

∎

###### Corollary 3

  * (i)

If $\text{girth}(G)\geq 7$, the graph $\mathsf{TS}(G)$ is non-planar.

  * (ii)

There exists a graph $G$ whose girth is $3$ and $\mathsf{TS}(G)$ is non-
planar.

###### Proof

  * (i)

Let $C$ be a cycle in $G$ whose length is $\text{girth}(G)\geq 7$. Note that
$C$ does not contain any chord; otherwise, we can find a cycle smaller than
$C$, which contradicts our assumption. Now, consider the subgraph
$\mathcal{H}$ of $\mathsf{TS}(G)$ induced by only independent sets in $C$. It
follows from Proposition 10 that $\mathcal{H}$ is non-planar, and so is
$\mathsf{TS}(G)$.

  * (ii)

Take $G$ as the graph obtained by connecting every vertex of $P_{n}$ to some
vertex $v$ not in $P_{n}$. The subgraph of $\mathsf{TS}(G)$ induced by
independent sets in $P_{n}$ is non-planar when $n\geq 9$ (see Proposition 8).

∎

###  5.3 Eulerianity

A graph $G$ is Eulerian if it has an Eulerian cycle—a cycle that visits each
edge of $G$ exactly once. It is well-known that a graph $G$ is Eulerian if and
only if it is connected and every vertex has even degree.

###### Proposition 11

The graph $\mathsf{TS}_{k}(C_{n})$ is Eulerian, for $1\leq k<n/2$.

###### Proof

Suppose that $C_{n}=w_{1}w_{2}\dots w_{n}$. It is not hard to see that
$\mathsf{TS}_{k}(G)$ is connected, since any independent set of size $k$,
where $1\leq k<n/2$, can be reconfigured to the canonical independent set
$\\{w_{1},w_{3},\allowbreak\dots,w_{2k+1}\\}$. Let $I$ be any independent set
of $C_{n}$ of size $k$. We show that $\deg_{\mathsf{TS}(C_{n})}(I)$ is even.
Note that only the maximal odd-length paths $P=v_{1}v_{2}\dots v_{2i+1}$ in
$C_{n}$ satisfying $\\{v_{1},v_{3},\dots,v_{2i+1}\\}\subseteq I$ affect
$\deg_{\mathsf{TS}(C_{n})}(I)$, and each of such path contributes either $0$
or $2$ to $\deg_{\mathsf{TS}(C_{n})}(I)$. Thus, $\deg_{\mathsf{TS}(C_{n})}(I)$
is even. ∎

###### Proposition 12

  * (a)

For any Eulerian graph $G$ on $n\geq 4$ vertices, every component of
$\mathsf{TS}_{2}(G)$ is Eulerian.

  * (b)

There exists an Eulerian graph $G$ where $\mathsf{TS}_{k}(G)$ is not Eulerian,
for any $k\in\\{3,\dots,\alpha(G)\\}$.

  * (c)

For any graph $G$, if $\mathsf{TS}(G)$ is Eulerian, so is $G$. Moreover, for
any $k\geq 2$, one can construct a graph $G$ such that $G$ is not Eulerian but
$\mathsf{TS}_{k}(G)$ is.

###### Proof

  * (a)

It suffices to show that all nodes of $\mathsf{TS}_{2}(G)$ have even degree.
Take any independent set $I=\\{v_{1},v_{2}\\}$. We have

$\deg_{\mathsf{TS}_{2}(G)}(I)=\deg_{G}(v_{1})+\deg_{G}(v_{2})-2|N_{G}(v_{1})\cap
N_{G}(v_{2})|,$

which is always even because $G$ is Eulerian.

  * (b)

For $k\geq 3$, take $G$ as the graph containing exactly two cycles: $C_{3}$
and $C_{2\ell+1}=v_{1}v_{2}\dots v_{2\ell+1}$. Note that $\alpha(G)=\ell+1$.
Suppose that vertices of $C_{2\ell+1}$ are in counter-clockwise order,
$V(C_{3})\cap V(C_{2\ell+1})=\\{v_{1}\\}$. For $3\leq k\leq\ell+1$, let
$I=\\{w,v_{2\ell+1},v_{2},v_{4},\dots,v_{2(k-2)}\\}$, where $w\in
V(C_{3})-v_{1}$. In these cases, we all have $\deg_{\mathsf{TS}_{k}(G)}(I)=3$,
and therefore $\mathsf{TS}_{k}(G)$ is not Eulerian.

  * (c)

Clearly, if $\mathsf{TS}(G)$ is Eulerian, it must be connected, and therefore
$\mathsf{TS}(G)\simeq\mathsf{TS}_{1}(G)\simeq G$, which implies $G$ is also
Eulerian. For $k=2$, let $G$ be a graph obtained by joining $K_{4}$ with a
single vertex. Since $G$ has a vertex of degree $1$, it is not Eulerian. One
can verify that $\mathsf{TS}_{2}(G)\simeq C_{3}$ and therefore it is Eulerian.
For $k\geq 3$, let $G$ be a graph obtained by joining a vertex of $C_{3}$ with
an endpoint of $P_{3}$ and with $k-2$ new vertices. Again, since $G$ has a
vertex of degree $1$, it is not Eulerian. One can verify that
$\mathsf{TS}_{k}(G)\simeq C_{4}$ and therefore it is Eulerian.

∎

###  5.4 Girth

Recall that the girth of a graph $G$ is the smallest size of a cycle in $G$,
and is $\infty$ if $G$ is a forest, i.e., it has no cycles.

###### Proposition 13

For every $n\geq 2k+1$, $\text{girth}(\mathsf{TS}_{k}(P_{n}))$ is $4$ and
$\infty$ otherwise. Consequently, $\text{girth}(\mathsf{TS}(P_{n}))$ is $4$
for every $n\geq 5$ and $\infty$ otherwise.

###### Proof

From Proposition 7, since $\mathsf{TS}(P_{n})$ is bipartite, it does not
contain any $C_{3}$, and therefore neither does $\mathsf{TS}_{k}(P_{n})$. Let
$P_{2k+1}=v_{1}v_{2}\dots v_{2k+1}$. One can readily verify that
$\mathsf{TS}_{k}(P_{2k+1})$ has a $C_{4}$ which contains the size-$k$
independent set $I=\\{v_{1},v_{4},v_{7},v_{9},\dots,v_{2k+1}\\}$. For $n\geq
2k+1$, since $P_{2k+1}$ is an induced subgraph of $P_{n}$, Proposition 1
implies that $\mathsf{TS}_{k}(P_{2k+1})$ is also an induced subgraph of
$\mathsf{TS}_{k}(P_{n})$, and therefore $\mathsf{TS}_{k}(P_{n})$ also contains
a $C_{4}$. Thus, $\text{girth}(\mathsf{TS}_{k}(P_{n}))$ is $4$ for every
$n\geq 2k+1$. It remains to show that when $n\leq 2k$, the graph
$\mathsf{TS}_{k}(P_{n})$ has no cycles. To see this, note that we also have
$k\leq\alpha(P_{n})=\lceil n/2\rceil$. Therefore, either $k=n/2$ or
$k=(n+1)/2$ and in both cases one can verify that $\mathsf{TS}_{k}(P_{n})$ has
no cycles. Consequently, since $\mathsf{TS}_{2}(P_{n})$ is an induced subgraph
of $\mathsf{TS}(P_{n})$, we have $\text{girth}(\mathsf{TS}(P_{n}))$ is $4$ for
every $n\geq 5=2\times 2+1$ and $\infty$ otherwise. ∎

###### Proposition 14

For $1\leq k<n/2$, $\text{girth}(\mathsf{TS}_{k}(C_{n}))=n$. If $k=n/2$, we
have $\text{girth}(\mathsf{TS}_{k}(C_{n}))=\infty$. Consequently,
$\text{girth}(\mathsf{TS}(C_{n}))=n$.

###### Proof

Suppose that $I=\\{v_{1},v_{2},\dots,v_{k}\\}$ is an independent set of
$C_{n}$, where $1\leq k<n/2$ and $\\{v_{i}\\}_{i=1,\dots,k}$ are ordered in
counter-clockwise direction. Since no token can “jump” above any other tokens,
any cycle $\mathcal{C}$ in $\mathsf{TS}(C_{n})$ containing $I$ must be formed
by moving tokens in counter-clockwise direction such that finally, the token
originally placed on $v_{i}$ is placed on $v_{i+1}$ ($i=1,2,\dots,k-1$), and
the token originally placed on $v_{k}$ is placed on $v_{1}$. One can achieve
this plan with exactly $n$ token-slides, provided that $1\leq k<n/2$. If
$k=n/2$, the graph $\mathsf{TS}_{k}(C_{n})$ contains exactly two isolated
vertices. Then, its girth is $\infty$. Consequently, since
$\mathsf{TS}_{k}(C_{n})$ is a subgraph of $\mathsf{TS}(C_{n})$ for $1\leq
k\leq n/2$, it follows that $\text{girth}(\mathsf{TS}(C_{n}))=n$.

∎

###  5.5 Clique of given size

###### Proposition 15

  * (a)

$G$ has a $K_{s}$ if and only if $\mathsf{TS}(G)$ has a $K_{s}$ ($s\geq 3$).

  * (b)

There exists a split graph $G$ such that $G$ has a $K_{s}$ and
$\mathsf{TS}_{k}(G)$ ($k\geq 2$) does not.

###### Proof

  * (a)

$G\simeq\mathsf{TS}_{1}(G)$ implies the only-if direction. Lemma 2 implies the
if direction.

  * (b)

Take a split graph $G=(K\cup S,E)_{\text{$K$-max}}$ such that $|K|=s$ and
there exists $v\in K$ with $\bigcup_{w\in S}N_{G}(w)=\\{v\\}$. Suppose to the
contrary that $\mathsf{TS}_{k}(G)$ ($k\geq 2$) has a $K_{s}$. Thus, from Lemma
2, there must be a token $t$ which traverses through all vertices in $K$.
Since $k\geq 2$, there is always at least one token $t^{\prime}\neq t$ in $S$,
which implies that $t$ can never be slid to $v$, a contradiction. Thus,
$\mathsf{TS}_{k}(G)$ ($k\geq 2$) has no $K_{s}$.

∎

##  6 Decompositions and Joins

A major problem in constructing the $\mathsf{TS}_{k}$-reconfiguration graph of
a given graph $G$ is that the number of independent sets in $G$ may be
exponentially large and hence so may be $\mathsf{TS}_{k}(G)$. However, the
structure of $G$ may be such that it can be decomposed into smaller subgraphs
for which the $\mathsf{TS}_{k}$-reconfiguration graphs are more easily
obtained. This will be useful whenever $\mathsf{TS}_{k}(G)$ can be built from
these smaller graphs. We present one such decomposition in this section. In a
subsequent paper [2] we introduced a different decomposition, called an
$H$-decomposition, useful in the context where the
$\mathsf{TS}_{k}$-reconfiguration graphs are acyclic.

###### Definition 1

The $H_{1},H_{2}$ join $G$ of vertex disjoint simple graphs $G_{1}$ and
$G_{2}$, where $H_{i}\subseteq G_{i},i=1,2$, is formed by adding all edges
between $H_{1}$ and $H_{2}$.

Figure 11(a) illustrates a join of the graphs $G_{1}$ and $G_{2}$. In cases
where the graph $G$ can be decomposed along a join we can decompose
$\mathsf{TS}_{k}(G)$ into connected components. For the decomposition theorem
we need a method of combining stable sets of possibly different sizes from
disjoint graphs.

###### Definition 2

Let $G_{1}$ and $G_{2}$ be simple connected graphs on different sets of
vertices. For $1\leq s<k$ we define the product
$\mathsf{TS}_{s}(G_{1})\otimes\mathsf{TS}_{k-s}(G_{2})$: The vertices are of
the form $S_{1}\cup S_{2}$ where $S_{1}\in V(\mathsf{TS}_{s}(G_{1}))$ and
$S_{2}\in V(\mathsf{TS}_{k-s}(G_{2}))$. The edges in the product are of the
form ($S_{1}\cup S_{2}$, $S_{1}^{{}^{\prime}}\cup S_{2}$) where
$(S_{1},S_{1}^{{}^{\prime}})\in E(\mathsf{TS}_{s}(G_{1}))$ and ($S_{1}\cup
S_{2}$, $S_{1}\cup S_{2}^{{}^{\prime}}$) where $(S_{2},S_{2}^{{}^{\prime}})\in
E(\mathsf{TS}_{k-s}(G_{2}))$.

Figure 11(b) shows some examples of this definition. In the following
proposition we show that if graph $G$ is the join of $G_{1}$ and $G_{2}$ then
$\mathsf{TS}_{k}(G)$ is the union of $\mathsf{TS}_{k}(G_{1})$,
$\mathsf{TS}_{k}(G_{2})$ and products of $\mathsf{TS}_{k}$-reconfiguration
graphs for smaller values of $k$. It is illustrated in Figure 11.

$K$$S$$I$$K_{n}$$K_{m}$$G_{1}$$G_{2}$$H_{1}$$H_{2}$$\mathsf{TS}_{3}(G_{1})$$\mathsf{TS}_{3}(G_{2})$$\mathsf{TS}_{2}(G_{1})\otimes\mathsf{TS}_{1}(G_{2}-H_{2})$$\mathsf{TS}_{1}(G_{1}-H_{1})\otimes\mathsf{TS}_{2}(G_{2})$$\mathsf{TS}_{1}(G_{1})\otimes\mathsf{TS}_{2}(G_{2}-H_{2})$$1$$2$$3$$4$$5$$6$$7$$8$$9$(a)
$G$ is $H_{1},H_{2}$ join of
$G_{1},G_{2}$.$234$$569$$238$$239$$237$$248$$249$$247$$348$$349$$347$$178$$278$$378$$478$$156$$159$$169$(b)
A decomposition of $\mathsf{TS}_{k}(G)$. Figure 11: A graph $G$ and a
decomposition of $\mathsf{TS}_{k}(G)$ using Proposition 16.

###### Proposition 16

Let $G$ be the $H_{1},H_{2}$ join of graphs $G_{1}$,$G_{2}$. Choose an integer
$k\geq 2$ so that $G_{1}$,$G_{2}$ each contain a stable set of size $k$.
(a) $\mathsf{TS}_{k}(G)$ be decomposed into $k+1$ (possibly empty) vertex
disjoint subgraphs $\mathsf{TS}_{k}(G_{1})$, $\mathsf{TS}_{k}(G_{2})$, and for
$1\leq s<k$ the union of

$\mathsf{TS}_{s}(G_{1})\otimes\mathsf{TS}_{k-s}(G_{2}-H_{2})\text{~{}~{}and~{}~{}}\mathsf{TS}_{s}(G_{1}-H_{1})\otimes\mathsf{TS}_{k-s}(G_{2}).$
(1)

(b) Fix $i=1$ or $2$. Every stable set $S_{i}$ of size $k$ in $G_{i}$
satisfies

$|S_{i}\cap V(H_{i})|\neq 1$ (2)

if and only if $\mathsf{TS}_{k}(G_{i})$ is disconnected from the remaining $k$
subgraphs of $\mathsf{TS}_{k}(G)$.

###### Proof

Let $S$ be an independent set of size $k$ in $G$ and, for $i=1,2$ let
$S_{i}=S\cap V(G_{i})$. Define $s=|S_{1}|$.

  * (a)

We consider the three cases.

    * (i)

$s=k$.
In this case $S_{1}$ is an independent set in $G_{1}$, so $S\in
V(\mathsf{TS}_{k}(G_{1}))$.

    * (ii)

$s=0$.
The symmetric case, which yields $S\in V(\mathsf{TS}_{k}(G_{2}))$.

    * (iii)

$0<s<k$.
First suppose that $S\cap V(H_{1})\neq\emptyset$ implying, by construction of
the join, that $S\cap V(H_{2})=\emptyset$. We have that $S_{1}\in
V(T_{s}(G_{1})),S_{2}\in V(T_{k-s}(G_{2}-H_{2}))$ and therefore
$(S_{1},S_{2})\in T_{s}(G_{1})\otimes T_{k-s}(G_{2}-H_{2})$. Symmetrically, if
$S\cap V(H_{2})\neq\emptyset$ we conclude that $(S_{1},S_{2})\in
T_{s}(G_{1}-H_{1})\otimes T_{k-s}(G_{2})$. Note that $S$ will appear in both
sides of the union in (1) if and only if $S\cap V(H_{i})=\emptyset,i=1,2$.

The vertices of the $k+1$ subgraphs of $\mathsf{TS}_{k}(G)$ in (a) correspond
to stable sets in $G$ with different values of $s$, so they are vertex
disjoint.

  * (b)

Suppose $i=1$. A similar argument applies to the case $i=2$.

    * ($\Rightarrow$)

We show that it is impossible to slide a vertex $v\in S_{1}$ to a vertex $w\in
G_{2}$ to create a new stable set. Indeed, for such a slide to be possible we
must have $v\in H_{1}$ and so by (1) $S_{1}\cap H_{1}$ must contain another
vertex $u$. Now $w\in H_{2}$ so it is adjacent to $u$ and hence $v$ cannot be
slid to $w$. Hence there are no edges from $\mathsf{TS}_{k}(G_{1})$ to any of
the other $k$ subgraphs in $\mathsf{TS}_{k}(G)$.

    * ($\Leftarrow$)

Suppose, by way of contradiction, that there is an edge between
$\mathsf{TS}_{k}(G_{1})$ and one of the other $k$ subgraphs. Then there is a
vertex $v\in H_{1}$ that can be slide to a vertex $w\in H_{2}$. This is only
possible if $|S_{1}\cap V(H_{1})|=1$ yielding the required contradiction.

∎

Observe that equation (2) in (b) is automatically satisfied if for either
$i=1$ or $2$ we have $|V(G_{i})|<|V(H_{i})|+k-1$. We remark that even when
part (b) applies there may be additional edges between the $k-1$ graphs
described by the products in part (a).

##  7 Concluding Remarks

In this paper, our primary focus was the realizability and structural
properties of reconfiguration graphs of independent sets under Token Sliding.

In Section 4, we presented necessary and sufficient conditions for a graph $G$
to be a $\mathsf{TS}_{k}$-reconfiguration graph ($k\geq 2$), where $G$ belongs
to certain restricted graph classes, namely complete graphs, paths, cycles,
complete bipartite graphs, connected split graphs, maximal outerplanar graphs,
and complete graphs minus one edge. Even for $k=2$, it remains unknown what
the necessary and sufficient conditions for a forest to be a
$\mathsf{TS}_{k}$-reconfiguration graph are. We remark that “being a
$\mathsf{TS}_{k}$-reconfiguration graph” is not hereditary, even for trees.
For example $K_{1,3}$ is not a $\mathsf{TS}_{2}$-reconfiguration graph
(Proposition 4) but if we replace one edge by a $P_{4}$ it is (Figure 12).
Proposition 13 provided a useful insight: given a forest $F$, if there exists
$G$ such that $F\simeq\mathsf{TS}_{2}(G)$, the graph $G$ must be $P_{5}$-free
(e.g., see the graph $G$ in Figure 12).

$K$$S$$I$$K_{n}$$K_{m}$$G_{1}$$G_{2}$$H_{1}$$H_{2}$$\mathsf{TS}_{3}(G_{1})$$\mathsf{TS}_{3}(G_{2})$$\mathsf{TS}_{2}(G_{1})\otimes\mathsf{TS}_{1}(G_{2}-H_{2})$$\mathsf{TS}_{1}(G_{1}-H_{1})\otimes\mathsf{TS}_{2}(G_{2})$$\mathsf{TS}_{1}(G_{1})\otimes\mathsf{TS}_{2}(G_{2}-H_{2})$$ab$$ac$$bd$$ae$$ef$$ce$$T\simeq\mathsf{TS}_{2}(G)$$a$$b$$c$$d$$e$$f$$G$
Figure 12: Replacing an edge of $K_{1,3}$ by a $P_{4}$ results a tree $T$
which is also a $\mathsf{TS}_{2}$-reconfiguration graph. Each node $ab$ in $T$
represents a size-$2$ stable set of $G$.

In Section 5, we shifted our focus to some graph properties, namely
$s$-partitedness, planarity, Eulerianity, girth, and the clique’s size, and
provided examples and proofs showing that for some given graph $G$, certain
$\mathsf{TS(G)}$ and $\mathsf{TS}_{k}(G)$ graphs do (not) inherit some
properties from $G$, and vice versa. As the structural properties of
$\mathsf{TS}(G)$ and $\mathsf{TS}_{k}(G)$ have not yet been systematically
investigated, a large number of open questions in this direction can be
obtained by strengthening our results or simply specifying either a graph
class or a property which has not yet been considered.

In Section 6 we showed a way of decomposing a graph that induced a
decomposition of its $\mathsf{TS}_{k}$-reconfiguration graphs. By inverting
the construction we have a way of building larger reconfiguration graphs from
smaller pieces.

In [2] we continue our study of reconfiguration graphs of independent sets by
focusing on the case where these graphs are acyclic.

## Acknowledgements

We thank Yuni Iwamasa, Jesper Jansson, and Dominik Köppl for their useful
comments and discussions. We thank Masahiro Takahashi for his proof of
Proposition 7(a). 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] Alavi, Y., Behzad, M., Erdős, P., Lick, D.R.: Double Vertex Graphs. Journal of Combinatorics, Information & System Sciences 16(1), 37–50 (1991)
  * [2] Avis, D., Hoang, D.A.: A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets. arXiv preprint arXiv:2301.00317 (2023)
  * [3] Bern, M.W., Eppstein, D.: Mesh Generation and Optimal Triangulation. In: Du, D.Z., Hwang, F.K.M. (eds.) Computing in Euclidean Geometry, pp. 23–90. No. 1 in Lecture Notes Series on Computing, World Scientific (1992). https://doi.org/10.1142/9789814355858_0002
  * [4] Bonamy, M., Bousquet, N.: Token Sliding on Chordal Graphs. In: Proceedings of WG 2017. LNCS, vol. 10520, pp. 127–139. Springer (2017). https://doi.org/10.1007/978-3-319-68705-6_10
  * [5] Bonsma, P.S., Kamiński, M., Wrochna, M.: Reconfiguring Independent Sets in Claw-Free Graphs. In: Proceedings of SWAT 2014. LNCS, vol. 8503, pp. 86–97. Springer (2014). https://doi.org/10.1007/978-3-319-08404-6_8
  * [6] Briański, M., Felsner, S., Hodor, J., Micek, P.: Reconfiguring Independent Sets on Interval Graphs. In: Bonchi, F., Puglisi, S.J. (eds.) Proceedings of MFCS 2021. LIPIcs, vol. 202, pp. 23:1–23:14 (2021). https://doi.org/10.4230/LIPIcs.MFCS.2021.23
  * [7] Collins, K.L., Trenk, A.N.: Split Graphs. In: Beineke, L.W., Golumbic, M.C., Wilson, R.J. (eds.) Topics in Algorithmic Graph Theory, p. 189–206. Encyclopedia of Mathematics and its Applications, Cambridge University Press (2021). https://doi.org/10.1017/9781108592376.012
  * [8] Demaine, E.D., Demaine, M.L., Fox-Epstein, E., Hoang, D.A., Ito, T., Ono, H., Otachi, Y., Uehara, R., Yamada, T.: Linear-Time Algorithm for Sliding Tokens on Trees. Theoretical Computer Science 600, 132–142 (2015). https://doi.org/10.1016/j.tcs.2015.07.037
  * [9] Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173. Springer, 5th edn. (2017). https://doi.org/10.1007/978-3-662-53622-3
  * [10] Fox-Epstein, E., Hoang, D.A., Otachi, Y., Uehara, R.: Sliding Token on Bipartite Permutation Graphs. In: Proceedings of ISAAC 2015. LNCS, vol. 9472, pp. 237–247. Springer (2015). https://doi.org/10.1007/978-3-662-48971-0_21
  * [11] van den Heuvel, J.: The Complexity of Change. In: Surveys in Combinatorics, London Mathematical Society Lecture Note Series, vol. 409, pp. 127–160. Cambridge University Press (2013). https://doi.org/10.1017/cbo9781139506748.005
  * [12] Kamiński, M., Medvedev, P., Milanič, M.: Shortest Paths Between Shortest Paths. Theoretical Computer Science 412(39), 5205–5210 (2011). https://doi.org/10.1016/j.tcs.2011.05.021
  * [13] Kamiński, M., Medvedev, P., Milanič, M.: Complexity of Independent Set Reconfigurability Problems. Theoretical Computer Science 439, 9–15 (2012). https://doi.org/10.1016/j.tcs.2012.03.004
  * [14] Lawson, C.L.: Software for C1 Surface Interpolation. In: Mathematical Software. pp. 161–194. Elsevier (1977). https://doi.org/10.1016/B978-0-12-587260-7.50011-X
  * [15] Monroy, R.F., Flores-Peñaloza, D., Huemer, C., Hurtado, F., Urrutia, J., Wood, D.R.: Token Graphs. Graphs and Combinatorics 28(3), 365–380 (2012). https://doi.org/10.1007/s00373-011-1055-9
  * [16] Mynhardt, C., Nasserasr, S.: Reconfiguration of Colourings and Dominating Sets in Graphs. In: Chung, F., Graham, R., Hoffman, F., Mullin, R.C., Hogben, L., West, D.B. (eds.) 50 years of Combinatorics, Graph Theory, and Computing, pp. 171–191. CRC Press, 1st edn. (2019). https://doi.org/10.1201/9780429280092-10
  * [17] Nishimura, N.: Introduction to Reconfiguration. Algorithms 11(4), 52 (2018). https://doi.org/10.3390/a11040052
  * [18] Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, 1st edn. (1985). https://doi.org/10.1007/978-1-4612-1098-6

##  Appendix 0.A Connectivity and Diameter of $\mathsf{TS}_{k}(G)$ for
Specific Graph Classes

For certain graph $G$, Table 3 includes some properties of the connectivity
and diameter of $\mathsf{TS}_{k}(G)$ that can be derived from known results.

Table 3: Connectivity and diameter of $\mathsf{TS}_{k}(G)$ ($2\leq k\leq\alpha(G)$). Here $n=|V(G)|$. $G$ (simple, connected) | $\mathsf{TS}_{k}(G)(1\leq k\leq\alpha(G))$ | Ref.
---|---|---
always connected? | diameter
1 | perfect | no | $O(2^{n})$ | [12, 13]
2 | even-hole-free | yes, if $k=\alpha(G)$ |  $O(n)$, if $k=\alpha(G)$
3 |  $P_{4}$-free | no | $O(n^{2})$
4 | claw-free | yes | $O(\text{poly}(n))$ | [5]
5 | tree | no | $O(n^{2})$ | [8]
6 | path | yes
7 | bipartite permutation | no | $O(n^{2})$ | [10]
8 | interval | no | $O(kn^{2})$ | [4, 6]

  * 1.

In [13], Kamiński et al. showed the $\mathtt{PSPACE}$-completeness of
Independent Set Reconfiguration (ISR) under any of $\mathsf{TS},\mathsf{TJ}$,
or $\mathsf{TAR}$ when the input graph is a perfect graph. Combining their
reduction from Shortest Path Reconfiguration (SPR) and an example of a
reconfiguration graph of SPR having exponentially large diameter in the size
of the input graph [12] gives us an example of $\mathsf{TS}_{k}(G)$ with
exponentially large diameter in $n=|V(G)|$.

Observe that one can construct a perfect graph $G$ where $\mathsf{TS}_{k}(G)$
is not connected. For instance, take $G$ as the star $K_{1,n}$. Then, for
$n\geq k+1$, $\mathsf{TS}_{k}(G)$ is not connected. This also holds for other
graph classes such as $P_{4}$-free graphs, trees, bipartite permutation
graphs, and interval graphs.

  * 2.

They also showed that $\mathsf{TJ}_{k}(G)$ is connected and its diameter is
$O(n)$ when $G$ is a connected even-hole-free graph. Observe that when
$k=\alpha(G)$, we have $\mathsf{TJ}_{k}(G)\simeq\mathsf{TS}_{k}(G)$.

  * 3.

Kamiński et al. [13] designed a linear-time algorithm that decides whether
there is a path between $I,J\in\mathsf{TS}_{k}(G)$, and if yes, outputs a
shortest one, where $G$ is $P_{4}$-free. One can verify that their algorithm
indeed outputs a path in $\mathsf{TS}_{k}(G)$ of length $O(n^{2})$.

  * 4.

Bonsma et al. [5] show that when $G$ is a connected claw-free graph,
$\mathsf{TS}_{k}(G)$ is always connected, and they provided a polynomial-time
algorithm for outputting a path between any pair $I,J\in\mathsf{TS}_{k}(G)$.

  * 5–6.

Demaine et al. [8] designed a linear-time algorithm for deciding, whether
there is a path between $I,J\in\mathsf{TS}_{k}(G)$, and if yes, output a path
of length $O(n^{2})$, provided that $G$ is a tree. They also gave an example
of an instance $(G,I,J)$ where $G$ is a path and the length of a shortest path
between $I,J\in\mathsf{TS}_{k}(G)$ is $\Omega(n^{2})$.

  * 7.

Fox-Epstein et al. [10] designed a cubic-time algorithm for deciding, whether
there is a path between $I,J\in\mathsf{TS}_{k}(G)$, and if yes, output a path
of length $O(n^{2})$, provided that $G$ is a bipartite permutation graph.

  * 8.

Bonamy and Bousquet [4] designed a polynomial-time algorithm for deciding
whether $\mathsf{TS}_{k}(G)$ is connected when $G$ is an interval graph.
However, they did not provide any estimation on its diameter. Motivated by
this question, Briański et al. [6] recently showed that the diameter of
$\mathsf{TS}_{k}(G)$ is $O(kn^{2})$.