
arXiv: 2301.00317
We continue the study of Token Sliding (reconfiguration) graphs of independent sets initiated by the authors in an earlier paper [Graphs Comb. 39.3, 59, 2023]. 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 in 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\)-graphs.
FOS: Computer and information sciences, 05C05, 05C99, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, 05C05, 05C99, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
