## 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

 dc.contributor.author Al Fran, Howida Adel dc.date.accessioned 2018-01-28T22:07:39Z dc.date.available 2018-01-28T22:07:39Z dc.date.issued 2017 dc.description.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. en_US dc.identifier.uri http://hdl.handle.net/10179/12742 dc.language.iso en en_US dc.publisher Massey University en_US dc.rights The Author en_US dc.subject Trees (Graph theory) en_US dc.subject Graph theory en_US dc.subject Research Subject Categories::MATHEMATICS en_US dc.title 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 en_US dc.type Thesis en_US massey.contributor.author Al Fran, Howida thesis.degree.discipline Mathematics en_US thesis.degree.grantor Massey University en_US thesis.degree.level Doctoral en_US thesis.degree.name Doctor of Philosophy (PhD) en_US
##### Original bundle
Now showing 1 - 2 of 2
Loading...
Name:
01_front.pdf
Size:
113.97 KB
Format:
Adobe Portable Document Format
Description:
Loading...
Name:
02_whole.pdf
Size:
1.07 MB
Format:
Adobe Portable Document Format
Description:
##### License bundle
Now showing 1 - 1 of 1
Loading...
Name:
license.txt
Size:
3.32 KB
Format:
Item-specific license agreed upon to submission
Description: