The realisability of γ-graphs

The γ-graph γ·G of a graph G is the graph whose vertices are labelled by the minimum dominating sets of G, in which two vertices are adjacent when their corresponding minimum dominating sets differ in exactly one element. We give an explicit construction of a graph having an arbitrary prescribed set of minimum dominating sets. We show as a corollary that "labellable implies realisable for γ-graphs": if the vertices of a graph H can be labelled by distinct sets of the same size, in a manner consistent with the adjacency condition for γ-graphs, then H = γ·G for some graph G. We use this corollary to extend the classification of γ-graphs, due to Lakshmanan and Vijayakumar, to all graphs on at most six vertices. We also use this corollary to relate γ-graphs both to induced subgraphs of Johnson graphs and to optimal dominating codes in graphs.