Reconfiguration of dominating sets

Akira Suzuki (), Amer E. Mouawad () and Naomi Nishimura ()
Additional contact information
Akira Suzuki: Tohoku University
Amer E. Mouawad: University of Waterloo
Naomi Nishimura: University of Waterloo

Journal of Combinatorial Optimization, 2016, vol. 32, issue 4, No 12, 1182-1195

Abstract: Abstract We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph G is a set S of vertices such that each vertex is either in S or has a neighbour in S. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions s and t such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of k, we consider properties of $$D_k(G)$$ D k ( G ) , the graph consisting of a node for each dominating set of size at most k and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that $$D_{\varGamma (G)+1}(G)$$ D Γ ( G ) + 1 ( G ) is not necessarily connected, for $$\varGamma (G)$$ Γ ( G ) the maximum cardinality of a minimal dominating set in G. The result holds even when graphs are constrained to be planar, of bounded tree-width, or b-partite for $$b \ge 3$$ b ≥ 3 . Moreover, we construct an infinite family of graphs such that $$D_{\gamma (G)+1}(G)$$ D γ ( G ) + 1 ( G ) has exponential diameter, for $$\gamma (G)$$ γ ( G ) the minimum size of a dominating set. On the positive side, we show that $$D_{n-\mu }(G)$$ D n - μ ( G ) is connected and of linear diameter for any graph G on n vertices with a matching of size at least $$\mu +1$$ μ + 1 .

Keywords: Dominating set; Reconfiguration; Reconfiguration graph; Connectivity; Diameter; Solution space (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9947-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:4:d:10.1007_s10878-015-9947-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9947-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().