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.
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Jedwab, Jonathan
Member of collection