TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs

2021/02/21 by Nicolás Bousquet, Bousquet, Nicolas, Alice Joffard +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems

paper · doi:10.48550/arxiv.2102.10568

openalex publication_date 2021/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the dominating set reconfiguration problem with the token sliding rule. It consists, given a graph G=(V,E) and two dominating sets D_s and D_t of G, in determining if there exists a sequence S= of dominating sets of G such that for any two consecutive dominating sets D_r and D_r+1 with r

Related

• Dominating sets reconfiguration under token sliding
• Shortest Dominating Set Reconfiguration under Token Sliding
• The tape reconfiguration problem and its consequences for dominating set reconfiguration
• Reconfiguration graphs for minimal domination sets
• Linear transformations between dominating sets in the TAR-model