Self-Complementary Hypergraphs

WinnSpace/Manakin Repository

Self-Complementary Hypergraphs

Show simple item record

dc.contributor.author Gosselin, Shonda
dc.date.accessioned 2010-12-17T17:45:01Z
dc.date.available 2010-12-17T17:45:01Z
dc.date.issued 2009
dc.identifier.uri http://hdl.handle.net/10680/292
dc.description.abstract In this thesis, we survey the current research into self-complementary hypergraphs, and present several new results. We characterize the cycle type of the permutations on n elements with order equal to a power of 2 which are k-complementing. The k-complementing permutations map the edges of a k-uniform hypergraph to the edges of its complement. This yields a test to determine whether a finite permutation is a k-complementing permutation, and an algorithm for generating all self-complementary k-uniform hypergraphs of order n, up to isomorphism, for feasible n. We also obtain an alternative description of the known necessary and sufficient conditions on the order of a self-complementary k-uniform hypergraph in terms of the binary representation of k. We examine the orders of t-subset-regular self-complementary uniform hyper- graphs. These form examples of large sets of two isomorphic t-designs. We restate the known necessary conditions on the order of these structures in terms of the binary representation of the rank k, and we construct 1-subset-regular self-complementary uniform hypergraphs to prove that these necessary conditions are sufficient for all ranks k in the case where t = 1. We construct vertex transitive self-complementary k-hypergraphs of order n for all integers n which satisfy the known necessary conditions due to Potocnik and Sajna, and consequently prove that these necessary conditions are also sufficient. We also generalize Potocnik and Sajna's necessary conditions on the order of a vertex transitive self-complementary uniform hypergraph for certain ranks k to give neces- sary conditions on the order of these structures when they are t-fold-transitive. In addition, we use Burnside's characterization of transitive groups of prime degree to determine the group of automorphisms and antimorphisms of certain vertex transitive self-complementary k-uniform hypergraphs of prime order, and we present an algorithm to generate all such hypergraphs. Finally, we examine the orders of self-complementary non-uniform hypergraphs, including the cases where these structures are t-subset-regular or t-fold-transitive. We find necessary conditions on the order of these structures, and we present constructions to show that in certain cases these necessary conditions are sufficient. en_US
dc.description.sponsorship University of Ottawa en_US
dc.language.iso en en_US
dc.publisher University of Ottawa en_US
dc.subject.other Self-complementary graphs
dc.subject.other k-uniform Hypergraphs
dc.title Self-Complementary Hypergraphs en_US
dc.type Thesis en_US

Files in this item

Files Size Format View
PhD thesis Gosselin UO FINAL.pdf 627.2Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search WinnSpace


Advanced Search

Browse

My Account