Almost Self-Complementary 3-Uniform Hypergraphs

Abstract

It is known that self-complementary 3-uniform hypergraphs on n vertices exist if and only if n is congruent to 0, 1 or 2 modulo 4. In this paper we define an almost self-complementary 3-uniform hypergraph on n vertices and prove that it exists if and only if n is congruent to 3 modulo 4. The structure of corresponding complementing permutation is also analyzed. Further, we prove that there does not exist a regular almost self-complementary 3-uniform hypergraph on n vertices where n is congruent to 3 modulo 4, and it is proved that there exist a quasi regular almost self-complementary 3-uniform hypergraph on n vertices where n is congruent to 3 modulo 4.

Keywords

• uniform hypergraph
• self-complementary hypergraph
• almost complete 3-uniform hypergraph
• almost self-complementary hypergraph
• quasi regular hypergraph
• 05c65