The existence of bipartite almost self-complementary 3-uniform hypergraphs

L.N. Kamble
C.M. Deshpande
B.P. Athawale

Abstract. An almost self-complementary 3-uniform hypergraph on \(n\) vertices exists if and only if \(n\) is congruent to 3 modulo 4 A hypergraph \(H\) with vertex set \(V\) and edge set \(E\) is called bipartite if \(V\) can be partitioned into two subsets \(V_1\) and \(V_2\) such that \(e\cap V_1\neq \emptyset\) and \(e\cap V_2\neq \emptyset\) for any \(e\in E\). A bipartite self-complementary 3-uniform hypergraph \(H\) with partition \((V_1, V_2)\) of the vertex set \(V\) such that \(|V_1|=m\) and \(|V_2|=n\) exists if and only if either (i) \(m=n\) or (ii) \(m\neq n\) and either \(m\) or \(n\) is congruent to 0 modulo 4 or (iii) \(m\neq n\) and both \(m\) and \(n\) are congruent to 1 or 2 modulo 4. In this paper we define a bipartite almost self-complementary 3-uniform hypergraph \(H\) with partition \((V_1, V_2)\) of a vertex set \(V\) such that \(|V_1|=m\) and \(|V_2|=n\) and find the conditions on \(m\) and \(n\) for a bipartite 3-uniform hypergraph \(H\) to be almost self-complementary. We also prove the existence of bi-regular bipartite almost self-complementary 3-uniform hypergraphs.

Keywords: almost self-complementary 3-uniform hypergraph, bipartite hypergraph, bipartite self-complementary 3-uniform hypergraph, bipartite almost self-complementary 3-uniform hypergraph.

Mathematics Subject Classification: 05C65.

Full text (pdf)