Reconfiguring dominating sets in minor-closed graph classes

DOI10.1007/S00373-021-02341-6MaRDI QIDQ2053687zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Johannes Redl

Publication date 30 November 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

dominating settoroidal graphreconfigurationminor-closed graph class

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph minors (05C83)

Abstract: For a graph $G$, two dominating sets $D$ and $D^{\prime }$ in $G$, and a non-negative integer $k$, the set $D$ is said to $k$-transform to $D^{\prime }$ if there is a sequence $D_0,ldots,D_{e}ll$ of dominating sets in $G$ such that $D=D_0$, $D^{\prime }=D_{e}ll$, $|D_i|leqk$ for every $iin0,1,ldots,ell$, and $D_i$ arises from $D_{i-1}$ by adding or removing one vertex for every $iin1,ldots,ell$. We prove that there is some positive constant $c$ and there are toroidal graphs $G$ of arbitrarily large order $n$, and two minimum dominating sets $D$ and $D^{\prime }$ in $G$ such that $D$ $k$-transforms to $D^{\prime }$ only if $kgeqmax|D|,|D^{\prime }|+csqrtn$. Conversely, for every hereditary class $calG$ that has balanced separators of order $nmapsto{n}^{a}lpha$ for some $alpha<1$, we prove that there is some positive constant $C$ such that, if $G$ is a graph in $calG$ of order $n$, and $D$ and $D^{\prime }$ are two dominating sets in $G$, then $D$ $k$-transforms to $D^{\prime }$ for $k=max|D|,|D^{\prime }|+lfloorC{n}^{a}lphafloor$.

Recommendations

• The complexity of dominating set reconfiguration
• The complexity of dominating set reconfiguration
• Dominating sets reconfiguration under token sliding

Cites work

• A Separator Theorem for Planar Graphs
• A separator theorem for graphs of bounded genus
• An Isoperimetric Inequality on the Discrete Torus
• Introduction to reconfiguration
• On the structure of dominating graphs
• The \(k\)-dominating graph
• The complexity of dominating set reconfiguration
• The domination number of grids

Cited in

(3)

• Reconfiguring dominating sets in some well-covered and other classes of graphs
• Reconfiguring minimum dominating sets: the -graph of a tree
• Reconfiguration graphs for dominating sets

This page was built for publication: Reconfiguring dominating sets in minor-closed graph classes

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