On reconfiguration graphs of independent sets under token sliding

DOI10.1007/S00373-023-02644-WMaRDI QIDQ6115427zbMATH OpenOpenAlexFDO

Authors David Avis, Duc A. Hoang

Publication date 12 July 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.16861

zbMATH Keywords

geometric graphindependent setrealizabilityreconfiguration graphstructuretoken sliding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

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 $mathsfTS$- ($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 $mathcalG$ (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 $mathcalP$ (including $s$-partitedness, planarity, Eulerianity, girth, and the clique's size), whether the corresponding $mathsfTS$- ($mathsf{TS}_k$-) reconfiguration graph of $G$ also satisfies $mathcalP$, and vice versa. Additionally, we give a decomposition result for splitting a $mathsf{TS}_k$-reconfiguration graph into smaller pieces.

Recommendations

• Token sliding on split graphs
• Token sliding on split graphs
• Complexity of independent set reconfigurability problems
• Parameterized complexity of independent set reconfiguration problems
• Token sliding on chordal graphs

Cites work

• Complexity of independent set reconfigurability problems
• Graph theory
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 146670 (Why is no real title available?)
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• Introduction to reconfiguration
• Linear-time algorithm for sliding tokens on trees
• Reconfiguring independent sets in claw-free graphs
• Reconfiguring Independent Sets on Interval Graphs
• Shortest paths between shortest paths
• Sliding token on bipartite permutation graphs
• Split graphs
• The complexity of change
• Token graphs
• Token sliding on chordal graphs

Cited in

(7)

• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Token sliding on split graphs
• Extremal independent set reconfiguration
• Reconfiguring Independent Sets on Interval Graphs
• Gated independence in graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• On finding short reconfiguration sequences between independent sets

This page was built for publication: On reconfiguration graphs of independent sets under token sliding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115427)