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 set minor-closed graph class reconfiguration toroidal graph

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^{'}

in

G

, and a non-negative integer

k

, the set

D

is said to

k

-transform to

D^{'}

if there is a sequence

D_{0}, l d o t s, D_{e} l l

of dominating sets in

G

such that

D = D_{0}

,

D^{'} = D_{e} l l

,

| D_{i} | l e q k

for every

i i n 0, 1, l d o t s, e l l

, and

D_{i}

arises from

D_{i - 1}

by adding or removing one vertex for every

i i n 1, l d o t s, e l l

. 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^{'}

in

G

such that

D

k

-transforms to

D^{'}

only if

k g e q m a x | D |, | D^{'} | + c s q r t n

. Conversely, for every hereditary class

c a l G

that has balanced separators of order

n m a p s t o n^{a} l p h a

for some

a l p h a < 1

, we prove that there is some positive constant

C

such that, if

G

is a graph in

c a l G

of order

n

, and

D

and

D^{'}

are two dominating sets in

G

, then

D

k

-transforms to

D^{'}

for

k = m a x | D |, | D^{'} | + l f l o o r C n^{a} l p h a f l o o r

.

Review text

Let \(G=(V,E)\) be a graph. A set \(S\subseteq V(G)\) is a dominating set, if every vertex in \(V(G)\backslash S\) is adjacent to at least one vertex in \(S\). Given dominating sets \(S\) and \(T\), is there a sequence of dominating sets \(S_0 = S_1, S_2,\ldots, S_k = T\) such that each \(S_{i+1}\) is obtained from \(S_i\) by deleting or adding a single vertex? If the answer is yes, then \(S\) is said to \(k\)-transform to \(T\). A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. A graph \(G\) of order \(n\) has a balanced separator of order \(k\) if there is a set \(D\) of at most \(k\) vertices of \(G\) as well as a partition of the vertex set \(V(G)\) of \(G\) into three sets \(D,A\) and \(B\) such that \(|A|,|B|\leq \frac{2n}{3}\), and \(G\) contains no edge between \(A\) and \(B\). The authors prove that there is some positive constant \(c\) and there are toroidal graphs \(G\) of arbitrarily large order \(n\), and two minimum dominating sets \(S\) and \(T\) in \(G\) such that \(S\) \(k\)-transforms to \(T\) only if \(k \geq \max\{|S|,|T|\}+c\sqrt{n}\). Conversely, for every hereditary class \(\mathcal{G}\) that has balanced separators of order \(n\mapsto n^{\alpha}\) for some \(\alpha<1\), they prove that there is some positive constant \(C\) such that, if \(G\) is a graph in \(\mathcal{G}\) of order \(n\), and \(S\) and \(T\) are two dominating sets in \(G\), then \(S\) \(k\)-transforms to \(T\) for \(k = \max\{|S|,|T|\}+\lfloor Cn^{\alpha}\rfloor\).

Recommendations

Cites work

Cited in

(3)

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)