|
| | | | |
| | | |
| Stat |
Members: 3665
Articles: 2'599'751
Articles rated: 2609
25 January 2025 |
|
| | | | |
|
Article overview
| |
|
|
A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets | | David Avis
; Duc A. Hoang
; | | Date: |
1 Jan 2023 | | 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. | | Source: | arXiv, 2301.00317 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER