TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs
From MaRDI portal
Publication:6361181
DOI10.1007/978-3-030-86593-1_8arXiv2102.10568MaRDI QIDQ6361181
Nicolas Bousquet, Alice Joffard
Publication date: 21 February 2021
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=<D_1:=D_s,...,D_l:=D_t> of dominating sets of G such that for any two consecutive dominating sets D_r and D_{r+1} with r<t, D_{r+1}=(D_r u) U v, where uv is an edge of G. In a recent paper, Bonamy et al studied this problem and raised the following questions: what is the complexity of this problem on circular arc graphs? On circle graphs? In this paper, we answer both questions by proving that the problem is polynomial on circular-arc graphs and PSPACE-complete on circle graphs.
This page was built for publication: TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6361181)
