Source author record

Alice Joffard

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Computational Complexity Data Structures and Algorithms math.CO

Catalog footprint

Research overview

2works

4topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

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

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.

preprint2020arXiv

Linear transformations between dominating sets in the TAR-model

Given a graph $G$ and an integer $k$ , a token addition and removal ({\sf TAR} for short) reconfiguration sequence between two dominating sets $D_{\sf s}$ and $D_{\sf t}$ of size at most $k$ is a sequence $S= \langle D_0 = D_{\sf s}, D_1 \ldots, D_\ell = D_{\sf t} \rangle$ of dominating sets of $G$ such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than $k$ . We first improve a result of Haas and Seyffarth, by showing that if $k=Γ(G)+α(G)-1$ (where $Γ(G)$ is the maximum size of a minimal dominating set and $α(G)$ the maximum size of an independent set), then there exists a linear {\sf TAR} reconfiguration sequence between any pair of dominating sets. We then improve these results on several graph classes by showing that the same holds for $K_{\ell}$ -minor free graph as long as $k \ge Γ(G)+O(\ell \sqrt{\log \ell})$ and for planar graphs whenever $k \ge Γ(G)+3$ . Finally, we show that if $k=Γ(G)+tw(G)+1$ , then there also exists a linear transformation between any pair of dominating sets.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.