ABSTRACT
In graph theory, reconfiguration is concerned with relationships among solutions to a given problem for a specific graph. The reconfiguration of one solution into another occurs via a sequence of steps, defined according to a predetermined rule, such that each step produces an intermediate solution to the problem. When the reconfiguration graph associated with a specific structure is connected, Markov chain simulation can be used to achieve approximate counting. The term “combinatorial Gray code” refers to a list of combinatorial objects so that successive objects differ in some prescribed minimal way. It generalises Gray codes, which are lists of fixed length binary strings such that successive strings differ by exactly one bit. One of the best studied reconfiguration graphs is the k-colouring graph. Other types of domination reconfiguration graphs are defined using only sets of cardinalities equal to a given domination parameter.
