Publication Date


Document Type


Committee Members

Yuqing Chen (Committee Member), Daniel Slilaty (Advisor), Xiangqian Zhou (Committee Member)

Degree Name

Master of Science (MS)


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


Department or Program

Department of Mathematics and Statistics

Year Degree Awarded