Publication Date
2016
Document Type
Thesis
Committee Members
Yuqing Chen (Committee Member), Daniel Slilaty (Advisor), Xiangqian Zhou (Committee Member)
Degree Name
Master of Science (MS)
Abstract
A self-complementary graph G is a subgraph of the complete graph K_n that is isomorphic to its complement. A self-complementary graph can be thought of as an edge 2-coloring of K_n that admits a color-switching automorphism. An automorphism of K_n that is color-switching for some edge 2-coloring is called a complementing automorphism. Complementing automorphisms for K_n have been characterized in the past by such authors as Sachs and Ringel. We are interested in extending this notion of self-complementary to other highly symmetric families of graphs; namely, the hypercube Q_n and its dual graph, the hyperoctahedron O_n. To that end, we develop a characterization of the automorphism group of these graphs and use it to prove necessary and sufficient conditions for an automorphism to be complementing. Finally, we use these theorems to construct a computer search algorithm which finds all self-complementary graphs in Q_n and O_n up to isomorphism for n=2,3,4.
Page Count
48
Department or Program
Department of Mathematics and Statistics
Year Degree Awarded
2016
Copyright
Copyright 2016, all rights reserved. My ETD will be available under the "Fair Use" terms of copyright law.
