Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: J Comb Optim

Search In Journal Title:

Abbravation: Journal of Combinatorial Optimization

Search In Journal Abbravation:

Publisher

Springer US

Search In Publisher:

DOI

10.1007/978-3-319-07148-0_14

Search In DOI:

ISSN

1573-2886

Search In ISSN:
Search In Title Of Papers:

Reconfiguration of dominating sets

Authors: Akira Suzuki Amer E Mouawad Naomi Nishimura
Publish Date: 2015/08/28
Volume: 32, Issue: 4, Pages: 1182-1195
PDF Link

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 kG 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+1G is not necessarily connected for varGamma G the maximum cardinality of a minimal dominating set in G The result holds even when graphs are constrained to be planar of bounded treewidth or bpartite for b ge 3 Moreover we construct an infinite family of graphs such that D gamma G+1G has exponential diameter for gamma G the minimum size of a dominating set On the positive side we show that D nmu G is connected and of linear diameter for any graph G on n vertices with a matching of size at least mu +1

Keywords:

References

.
Search In Abstract Of Papers:
Other Papers In This Journal:
  1. A Lagrangian bound for many-to-many assignment problems
  2. New bounds for the balloon popping problem
  3. An exact algorithm for the maximum probabilistic clique problem
  4. A two-stage method for member selection of emergency medical service
  5. Budget-constrained minimum cost flows
  6. On the complexity of partitioning a graph into a few connected subgraphs
  7. Median problems with positive and negative weights on cycles and cacti
  8. The unconstrained binary quadratic programming problem: a survey
  9. Multiple L ( j ,1)-labeling of the triangular lattice
  10. A hybrid algorithm based on variable neighbourhood for the strip packing problem
  11. Penalty guided genetic search for redundancy optimization in multi-state series-parallel power system
  12. Evaluation performance of genetic algorithm and tabu search algorithm for solving the Max-RWA problem in all-optical networks
  13. Modified differential evolution with self-adaptive parameters method
  14. Extremal polyomino chains with respect to general Randić index
  15. The weighted link ring loading problem
  16. A new recombination lower bound and the minimum perfect phylogenetic forest problem
  17. Optimization of loss-balanced multicast in all-optical WDM networks
  18. Approximate event detection over multi-modal sensing data
  19. Mobile facility location: combinatorial filtering via weighted occupancy
  20. Bounded information dissemination in multi-channel wireless networks
  21. Total coloring of planar graphs without adjacent short cycles
  22. Disjunctive total domination in graphs
  23. A quadratic lower bound for colourful simplicial depth
Search Result: