Reconfiguring dominating sets in minor-closed graph classes

DOI10.1007/S00373-021-02341-6zbMATH Open1479.05285arXiv2005.13844OpenAlexW3168265398MaRDI QIDQ2053687FDOQ2053687

Authors: Dieter Rautenbach, Johannes Redl 

Publication date: 30 November 2021

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

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$.

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

Recommendations

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

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)

Cites Work

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

Cited In (3)

• Reconfiguring dominating sets in some well-covered and other classes of graphs
• Reconfiguring minimum dominating sets: the \(\gamma\)-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)