The realisability of γ-graphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2017-08-14
Authors/Contributors
Abstract
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.
Document
Identifier
etd10343
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Jedwab, Jonathan
Member of collection
Attachment Size
etd10343_ADyck.pdf 562.8 KB