•  
  •  
 

Abstract

The goal of this paper is to study the spanning trees of the 3-cube by understanding their \emph{edge slide graph}. A spanning tree of a graph $G$ is a minimal set of edges that connects all vertices. An edge slide occurs in a spanning tree of the 3-cube when a single edge can be slid across a 2-dimensional face to form another spanning tree. The edge slide graph is the graph whose vertices are the spanning trees, with an edge between two vertices if the spanning trees are related by a single edge slide. This report completely determines the edge slide graph of the 3-cube. The edge slide graph of the 3-cube has twelve components isomorphic to the 4-cube, and three other components, mutually isomorphic, with 64 vertices each. The main result is to determine the structure of the three components that each have 64 vertices and we also describe their symmetries. Some partial results on the 4-cube are also provided.

Author Bio

Lyndal Henden is an undergraduate student at Massey University in Palmerston North, New Zealand. She currently in her third year of study and is double majoring in mathematics and statistics. She plans to pursue a postgraduate degree in statistics after completing her undergraduate studies. The paper, 㤼㸳The Edge Slide Graph of the 3-cube” was written during the summer of 2010-2011 as part of the Institute of Fundamental Sciences Summer Scholarship program with editing continuing into 2011 under the supervision of Dr. Christopher Tuffley.

Download

Share

COinS