Advisor(s)

Mark Ramras

Contributor(s)

Egon Schulte, Brigitte Servatius, Andrei V. Zelevinsky

Date of Award

2009

Date Accepted

4-2009

Degree Grantor

Northeastern University

Degree Level

Ph.D.

Degree Name

Doctor of Philosophy

Department or Academic Unit

College of Arts and Sciences. Department of Mathematics.

Keywords

Colex order, Greedy algorithm, Hamiltonian cycle, Hypercube

Subject Categories

Hypercube, Graphs

Disciplines

Mathematics

Abstract

The hypercube, in its various forms, has been greatly studied over the last sixty years. Our research involving this graph primarily uses a concept of ""levels"" in this graph, where the i-th level of the n-cube is defined as the set of all vertices of weight i. When examining more than one level, we are, in fact, just viewing the induced subgraph whose vertex set consists of those vertices of desired weights. We begin by considering the vertices of any two consecutive levels on the lower half of the cube sorted in colexicographic order and obtain a perfect matching of initial segments of maximum size. This leads to the long-standing open question of finding a Hamiltonian cycle in the middle two levels of the n-cube, where n is odd. For, if we could find two such disjoint complete matchings on these levels, we might be able to extend the results to a Hamiltonian cycle. We attempted to answer this question by considering the Johnson graph whose vertices are those from one level and edges are formed between vertices of distance two. We then form a Hamiltonian cycle where adjacent vertices in the cycle are at distance two from one another in the middle levels subgraph. The chapter concludes with determining the automorphism group of the Johnson graph. We then develop a type of greedy matching in which the vertices of any two consecutive levels are sorted, independently, in colexicographic order. Some specific matching results are given, as well as a second method of generating a matching, the reverse greedy algorithm. We switch our view to that of lexicographic orderings with the original algorithm and prove that, regardless of the method or ordering used, all three matching produced are equal. The key result follows from this work: a complete saturation of the middle two levels of an odd cube, again independent of the algorithm or ordering chosen. The structure of the automorphism group is the basis for the next section on transitivity, whose starting point is the following question: given two m-sets of vertices whose pairwise distances in the first set are the same as those in the second set, respectively, is there an automorphism that maps each member of the first set to a designated member of the second set? While this answer is affirmative for m=1, 2, 3, we produce a counterexample to show that the n-cube is not distance m-transitive for m>3. We then define two new type of transitivity, intersection m-transitivity and Delta m-transitivity, and show, not only that these new parameters are equivalent, but also that Q_n has these properties. After finding the automorphism group of the middle two levels of an odd dimensional cube, we extend these transitivity definitions to this restricted level graph and draw similar results to those that hold for the whole cube. We conclude our paper with the definition of a supergraph of the n-dimensional hypercube, Q_n*. This new graph maintains the full structure of the underlying hypercube, with the addition of complementary edges: edges that connect a vertex to its complement. Many parameters for this supergraph are established, including the size of its diameter, maximum connectivity and colorability. We also note how the same conclusions for the three types of transitivity discussed previously still hold for this supergraph.

Document Type

Dissertation

Rights Holder

Elizabeth A. Donovan


View Full Text

Click button above to open, or right-click to save.

Included in

Mathematics Commons

Share

COinS