The edge slide graph of the n-dimensional cube : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics at Massey University, Manawatū, New Zealand
Loading...
Date
2017
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
The Author
Abstract
The goal of this thesis is to understand the spanning trees of the n-dimensional cube Qn by
understanding their edge slide graph. An edge slide is a move that “slides” an edge of a spanning
tree of Qn across a two-dimensional face, and the edge slide graph is the graph on the spanning
trees of Qn with an edge between two trees if they are connected by an edge slide. Edge slides
are a restricted form of an edge move, in which the edges involved in the move are constrained
by the structure of Qn, and the edge slide graph is a subgraph of the tree graph of Qn given by
edge moves.
The signature of a spanning tree of Qn is the n-tuple (a1; : : : ; an), where ai is the number of
edges in the ith direction. The signature of a tree is invariant under edge slides and is therefore
constant on connected components. We say that a signature is connected if the trees with that
signature lie in a single connected component, and disconnected otherwise. The goal of this
research is to determine which signatures are connected.
Signatures can be naturally classified as reducible or irreducible, with the reducible signatures
being further divided into strictly reducible and quasi-irreducible signatures. We determine
necessary and sufficient conditions for (a1; : : : ; an) to be a signature of Qn, and show that
strictly reducible signatures are disconnected. We conjecture that strict reducibility is the only
obstruction to connectivity, and present substantial partial progress towards an inductive proof
of this conjecture. In particular, we reduce the inductive step to the problem of proving under
the inductive hypothesis that every irreducible signature has a “splitting signature” for which
the upright trees with that signature and splitting signature all lie in the same component. We
establish this step for certain classes of signatures, but at present are unable to complete it for
all.
Hall’s Theorem plays an important role throughout the work, both in characterising the
signatures, and in proving the existence of certain trees used in the arguments.
Description
Keywords
Trees (Graph theory), Graph theory, Research Subject Categories::MATHEMATICS