Atlantic Graph Theory Seminar: Margaret-Ellen Messinger (Mount Allison University)

Reconfiguration for Dominating Sets

Given a problem and a set of feasible solutions to that problem, the associated  reconfiguration problem involves determining whether one feasible solution to the original problem can be transformed to a different feasible solution through a sequence of allowable moves, with the condition that the intermediate stages are also feasible solutions.  Any reconfiguration problem can be modelled with a  reconfiguration graph, where the vertices represent feasible solutions and two vertices are adjacent if and only if the corresponding feasible solutions can be transformed to each other via em one allowable move.

The domination reconfiguration graph of a graph $G$, denoted ${\mathcal D}(G)$, has a vertex corresponding to each dominating set of $G$ and two vertices of ${\mathcal D}(G)$ are adjacent if and only if the corresponding dominating sets differ by the deletion or addition of a single vertex.  We are interested in properties of domination reconfiguration graphs. For example, it is easy to see that they are always connected and bipartite.  We can also characterize exactly which graphs yield domination reconfiguration graphs with Eulerian circuits.  While none has a Hamilton cycle, we explore families of graphs whose reconfiguration graphs have Hamilton paths.

Join Zoom Meeting: link