A hypergraph \(H\) is said to be \(r\)-partite \(r\)-uniform if its vertex set \(V\) can be partitioned into non-empty sets \(V_1, V_2, \cdots, V_r\) so that every edge in the edge set \(E(H)\), consists of precisely one vertex from each set \(V_i\), \(i=1,2,\cdots,r\). It is denoted as \(H^r(V_1,V_2,\cdots,V_r)\) or \(H^r_{(n_1,n_2,\cdots,n_r)}\) if \(|V_i|=n_i\) for \(i=1,2,\cdots,r\). There exists an \(r\)-partite self-complementary \(r\)-uniform hypergraph \(H^r(V_1,V_2,\cdots,V_r)\) where \(|V_i|=n_i\) for \(i=1,2,\cdots,r\) if and only if at least one of \(n_1,n_2,\cdots,n_r\) is even. And there exists an \(r\)-partite almost self-complementary \(r\)-uniform hypergraph \(H^r(V_1, V_2,\cdots,V_r)\) where \(|V_i|=n_i\) for \(i=1,2,\cdots,r\) if and only if \(n_1,n_2,\cdots,n_r\) are odd. In this paper, we prove the existence of regular \(3\)-partite self-complementary \(3\)-uniform hypergraphs. Further we prove there does not exist a regular \(3\)-partite almost self-complementary \(3\)-uniform hypergraph.
Let \(V\) be a finite set with \(n\) vertices. By \(V\choose k\) we denote the set of all \(k\)-subsets of \(V\). A \(k\)-uniform hypergraph is a pair \(H = (V ; E)\), where \(E \subset {V\choose k}\). \(V\) is called a vertex set, and \(E\) an edge set of \(H\). Two \(k\)-uniform hypergraphs \(H = (V ; E)\) and \(H' = (V'; E')\) are isomorphic if there is a bijection \(\sigma: V \rightarrow V'\) such that \(\sigma\) induces a bijection of \(E\) onto \(E'\). If \(H = (V ; E)\) is isomorphic to \(H' = (V ; {V\choose k} -E)\), then \(H\) is called a self-complementary \(k\)-uniform hypergraph. Every permutation \(\pi : V \rightarrow V\) which induces a bijection \(\pi': E \rightarrow {V\choose k} -E\) is called a self-complementing permutation.
Syma\(\acute{n}\)ski and Wojda [11],[12], Wojda [13] and Gosselin [2], independently characterized \(n\) and \(k\) for which there exist \(k\)-uniform self-complementary hypergraphs of order \(n\). Poto\(\breve{c}\)nik and \(\breve{S}\)ajana [10] proved the existence of regular self-complementary \(3\)-uniform hypergraphs. Gosselin [3] has characterized all \(n\) and \(k\) for which there exists a regular \(k\)-uniform self-complementary hypergraph of order \(n\). In [4], Kamble et al. studied the existence of quasi-regular and bi-regular self-complementary \(3\)-uniform hypergraphs. In [5], the existence of an almost self-complementary \(3\)-uniform hypergraphs is proved and in [14], Wojda generalized these results for \(k\)-uniform hypergraphs. In [6], a bipartite 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\) is studied. In [7], Kamble et al. proved the conditions on \(m\) and \(n\) for a bipartite self-complementary \(3\)-uniform hypergraph \(H^3(V_1,V_2)\) to be regular and quasi-regular. In [9], bipartite almost self-complementary \(3\)-uniform hypergraphs are studied. In [8], \(r\)-partite self-complementary and almost self-complementary \(r\)-uniform hypergraphs are defined.
In this paper the authors proved necessary and sufficient conditions for the existence of \(r\)-partite self-complementary and almost self-complementary \(r\)-uniform hypergraphs. Further they have characterized the cycle structure of their complementing permutations.
The paper is organized as follows: In Section 2, we study the existence of regular and quasi-regular \(2\)-partite self-complementary and almost self-complementary \(2\)-uniform hypergraphs and in Section 3, we extended these results for \(3\)-partite self-complementary and almost self-complementary \(3\)-uniform hypergraphs.
Definition 2.1(\(r\)-partite \(r\)-uniform Hypergraph). A hypergraph \(H\) is said to be \(r\)-partite \(r\)-uniform if its vertex set \(V\) can be partitioned into non-empty sets \(V_1, V_2,\cdots , V_r\) so that every edge in the edge set \(E(H)\) consists of precisely one vertex from each set \(V_i\), \(i=1,2,\cdots,r\).
An \(r\)-partite \(r\)-uniform hypergraph is denoted as \(H^r(V_1,V_2,\cdots,V_r)\) or \(H^r_{(n_1,n_2,\cdots,n_r)}\) if \(|V_i|=n_i\) for \(i=1,2,\cdots, r\). A \(2\)-partite \(2\)-uniform hypergraph is nothing but a bipartite graph.
Definition 2.2(Complete \(r\)-partite \(r\)-uniform hypergraph).An \(r\)-partite \(r\)-uniform hypergraph \(H\) with the vertex set \(\displaystyle V=\bigcup_{i=1}^r V_i,~ V_i\cap V_j=\phi,~\forall~ i\neq j\) and the edge set \(E=\{e: e\subset V, |e|=r\) and \(e\cap V_i\neq \phi,\) for \(i=1,2,\cdots,r\}\) is called a complete \(r\)-partite \(r\)-uniform hypergraph.
A complete \(r\)-partite \(r\)-uniform hypergraph is denoted as \(K^r(V_1,V_2,\cdots,V_r)\) or \(K^r_{(n_1,n_2,\cdots,n_r)}\) if \(|V_i|=n_i\) for \(i=1,2,\cdots, r\). We observe that, the total number of edges in \(K^r_{(n_1,n_2,\cdots,n_r)}\) is \(\displaystyle \prod _{i=1}^r n_i\).
Given an \(r\)-partite \(r\)-uniform hypergraph \(H=H^r(V_1,V_2,\cdots,\) \(V_r)\), its \(r\)-partite complement is the \(r\)-partite \(r\)-uniform hypergraph \(\bar{H}=\bar{H}^r(V_1,V_2,\cdots,V_r)\) where \(V(\bar{H})=V(H)\) and \(E(\bar{H})=E(K^r(V_1,V_2,\cdots,V_r))-E(H)\).
\(\bar{H}\) is said to be complement of \(H\) with respect to \(K^r(V_1,V_2,\cdots,V_r)\). An \(r\)-partite \(r\)-uniform hypergraph \(H=H^r(V_1,V_2,\cdots,V_r)=H^r(V)\) is said to be self-complementary if it is isomorphic to its \(r\)-partite complement \(\bar{H}=\bar{H}^r(V_1,V_2,\cdots,V_r)=\bar{H}^r(V)\), that is, there exists a bijection \(\sigma:V\rightarrow V\) such that \(e\) is an edge in \(H\) if and only if \(\sigma(e)\) is an edge in \(\bar{H}\).
We use the short form “\(r\)-psc” for the \(r\)-partite self-complementary \(r\)-uniform hypergraph. In [8], Kamble et al. proved the existence of \(r\)-partite self-complementary and almost self-complementary \(r\)-uniform hypergraphs.
The following result gives the necessary and sufficient condition for the existence of \(r\)-partite self-complementary \(r\)-uniform hypergraph.
Result 2.3. [8] There exists an \(r\)-psc \(H^r(V_1,V_2,\cdots,V_r)\) where \(|V_i|=n_i\) for \(i=1,2,\cdots,r\) if and only if at least one of \(n_1,n_2,\cdots,n_r\) is even.
For \(3\)-partite self-complementary \(3\)-uniform hypergraphs the above result can be restated as, “There exists a \(3\)-psc \(H^3(V_1,V_2,V_3)\) where \(|V_i|=n_i\) for \(i=1,2,3\) if and only if at least one of \(n_1,n_2,n_3\) is even”.
A permutation \(\sigma\) on \(V\) is said to be a complementing permutation of an \(r\)-psc \(H\), if \(\sigma(e)\) is an edge in \(E(\bar{H})\) whenever \(e\) is an edge in \(H\). In [1], Gangopadhyay and Rao Hebbare studied structural properties of \(r\)-partite complementing permutations. In [8], the authors analyzed the cycle structure of \(r\)-partite \(r\)-uniform self-complementary and almost self-complementary hypergraphs.
Definition 2.4. Let \(V=\{V_1,V_2,…,V_r\}\) be a partition of \(V\). A permutation \(\sigma_{p_i}\) is said to be a pure permutation on the set \(V_i\) if it is a permutation on the set \(V_i\) that can be written as a product of disjoint cycles containing all the vertices of \(V_i\).
Definition 2.5. Let \(V=\{V_1,V_2,…,V_r\}\) be a partition of \(V\). A permutation \(\sigma_{m_j}\) is said to be a mixed permutation on any \(j\) sets of \(V, ~2\leq j\leq r\) if it can be written as a product of disjoint cycles where each cycle contains at least one vertex from each of the \(j\) sets.
Remark 2.6. Let \(\sigma:V\rightarrow V\) be a complementing permutation of an \(r\)-partite \(r\)-uniform hypergraph \(H=H^r(V_1,V_2,\cdots,V_r)=H^r(V)\). We have \(e=\{u_1,u_2,\cdots, u_r\}\) is an edge in \(H\) if and only if \(\sigma(e)=\{\sigma(u_1),\sigma(u_2), \cdots, \sigma(u_r)\}\) is an edge in \(\bar{H}\). Therefore, the degree of any vertex \(u\) in \({H}\) is equal to the degree of its image \(\sigma(u)\) in \(\bar H\). In addition, we have \(d_H(u)+d_{\bar H}(u)=\) degree of \(u\) in \(K^r(V_1,V_2,\cdots,V_r)\). Therefore \(d_H(u)+d_{ H}(\sigma(u))=\) degree of \(u\) in \(K^r(V_1,V_2,\cdots,V_r)\).
If \(u\in V_j\) for some \(j=1, 2,\cdots, r\) is any vertex, then the degree of \(u\) in \(K^r(V_1,V_2,\cdots,V_r)\) is \(\displaystyle \prod_{\substack{i=1 \\ i\neq j}}^r n_i\). Therefore, we get \(d_H(u)+d_{\bar H}(u)=d_H(u)+d_{ H}(\sigma(u))=\displaystyle \prod_{\substack{i=1 \\ i\neq j}}^r n_i\).
It is clear that partitioning of the edge set of \(K^r(V_1,V_2,\cdots,V_r)\) into two isomorphic factors is not possible when \(K^r(V_1,V_2,\cdots,V_r)\) has an odd number of edges. However, after removing an odd number of edges from \(K^r(V_1,V_2,\cdots,V_r)\), the remaining \(r\)-uniform hypergraph may be partitioned into two isomorphic factors. By deleting one edge from \(K^r(V_1,V_2,\cdots,V_r)\) an almost complete \(r\)-partite \(r\)-uniform hypergraph is defined in [8] as follows.
Definition 2.7(Almost complete \(r\)-partite \(r\)-uniform hypergraph).[8] The hypergraph \(\tilde{K}_{(n_1,n_2,\cdots,n_r)}^r =K_{(n_1,n_2,\cdots,n_r)}^r-e\) is called an almost complete \(r\)-partite \(r\)-uniform hypergraph where \(e\) is an edge in \(K_{(n_1,n_2,\cdots,n_r)}^r\) called the deleted edge. Vertices of \(e\) will be called the special vertices.
Definition 2.8(\(r\)-partite almost self-complementary \(r\)-uniform hypergraph).[8] An \(r\)-partite \(r\)-uniform hypergraph \(H(V_1,V_2,\cdots,V_r)\) such that \(|V_i|=n_i\) for \(i=1,2,\cdots,r\) is almost self-complementary if it is isomorphic with its complement \(\bar{H}(V_1,V_2,\cdots,V_r)\) with respect to \(\tilde{K}_{(n_1,n_2,\cdots,n_r)}^r\).
We use the short form “\(r\)-pasc” for \(r\)-partite almost self-complementary \(r\)-uniform hypergraph.
The following result gives necessary and sufficient condition for the existence of \(r\)-pasc.
Result 2.9. [8] There exists an \(r\)-pasc \(H^r(V_1,V_2,\cdots,V_r)\) where \(|V_i|=n_i\) for \(i=1,2,\cdots,r\) if and only if \(n_1,n_2,\cdots,n_r\) are odd.
For \(3\)-partite almost self-complementary \(3\)-uniform hypergraphs the above result can be restated as, “There exists a \(3\)-pasc \(H^3(V_1,V_2,V_3)\) where \(|V_i|=n_i\) for \(i=1,2,3\) if and only if all \(n_1,n_2,n_3\) are odd”.
In [1], Gangopadhyay and Rao Hebbare characterized structural properties of \(r\)-partite complementing permutations. Let \(\mathcal{C}((G,V))\) be the class of all complementing permutations of the \(2\)-psc \(G(V_1,V_2)\) where \(|V_1|=n_1, |V_2|=n_2\) with \(V=V_1\cup V_2\). A cycle of a complementing permutation is said to be pure if it permutes only vertices belonging to a single set of \(V=V_1\cup V_2\), and is said to be mixed otherwise.
Define two subclasses of \(\mathcal{C}((G,V))\) as follows: \[\mathcal{C}_p((G,V)) = \{ \sigma \in \mathcal{C}((G,V)) \mid \text{all cycles of } \sigma \text{ are pure} \},\] \[\mathcal{C}_m((G,V)) = \{ \sigma \in \mathcal{C}((G,V)) \mid \text{all cycles of } \sigma \text{ are mixed} \}.\]
In [1], the authors proved that, \(\mathcal{C}((G,V)) = \mathcal{C}_p((G,V)) \cup \mathcal{C}_m((G,V))\). That is, if \(\sigma\) is a complementing permutation of \(2\)-psc \(G(V_1, V_2)\) then all cycles of \(\sigma\) are either pure or mixed. Further, if \(\sigma \in \mathcal{C}_m((G,V))\) and \(\tau\) is a cycle of \(\sigma\), then \(|\tau| \equiv 0 \pmod{4}\) and \(\sigma\) takes vertices alternately from \(V_1\) and \(V_2\), proving \(n_1=n_2\).
Remark 2.10. If all cycles of a complementing permutation \(\sigma\) are pure then for any \(u\in V_1\), \(d_G(u)+d_G(\sigma(u))=n_2\) and for any \(v\in V_2\), \(d_G(v)+d_G(\sigma(v))=n_1\). Similarly, if all cycles of \(\sigma\) are mixed then \(n_1=n_2\) and for any vertex \(u\in V\), \(d_G(u)+d_G(\sigma (u))=n_1=n_2\).
Definition 2.11(Degree of a vertex).The degree of a vertex \(v\) in a hypergraph \(H\) is the number of edges containing the vertex \(v\) and is denoted as \(d_H(v)\).
Definition 2.12(Regular hypergraph).A hypergraph \(H\) is said to be regular if all vertices have the same degree.
Definition 2.13(Quasi-regular hypergraph).A hypergraph \(H\) is said to be quasi-regular if the degree of each vertex is either \(s\) or \(s-1\) for some positive integer \(s\).
We know that \(2\)-psc (i.e bipartite self-complementary graph) \(G(V_1,V_2)\), where \(|V_1|=n_1, |V_2|=n_2\) with \(V=V_1\cup V_2\) exists if and only if either \(n_1\) or \(n_2\) is even. In the following theorem, we prove the existence of a regular \(2\)-partite self-complementary \(2\)-uniform hypergraph (i.e. regular bipartite self-complementary graph).
Theorem 2.14. There exists a regular \(2\)-psc (i.e bipartite self-complementary graph) \(G(V_1,V_2)\), where \(|V_1|=n_1, |V_2|=n_2\) if and only if both \(n_1\), \(n_2\) are even and \(n_1=n_2\).
Proof. Suppose there exists a regular \(2\)-psc \(G(V_1,V_2)\) where \(|V_1|=n_1, |V_2|=n_2\). Let \(s\) be the degree of every vertex in \(G(V_1,V_2)\). Let \(\sigma\) be a complementing permutation of \(G\).
Suppose all cycles of \(\sigma\) are pure. Then from the Remark 2.10 for any vertex \(u_1 \in V_1\), \(d_G(u_1)+d_G(\sigma(u_1))= n_2\). That is, \(s+s= n_2\). That is, \(2s=n_2\). Similarly, for any \(u_2\in V_2\), \(d_G(u_2)+d_G(\sigma(u_2))= n_1\). That is, \(s+s= n_1\). That is, \(2s=n_1\). Hence, \(2s=n_1=n_2\). This implies \(n_1\), \(n_2\) are even and \(n_1=n_2\).
Now, if all cycles of \(\sigma\) are mixed then we have \(n_1=n_2\). And for any vertex \(v\in V\), \(d_G(v)+d_G(\sigma (v))=n_1=n_2\). That is, \(2s=n_1=n_2\). Hence, both \(n_1\) and \(n_2\) are even.
Conversely, suppose \(n_1, n_2\) are even and \(n_1=n_2\). Let \(n_1=n_2=n\). To prove the converse, we construct a regular \(2\)-psc \(G(V_1,V_2)\) such that \(|V_1|=|V_2|=n\), where \(n\) is even. Let \(V_1=\{u_1,u_2,\cdots, u_n\}\), \(V_2=\{v_1,v_2,\cdots, v_n\}\) and \(V=V_1\cup V_2\). Let \(E=\{(u_iv_j)~|~i+j\equiv 0 ~\rm {or}~ 2 \pmod 4\}\) be the edge set of \(G\). That is, \((u_i v_j)\) is an edge if and only if \(i\) and \(j\) have the same parity. Clearly, \(d(u_i)=d(v_i)=\frac{n}{2},~~ i=1,2,\cdots, n\). Hence, \(G\) is regular. Let \(\sigma:V\rightarrow V\) be defined as \(\sigma(u_i)=u_{i+1}, i=1,2, 3,\cdots, n-1\), \(\sigma(u_n)=u_1,\) and \(\sigma(v_j)=v_j, j=1,2,3,\cdots n\). Observe that, for \(i=1,2,\cdots, n-1\) and \(j=1, 2, \cdots n\), if \((u_iv_j)\) is an edge in \(G\) then \(\sigma(u_iv_j)=(u_{i+1}v_{j} )\) is not an edge in \(G\), since \(i+1+j\equiv 1~\rm {or} ~3 \pmod 4\). Moreover, if \((u_nv_j)\) is an edge in \(G\) then \(j\) must be even and hence \(\sigma(u_nv_j)=(u_1v_j)\) is not an edge in \(G\). Hence, \(G\) is self-complementary with its complementing permutation \(\sigma\). ◻
In the next theorem, we prove the existence of a quasi-regular \(2\)-psc (i.e. quasi-regular bipartite self-complementary graph).
Theorem 2.15. There exists a quasi-regular \(2\)-psc \(G(V_1, V_2)\) if and only if either
(i) \(n_1\) and \(n_2\) differ by \(1\); or
(ii) both \(n_1\) and \(n_2\) are even and differ by \(2\).
Proof. Suppose that there exists a quasi-regular \(2\)-psc \(G(V_1,V_2)\) with \(|V_1|=n_1,\) and \(|V_2|=n_2\) with \(V=V_1\cup V_2\). Suppose for any vertex \(u\in V\), \(d(u)=s\) or \(s-1\). Let \(\sigma\) be its corresponding complementing permutation.
Suppose all cycles of \(\sigma\) are pure. Then from the Remark 2.10, for any vertex \(u\in V_1\), we have \[d_G(u)+d_G(\sigma(u))=n_2.\label{qpsc} \tag{1}\] And for any vertex \(v\in V_2\), we have \[d_G(v)+d_G(\sigma(v))=n_1.\label{qpsc2} \tag{2}\] From Result 2.3, at least one of \(n_1\) or \(n_2\) is even. Suppose \(n_1\) is odd and \(n_2\) is even.
Since \(G(V_1,V_2)\) is quasi-regular, from Eq. (1) we get, either \(s+s=n_2\) or \(s+(s-1)=n_2\) or \((s-1)+(s-1)=n_2\). That is, \(2s=n_2\) or \(2s-1=n_2\) or \(2s-2=n_2\). Since \(n_2\) is even, we get \(2s=n_2\) or \(2s-2=n_2\). Similarly, from Eq. (2), we get \(s+s=n_1\) or \(s+(s-1)=n_1\) or \((s-1)+(s-1)=n_1\). That is, \(2s=n_1\) or \(2s_1-1=n_1\) or \(2s-2=n_1\). Since \(n_1\) is odd, we get \(2s-1=n_1\). Therefore, we get \(2s=n_2\) or \(2s-2=n_2\) and \(2s-1=n_1\). That is, \(n_2=2s, n_1=2s-1\) or \(n_2=2s-2, n_1=2s-1\). This implies \(n_1=n_2-1\) or \(n_1=n_2+1\). This implies \(n_1\) and \(n_2\) differ by 1.
Now suppose \(n_1\) and \(n_2\) both are even. Then by the similar argument as above from Eqs. (1) and (2), we get \(2s=n_2\) or \(2s-2=n_2\) and \(2s=n_1\) or \(2s-2=n_1\). This implies \(2s=n_2, 2s-2=n_1\) or \(2s=n_1, 2s-2=n_2\). As \(G\) is quasi-regular \(2s=n_1=n_2\) or \(2s-2=n_1=n_2\) is not possible. This implies that \(n_1\) and \(n_2\) differ by 2.
To prove the converse, we construct a quasi-regular \(2\)-psc \(G(V_1, V_2)\) such that \(V_1=n_1\) and \(V_2=n_2\) in both the cases.
i) Suppose \(n_1\) and \(n_2\) differ by 1 with \(n_1\) is even. Let \(n_2=n_1+1\). Let \(V_1=\{u_1, u_2, \cdots, u_{n_1}\}\) and \(V_2=\{v_1, v_2,\cdots,v_{n_1}, v_{n_1+1}\}\) and \(V=V_1\cup V_2\). Let \(E=\{(u_iv_j)~|~i+j\equiv 0 ~\rm {or}~ 2 \pmod 4\}\) be the edge set of \(G\). That is, \((u_i v_j)\) is an edge if and only if \(i\) and \(j\) have the same parity. Clearly, for any \(i=1, 2, \cdots, n_1\), \(d(u_i)=\frac{n_1}{2} +1,~~\) if \(i\) is odd and \(d(u_i)=\frac{n_1}{2},~~\) if \(i\) is even. And \(d(v_j)=\frac{n_1}{2},\) for each \(j=1, 2, \cdots, n_1+1\). Since degree of any vertex in \(G\) is either \(\frac{n_1}{2}\) or \(\frac{n_1}{2}+1\), \(G\) is quasi-regular. Let \(\sigma:V\rightarrow V\) be defined as \(\sigma(u_i)=u_{i+1}, i=1,2, 3,\cdots, n_1\), \(\sigma(u_{n_1})=u_1,\) and \(\sigma(v_j)=v_j, ~j=1,2,3,\cdots, n_1+1\).
Now if \((u_iv_j)\) is an edge in \(G\) then \(\sigma(u_iv_j)=u_{i+1}v_j\) is not an edge in \(G\) since \(i+1\) and \(j\) are of opposite parity for \(i=1,2, 3,\cdots, n_1\) and \(j=1,2,3,\cdots, n_1+1\). Hence, \(G\) is self-complementary with its complementing permutation \(\sigma\).
ii) Suppose \(n_1\) and \(n_2\) are even and differ by 2. Let \(n_2=n_1+2\). Let \(V_1=\{u_1, u_2, \cdots, u_{n_1}\}\) and \(V_2=\{v_1, v_2,\cdots,v_{n_1}, v_{n_1+1}, v_{n_1+2}\}\) and \(V=V_1\cup V_2\).
Let \(E=\{(u_iv_j)~|~i+j\equiv 0 ~\rm {or}~ 2 \pmod 4\}\) be the edge set of \(G\). That is, \((u_i u_j)\) is an edge if and only if \(i\) and \(j\) have the same parity. Clearly, \(d(u_i)=\frac{n_1}{2} +1,~~\) for each \(i, ~i=1, 2, \cdots, n_1\). And \(d(v_j)=\frac{n_1}{2},\) for each \(j=1, 2, \cdots, n_1, n_1+1, n_2+2\). Since degree of any vertex in \(G\) is either \(\frac{n_1}{2}\) or \(\frac{n_1}{2} +1\), \(G\) is quasi-regular. Let \(\sigma:V\rightarrow V\) be defined as \(\sigma(u_i)=u_{i+1}, i=1,2, 3,\cdots, n_1\), \(\sigma(u_n)=u_1,\) and \(\sigma(v_j)=v_j, ~j=1,2,3,\cdots, n_1+1, n_1+2\).
Now if \((u_iv_j)\) is an edge in \(G\) then \(\sigma(u_iv_j)=u_{i+1}v_j\) is not an edge in \(G\) since \(i+1\) and \(j\) are of opposite parity for \(i=1,2, 3,\cdots, n_1\) and \(j=1,2,3,\cdots, n_1+1, n_1+2\). Hence, \(G\) is self-complementary with its complementing permutation \(\sigma\). ◻
In [8], Kamble et al. proved that a \(2\)-pasc (i.e bipartite almost self-complementary graph) \(G(V_1,V_2)\), where \(|V_1|=n_1, |V_2|=n_2\) exists if and only if both \(n_1\) and \(n_2\) are odd. In addition, the authors analyzed the cycle structure of complementing permutations of \(2\)-pasc \(G(V_1,V_2)\).
Remark 2.16. Let \(G(V_1,V_2)\), where \(|V_1|=n_1, |V_2|=n_2\) be a \(2\)-pasc with the complementing permutation \(\sigma\). Let \(u\in V_1\). Suppose all cycles of \(\sigma\) are pure. If \(u\) is not a special vertex, then \(d_G(u)+d_G(\sigma(u))=n_2\) and if \(u\) is a special vertex, then \(d_G(u)+d_G(\sigma(u))=n_2-1\). Similarly, for any \(v\in V_2\), if \(v\) is not a special vertex, then \(d_G(v)+d_G(\sigma(v))=n_1\) and if \(v\) is a special vertex, then \(d_G(v)+d_G(\sigma(v))=n_1-1\). Similarly, if all cycles of \(\sigma\) are mixed, then \(n_1=n_2\). Furthermore, if \(v\in V\) is not a special vertex, then \(d_G(v)+d_G(\sigma (v))=n_1=n_2\) and if \(v\in V\) is a special vertex, then \(d_G(v)+d_G(\sigma (v))=n_1-1=n_2-1\).
We have if \(|V_1|=1, |V_2|=1\), then \(K^2_{(1,1)}\) has only one edge, and \(\tilde K^2_{(1, 1)}\) is obtained by deleting that edge, which is the null graph. And the null graph on two vertices is regular of degree \(0\).
In the following theorem we prove that there does not exist a regular \(2\)-pasc graph \(G(V_1, V_2)\) such that \(|V_1|=n_1, |V_2|=n_2\) and \(n_1, n_2>1\).
Theorem 2.17. There does not exist a regular \(2\)-pasc graph \(G(V_1, V_2)\) such that \(|V_1|=n_1, |V_2|=n_2\) and \(n_1, n_2>1\).
Proof. Suppose there exists a regular \(2\)-pasc \(G(V_1,V_2)\) such that \(|V_1|=n_1, |V_2|=n_2\) and \(n_1, n_2>1\). Let \(d(u)=s\) for each \(u\in V\). From Result 2.9 we get that \(n_1\) and \(n_2\) are odd. Let \(\sigma\) be the corresponding complementing permutation. If all cycles of \(\sigma\) are pure, then from the Remark 2.16, we get, if \(u\) is not a special vertex, then \(d_G(u)+d_G(\sigma(u))=n_2\) and if \(u\) is a special vertex, then \(d_G(u)+d_G(\sigma(u))=n_2-1\). That is, \(s+s=n_2\) and \(s+s=n_2-1\), which is not possible.
Similarly, if all cycles of \(\sigma\) are mixed, then \(n_1=n_2\). If \(u\in V\) is not a special vertex, then \(d_G(u)+d_G(\sigma (u))=n\) and if \(u\in V\) is a special vertex, then \(d_G(u)+d_G(\sigma (u))=n-1\). That is, \(s+s=n\) and \(s+s=n-1\), which is a contradiction. Hence, there does not exist a regular \(2\)-pasc graph \(G(V_1, V_2)\) such that \(|V_1|=n_1, |V_2|=n_2\) and \(n_1, n_2>1\). ◻
In the following theorem we prove the necessary and sufficient condition for the existence of a quasi-regular 2-pasc.
Theorem 2.18. There exists a quasi-regular \(2\)-pasc \(G(V_1,V_2)\) with \(|V_1|=n_1,\) and \(|V_2|=n_2\), if and only if both \(n_1, n_2\) are odd and \(n_1=n_2\).
Proof. Suppose there exists a quasi-regular \(2\)-pasc \(G(V_1,V_2)\) with \(|V_1|=n_1,\) and \(|V_2|=n_2\). From Result 2.9, we have \(n_1\) and \(n_2\) are odd. Suppose for any vertex \(u \in V ,~~ d(u) = q\) or \(q – 1.\) Let \(\sigma\) be the corresponding complementing permutation.
Suppose all cycles of \(\sigma\) are pure.
From the Remark 2.16, if \(u\in V_1\) is not a special vertex, we get
\[d_G(u)+d_G(\sigma(u))=n_2, \label{eqn-11} \tag{3}\] and if \(u\in V_1\) is a special vertex, then \[d_G(u)+d_G(\sigma(u))=n_2-1. \label{eqn-12} \tag{4}\]
Similarly, if \(v\in V_2\) is not a special vertex, then \[d_G(v)+d_G(\sigma(v))=n_1. \label{eqn-13} \tag{5}\]
If \(v\in V_2\) is a special vertex, then \[d_G(v)+d_G(\sigma(v))=n_1-1. \label{eqn-14} \tag{6}\]
From Eq. (3), we get that either \(q+q=n_2\) or \(q+(q-1)=n_2\) or \((q-1)+(q-1)=n_2\) that is either \(2q=n_2\) or \(2q-1=n_2\) or \(2q-2=n_2\). Since \(n_2\) is odd, we get \(2q-1=n_2\). And from Eq. (4), we get either \(q+q=n_2-1\) or \(q+(q-1)=n_2-1\) or \((q-1)+(q-1)=n_2-1\) that is either \(2q=n_2-1\) or \(2q-1=n_2-1\) or \(2q-2=n_2-1\). Since \(n_2\) is odd, we get, \(2q=n_2-1\) or \(2q-2=n_2-1\).
Therefore, \(2q-1=n_2\).
Similarly, from Eq. (5), we get that either \(q+q=n_1\) or \(q+(q-1)=n_1\) or \((q-1)+(q-1)=n_1\) that is either \(2q=n_1\) or \(2q-1=n_1\) or \(2q-2=n_1\). Since \(n_1\) is odd we get \(2q-1=n_1\). And from Eq. (6), we get that either \(q+q=n_1-1\) or \(q+(q-1)=n_1-1\) or \((q-1)+(q-1)=n_1-1\) that is either \(2q=n_1-1\) or \(2q-1=n_1-1\) or \(2q-2=n_1-1\). Since \(n_1\) is odd we get that, \(2q=n_1-1\) or \(2q-2=n_1-1\).
Therefore, \(2q-1=n_1\). Hence, we get that \(2q-1=n_1=n_2\) i.e. \(n_1=n_2\).
Suppose all cycles of \(\sigma\) are mixed. Then we have \(n_1=n_2\).
To prove the converse, we construct a quasi-regular \(2\)-pasc \(G(V_1,V_2)\) with \(|V_1|=n_1,\) and \(|V_2|=n_2\), with both \(n_1, n_2\) are odd and \(n_1=n_2\).
Let \(V_1=\{u_1, u_2, \cdots, u_{2k+1}\}\) and \(V_2=\{v_1, v_2,\cdots, v_{2k+1}\}\) and \(V=V_1\cup V_2\).
Let \(E=\{(u_iv_j)~|~ \text{both } i ~\text{and} ~ j ~\text{are either even or odd} \}\cup \{(u_i v_{2k+1})~|~ i ~\text {is odd}, ~1\leq i\leq 2k\} \cup \{( u_{2k+1} v_i)~|~ i ~\text {is odd},~1\leq i\leq 2k\}\) be the edge set of \(G\) with the deleted edge \((u_{2k+1} v_{2k+1})\). Observe that for each odd \(i, 1\leq i\leq 2k\), \(d(u_i)=d(v_i)=k+1\), for each even \(j, 1\leq j\leq 2k\), \(d(u_i)=d(v_i)=k\), and \(d(u_{2k+1})=d(v_{2k+1})=k\). This implies \(G\) is quasi-regular.
Let \(\sigma:V\rightarrow V\) be defined as \(\sigma(u_i)=u_{i+1}, ~ i=1,2, 3,\cdots, 2k\), \(\sigma(u_{2k})=u_1,\) \(\sigma(u_{2k+1})=u_{2k+1}, ~ \sigma(v_j)=v_{j}, ~j=1,2,3,\cdots, 2k+1\).
Observe that, if \((u_iv_j)\) is an edge in \(G\) then \(\sigma(u_iv_j)\) is not an edge in \(G\). Hence, \(G\) is almost self-complementary with complementing permutation \(\sigma\). ◻
In the next section, we prove the existence of regular \(3\)-partite self-complementary and almost self-complementary \(3\)-uniform hypergraphs.
It is known that [10], a regular self-complementary \(3\)-uniform hypergraph exists if and only if \(n\) is congruent to 1 or 2 modulo 4. In [7], it is proved that, there exists a regular bipartite self-complementary \(3\)-uniform hypergraph \(H(V_1,V_2)\) with \(|V_1|=m,|V_2|=n,m+n>3\) if and only if \(m=n\) and \(n\) is congruent to \(0\) or \(1\) modulo \(4\).
In [8], Kamble et al. proved that a \(3\)-psc (i.e 3-partite self-complementary 3-uniform hypergraph) \(H(V_1,V_2, V_3)\), where \(|V_1|=n_1, |V_2|=n_2, |V_3|=n_3\) exists if and only if at least one of \(n_1, n_2, n_3\) is even. Further, the authors analyzed the cycle structure of complementing permutations of \(3\)-psc \(H(V_1,V_2, V_3)\).
Remark 3.1. Let \(H(V_1,V_2, V_3)\), where \(|V_1|=n_1, |V_2|=n_2, |V_3|=n_3\) be a \(3\)-psc with a complementing permutation \(\sigma\).
i) Suppose all cycles of \(\sigma\) are pure then for any vertex \(u\in V_1\), we have \(d_H(u)+d_H(\sigma(u))=n_2n_3\), for any vertex \(u\in V_2\), we have \(d_H(u)+d_H(\sigma(u))=n_1n_3\), and for any vertex \(u\in V_3\), we have \(d_H(u)+d_H(\sigma(u))=n_1n_2\).
ii) Suppose cycles of \(\sigma\) are mixed and it permutes vertices from each set \(V_1, V_2, V_3\), then \(n_1=n_2=n_3=n\). Furthermore, for any vertex \(u\in V\), \(d_H(u)+d_H(\sigma(u))=n^2\).
iii) Suppose cycles of \(\sigma\) are mixed and it permutes vertices from \(V_1\) and \(V_2\) only. That is \(\sigma(V_1)=V_2, \sigma(V_2)=V_1\) and \(\sigma(V_3)=V_3\). In this case \(n_1=n_2=n\). And for any vertex \(u\in V_1\) or \(u\in V_2\), we have \(d_H(u)+d_H(\sigma(u))=nn_3\), and for any vertex \(u\in V_3\), we have \(d_H(u)+d_H(\sigma(u))=n^2\).
The following theorem gives a necessary and sufficient condition for the existence of a regular \(3\)-psc.
Theorem 3.2. There exists a regular \(3\)-psc \(H^3(V_1,V_2,V_3)\) where \(|V_i|=n_i\) for \(i=1,2,3\) if and only if \(n_1=n_2=n_3\) and each \(n_i, i=1, 2, 3\) is even.
Proof. Suppose there exists a regular \(3\)-psc \(H^3(V_1,V_2,V_3)\) where \(|V_i|=n_i\) for \(i=1,2,3\) with a complementing permutation \(\sigma\). From Result 2.3, at least one of \(n_1,n_2\) and \(n_3\) must be even. Let \(s\) be the degree of every vertex in \(H^3(V_1,V_2,V_3)\).
i) Suppose \(\sigma\) is pure, that is \(\sigma(V_i)=V_i, i=1, 2, 3\). From the Remark 3.1, for any vertex \(u_1 \in V_1\), \(d_H(u_1)+d_H(\sigma(u_1))= n_2n_3\). That is, \(s+s= n_2n_3\). That is, \(2s=n_2n_3\).
And, for any \(u_2\in V_2\), \(d_H(u_2)+d_H(\sigma(u_2))= n_1n_3\). That is, \(s+s= n_1n_3\). That is, \(2s=n_1n_3\).
Similarly, for any \(u_3\in V_3\), \(d_H(u_3)+d_H(\sigma(u_3))= n_1n_2\). That is, \(s+s= n_1n_2\). That is, \(2s=n_1n_2\).
Hence, \(n_2n_3=n_1n_3=n_1n_2\). That is, \(n_1=n_2=n_3\). From Result 2.3, we have \(n_1,n_2\) and \(n_3\) are even.
ii) Suppose \(\sigma\) is mixed such that \(\sigma(V_1)=V_2, ~~\sigma(V_2)=V_1\), and \(\sigma(V_3)=V_3\). Then \(n_1=n_2=n\).
For any vertex \(u \in V_1\) or \(V_2\), \(d_H(u)+d_H(\sigma(u))= nn_3\). That is, \(s+s= nn_3\). That is \(2s=nn_3\). And for any vertex \(v \in V_3\), \(d_H(v)+d_H(\sigma(v))= n^2\). That is, \(s+s= n^2\). That is, \(2s=n^2\). Hence, we get \(2s=n^2=nn_3\). That is, \(n=n_3\) and \(n\) is even.
iii) Suppose \(\sigma\) is mixed such that \(\sigma(V_1)=V_2, ~~\sigma(V_2)=V_3\), and \(\sigma(V_3)=V_1\). Then \(n_1=n_2=n_3=n\).
For any vertex \(u \in V\), \(d_H(u)+d_H(\sigma(u))= n^2\). That is, \(s+s= n^2\). That is \(2s=n^2\). That is, \(n\) is even.
Hence, if a regular \(3\)-psc \(H^3(V_1,V_2,V_3)\) where \(|V_i|=n_i\) for \(i=1,2,3\) exists then \(n_1=n_2=n_3\) and each \(n_i, i=1, 2, 3\) is even.
To prove the converse, we construct a regular \(3\)-psc \(H^3(V_1,V_2,V_3)\) such that \(|V_i|=n, i=1, 2, 3\) and \(n\) is even.
Let \(V_1=\{u_1,u_2,\cdots, u_n\}\), \(V_2=\{v_1,v_2,\cdots, v_n\}\) and \(V_3=\{w_1,w_2,\cdots, w_n\}\).
First we construct a regular \(2\)-partite self-complementary graph \(G(V_1,V_2)\) as constructed in the Theorem 2.14. We have \(\sigma:V(G)\rightarrow V(G)\) defined as \(\sigma(u_i)=u_{i+1}, i=1,2, \cdots, n-1\), \(\sigma(u_n)=u_1,\) and \(\sigma(v_j)=v_j, j=1,2,\cdots, n\) is its complementing permutation.
Consider the following partition of the edge set of \(K^3(V_1,V_2,V_3)\). \[E=\{e\cup w_i, ~~ i=1, 2,\cdots, n~|~ e ~\rm {is~ an~ edge~ in~} G\},\] \[{\bar E}=\{e'\cup w_i, ~~i=1, 2,\cdots, n~|~ e' ~\rm {is~ an~ edge~ in~} \bar G\}.\]
Let \(H\) be a \(3\)-uniform hypergraph whose edge set is \(E\). \(H\) is a \(3\)-partite \(3\)-uniform hypergraph with partition \((V_1,V_2,V_3)\) of the vertex set \(V\) such that \(|V_i|=n, ~i=1, 2, 3.\)
Let \(\sigma': V\rightarrow V\) be defined as \(\sigma'(u_i)=\sigma(u_i), ~\sigma'(v_i)=\sigma(v_i), ~ \sigma'(w_{i})=w_i, i=1, 2,\cdots n.\)
We have, for \(i=1,2,\cdots, n-1\) and \(j=1, 2, \cdots, n\), \(u_iv_j\) is an edge in \(G\) if and only if \(\sigma(u_iv_j)=u_{i+1}v_{j}\) is not an edge in \(G\). Consequently, \(\{u_i, v_j,w_k\}\) is an edge in \(H\) if and only if \(\{\sigma(u_i), \sigma(v_j),\sigma(w_k)\}=\{u_{i+1}, v_j,w_k\}\) is an edge in \(\bar H\). Hence, \(\sigma'\) is a complementing permutation of \(H\). That is, \(H\) is self-complementary with complementing permutation \(\sigma'\).
Observe that, \(d_H(u_i)=(\frac{n}{2})\times n=\frac{n^2}{2},~d_H(v_j)= \frac{n^2}{2}\) and \(d_H(w_k)=|E(G)|=\frac{n^2}{2}\) for \(i,j,k=1, 2, 3,\cdots, n\). Hence, \(d_H(u_i)=d_H(v_j)=d_H(w_k)=\frac{n^2}{2}\) for each \(i,j,k=1,2,\cdots,n\). This proves that \(H\) is a regular \(3\)-psc. ◻
The following example illustrates the construction of a regular 3-psc \(H(V_1,V_2,V_3)\) with \(|V_i|=4, i=1,2,3\).
Example 3.3. Let \(V=V_1\cup V_2\cup V_3\) with \(V_1=\{u_1, u_2, u_3, u_4\}, V_2=\{v_1, v_2,v_3,v_4\}\) and \(V_3=\{w_1, w_2, w_3, w_4\}\). We construct a regular self-complementary 3-psc \(H(V_1,V_2,V_3)\).
First we construct a regular 2-partite graph \(G(V_1,V_2)\) as constructed in Theorem 2.14.
We have \(E(G)=\{(u_iv_j)~|~ i ~\text{and }~ j ~\text{have the same parity}\}\).
That is, \(E(G)=\{(u_1v_1), (u_1v_3), (u_2 v_2), (u_2 v_4), (u_3 v_1),(u_3v_3),(u_4v_2),(u_4v_4 \}\).
Here \(d_G(u_1)=d_G(u_2)=d_G(u_3)=d_G(u_4)=d_G(v_1)=d_G(v_2)=d_G(v_3)=d_G(v_4)=2\). Hence, \(G\) is a regular graph.
Let \(\sigma: V(G)\rightarrow V(G)\) be defined as \(\sigma(u_1)=u_2,\sigma(u_2)=u_3,\sigma(u_3)=u_4,\sigma(u_4)=u_1\) and \(\sigma(v_i)=v_i, ~i=1, 2, 3, 4\). Here if \((u_iv_j)\) is an edge in \(G\), then \(i\) and \(j\) are of same parity. And \(\sigma(u_iv_j)=(u_{i+1}vj)\) is not an edge in \(G\), since \(i+1\) and \(j\) are of opposite parity. Hence, \(G(V_1,V_2)\) is self-complementary with complementing permutation \(\sigma\).
Now we construct a \(3\)-psc \(H(V_1,V_2,V_3)\). The edge set of \(H\) is \(E(H)=\{e\cup w_i, ~~ i=1, 2,\cdots, n~|~ e ~\rm {is~ an~ edge~ in~} G\}\) that is \(E(H)\) is obtained by adding each vertex \(w_1,w_2,w_3\) and \(w_4\) in every edge of \(G\).
Therefore \(E(H)=\{(u_1v_1w_1),
(u_1v_1w_2),(u_1v_1w_3),(u_1v_1w_4),(u_1v_3w_1),(u_1v_3w_2),(u_1v_3w_3),\\(u_1v_3w_4),\)
\((u_2 v_2w_1),(u_2 v_2w_2),(u_2 v_2w_3),(u_2
v_2w_4), (u_2 v_4w_1), (u_2 v_4w_2),(u_2 v_4w_3),(u_2
v_4w_4),\)
\((u_3 v_1w_1),(u_3 v_1w_2),(u_3 v_1w_3),(u_3
v_1w_4),(u_3v_3w_1),(u_3v_3w_2),(u_3v_3w_3),(u_3v_3w_4),\) \((u_4v_2w_1),\\
(u_4v_2w_2),(u_4v_2w_3),(u_4v_2w_4),(u_4v_4w_1) ,
(u_4v_4w_2),(u_4v_4w_3),(u_4v_4w_4)\}\).
Observe that \(d_H(u_i)=8,~d_H(v_j)= 8\) and \(d_H(w_k)=|E(G)|=8\) for \(i,j,k=1, 2, 3,4\).
Hence, \(H\) is regular.
Let \(\sigma':V(H)\rightarrow V(H)\) be defined as \(\sigma'(u_i)=\sigma(u_i), ~\sigma'(v_i)=\sigma(v_i), ~ \sigma'(w_{i})=w_i, i=1, 2,3, 4.\) That is, \(\sigma'(u_1)=u_2,\sigma'(u_2)=u_3,\sigma'(u_3)=u_4,\sigma'(u_4)=u_1\), \(\sigma'(v_i)=v_i, ~i=1, 2, 3, 4\) and \(\sigma'(w_{i})=w_i, i=1, 2,3,4.\) Here for any edge \(e\) in \(H\), \(\sigma'(e)\) is not an edge in \(H\). Hence \(\sigma\) is a complementing permutation of \(H\). Therefore \(H\) is regular \(3\)-psc.
In the next theorem, we prove the existence of quasi-regular \(3\)-psc \(H(V_1,V_2,V_3)\).
Theorem 3.4. There exists a quasi-regular \(3\)-psc \(H(V_1,V_2,V_3)\) with \(|V_i|=n_i, i=1,2,3\) if and only if the set \(\{n_1, n_2, n_3\}\) is equal to one of \(\{1, 1, 2\}, \{2, 2, 1\},\) or \(\{2, 2, 3\}\).
Proof. Suppose there exists a quasi-regular \(3\)-psc \(H(V_1,V_2,V_3)\) with \(|V_i|=n_i, i=1,2,3\). Since \(H\) is quasi-regular, for any vertex \(u\in V\), we have \(d(u)=q\) or \(q-1\). Let \(\sigma\) be its corresponding complementing permutation. We have either \(\sigma\) is pure or it is mixed. To prove the result we consider following cases depending on the nature of complementing permutation \(\sigma\).
Case 1. Suppose \(\sigma\) is pure.
For any \(u_1\in V_1\), from the Remark 3.1, we get \[d_H(u_1)+d_H(\sigma(u_1))=n_2n_3 \label{q1}. \tag{7}\]
For any \(u_2\in V_2\), we get \[d_H(u_2)+d_H(\sigma(u_2))=n_1n_3 \label{q2}. \tag{8}\]
For any \(u_3\in V_3\), we get \[d_H(u_3)+d_H(\sigma(u_3))=n_1n_2 \label{q3}. \tag{9}\]
Since \(H\) is self-complementary from the Result 2.3, at least one of \(n_1, n_2, n_3\) is even.
We consider the following cases \((a), (b)\) and \((c)\).
a) Suppose exactly one of \(n_1, n_2, n_3\) is even say \(n_1.\)
From the Eq. (7) we get, \(q+q=n_2n_3\) or \(q+(q-1)=n_2n_3\) or \((q-1)+(q-1)=n_2n_3\). Since \(n_2\) and \(n_3\) are odd we get, \(q+(q-1)=n_2n_3\). That is, \(2q-1=n_2n_3\).
From the Eq. (8) we get, \(q+q=n_1n_3\) or \(q+(q-1)=n_1n_3\) or \((q-1)+(q-1)=n_1n_3\). Since \(n_1\) is even and \(n_3\) is odd we get, \(2q=n_1n_3\) or \(2q-2=n_1n_3\).
From the Eq. (9) we get, \(q+q=n_1n_2\) or \(q+(q-1)=n_1n_2\) or \((q-1)+(q-1)=n_1n_2\). Since \(n_1\) is even we get, \(2q=n_1n_2\) or \(2q-2=n_1n_2\).
Considering all possibilities, we get either \(2q-1=n_2n_3\), \(2q=n_1n_3\) , \(2q=n_1n_2\) or \(2q-1=n_2n_3\), \(2q-2=n_1n_3\) , \(2q=n_1n_2\) or \(2q-1=n_2n_3\), \(2q=n_1n_3\) , \(2q-2=n_1n_2\) or \(2q-1=n_2n_3\), \(2q-2=n_1n_3\) , \(2q-2=n_1n_2\).
Solving all above equations we get \(\{n_1, n_2, n_3\}=\{1, 1, 2\}\).
b) Suppose any two of \(n_1, n_2, n_3\) are even say \(n_1\) and \(n_3\). From Eq. (7) we get \(2q=n_2n_3\) or \(2q-2=n_2n_3\).
From Eq. (8) we get \(2q=n_1n_3\) or \(2q-2=n_1n_3\).
From Eq. (9) we get \(2q=n_1n_2\) or \(2q-2=n_1n_2\).
Considering all possibilities, we get \(2q=n_2n_3\), \(2q=n_1n_3\) , \(2q=n_1n_2\) or \(2q=n_2n_3\), \(2q=n_1n_3\) , \(2q-2=n_1n_2\) or \(2q=n_2n_3\), \(2q-2=n_1n_3\) , \(2q=n_1n_2\) or \(2q=n_2n_3\), \(2q-2=n_1n_3\) , \(2q-2=n_1n_2\) or \(2q-2=n_2n_3\), \(2q=n_1n_3\) , \(2q=n_1n_2\) or \(2q-2=n_2n_3\), \(2q-2=n_1n_3\) , \(2q=n_1n_2\) or \(2q-2=n_2n_3\), \(2q=n_1n_3\) , \(2q-2=n_1n_2\) or \(2q-2=n_2n_3\), \(2q-2=n_1n_3\) , \(2q-2=n_1n_2\).
Solving all above equations we get, \(\{n_1, n_2, n_3\}=\{2, 2, 1\}\) or \(\{n_1, n_2, n_3\}=\{2, 2, 3\}\).
c) If all \(n_1, n_2, n_3\) are even then we get the same possibilities that are in case (b).
Hence, if \(\sigma\) is pure, we get, \(\{n_1, n_2, n_3\}=\{1, 1, 2\}\) or \(\{n_1, n_2, n_3\}=\{2, 2, 1\}\) or \(\{n_1, n_2, n_3\}=\{2, 2, 3\}\).
Case 2. Suppose cycles of \(\sigma\) are mixed and it permutes vertices from each set \(V_1, V_2, V_3\), then \(n_1=n_2=n_3=n\). And \(n\) is even. Furthermore, for any vertex \(u\in V\), \(d_H(u)+d_H(\sigma(u))=n^2\).
Considering all possibilities we get, \(2q=n^2\) or \(2q-2=n^2\), which is a contradiction, since \(H\) is quasi-regular.
Case 3. Suppose cycles of \(\sigma\) are mixed and it permutes vertices from \(V_1, V_2\) only, then \(n_1=n_2=n\). And for any vertex \(u\in V_1\) or \(u\in V_2\), we have \[d_H(u)+d_H(\sigma(u))=n n_3 ,\label{e1} \tag{10}\] and for any vertex \(u\in V_3\), we have \[d_H(u)+d_H(\sigma(u))=n^2. \label{e2} \tag{11}\]
We have either \(n\) or \(n_3\) must be even.
a) Suppose \(n\) is even and \(n_3\) is odd. From Eq. (10), we get \(2q=n n_3\) or \(2q-2=n n_3\). Similarly, from Eq. (11), we get \(2q=n^2\) or \(2q-2=n^2\).
By considering all possibilities, we get following equations. \(2q=n n_3\), \(2q=n^2\) or \(2q-2=n^2\), \(2q=n n_3\) or \(2q-2=n n_3\), \(2q=n^2\) or \(2q-2=n n_3\), \(2q-2=n^2\).
Solving all above equations we get, \(n=2\) and \(n_3=3\).
b) Suppose \(n\) is odd and \(n_3\) is even.
By considering all possibilities, we get following equations.
\(2q=n n_3\), \(2q=n^2\) or \(2q-2=n^2\), \(2q=n n_3\) or \(2q-2=n n_3\), \(2q=n^2\) or \(2q-2=n n_3\), \(2q-2=n^2\).
Solving all above equations we get, \(n=1\) and \(n_3=2\).
Hence, from case (a) and case (b) we get either \(n_1=n_2=2, n_3=3\) or \(n_1=n_2=1, n_3=2\). That is, \(\{n_1, n_2, n_3\}=\{1, 1, 2\}\) or \(\{n_1, n_2, n_3\}=\{2, 2, 3\}\).
Hence, from Case I, Case II and Case III, we get, if there exists a quasi-regular \(3\)-psc \(H(V_1,V_2,V_3)\) with \(|V_i|=n_i, i=1,2,3\) then \(\{n_1, n_2, n_3\}=\{1, 1, 2\}\) or \(\{n_1, n_2, n_3\}=\{2, 2, 1\}\) or \(\{n_1, n_2, n_3\}=\{2, 2, 3\}\).
The converse of the theorem follows from the following examples.
1) Consider a hypergraph \(H(V_1, V_2, V_3)\) with vertex set \(V=V_1\cup V_2\cup V_3\) where \(V_1=\{u\}, V_2=\{v\}, V_3=\{w_1, w_2\}.\) Let \(E(H)=\{\{u, v,w_1\}\}\) and edge set of its complement is \(E(\bar H)=\{\{u,v, w_2\}\}\). \(d_H(u)=d_H(v)=d_H(w)=1\), and \(d_H(w_2)=0\). Now consider \(\sigma:V(H)\rightarrow V(H)\) given by \(\sigma(u)=u, \sigma(v)=v, \sigma(w_1)=w_2,\) and \(\sigma(w_2)=w_1\). Here \(\{u, v, w_1\}\) is an edge in \(H\) and \(\{\sigma(u), \sigma(v), \sigma(w_1)\}=\{u,v,w_2\}\) is an edge in \(\bar H\). Therefore \(H\) is quasi-regular 3-psc.
2) Consider a hypergraph \(H(V_1, V_2, V_3)\) with vertex set \(V=V_1\cup V_2\cup V_3\) where \(V_1=\{u_1, u_2\}, ~V_2=\{v_1,v_2\}, V_3=\{w\}.\) Let \(E(H)=\{\{u_1, v_1, w\}, \{u_2, v_2, w\}\}\) and edge set of its complement is \(E(\bar H)=\{\{u_1,v_2, w\}, \{u_2, v_1, w\}\}\). Here \(d_H(u_1)=d_H(v_1)=d_H(w)=2\), and \(d_H(u_2)=d_H(u_2)=1\). Hence, \(H\) is quasi-regular. Now consider \(\sigma:V(H)\rightarrow V(H)\) given by \(\sigma(u_1)=u_2, \sigma(u_2)=u_1, \sigma(v_1)=v_1,~\sigma(v_2)=v_2\) and \(\sigma(w)=w\). Here \(\{u_1, v_1, w\}\) and \(\{u_2, v_2, w\}\) are edges in \(H\) whereas \(\{\sigma(u_1), \sigma(v_1), \sigma(w)\}=\{u_2,v_1,w\}\) and \(\{\sigma(u_2), \sigma(v_2), \sigma(w)\}=\{u_1,v_2,w\}\) are edges in \(\bar H\). Therefore, \(H\) is self-complementary.
3) Consider a hypergraph \(H(V_1, V_2, V_3)\) with a vertex set \(V=V_1\cup V_2\cup V_3\) where \(V_1=\{u_1, u_2\}, ~V_2=\{v_1,v_2\},~ V_3=\{w_1, w_2,w_3\}.\) Let \(E(H)=\{\{u_1, v_1, w_1\}, \{u_2, v_2, w_1\},\{u_1, v_1,\\ w_2\}, \{u_2, v_2, w_2\},\)\(\{u_1, v_1, w_3\}, \{u_2, v_2, w_3\}\}\) be the edge set of \(H\) and \(E(\bar H)=\{\{u_1,v_2, w_1\},\\ \{u_2, v_1, w_1\} \{u_1,v_2, w_2\}, \{u_2, v_1, w_2\},\) \(\{u_1,v_2, w_3\}, \{u_2, v_1, w_3\}\}\) be the edge set of its complement. Here \(d_H(u_1)=d_H(u_2)=d_H(v_1)=d_H(v_2)=3, ~d_H(w_1)=d_H(w_2)=d_H(w_3)=2\). Hence, \(H\) is quasi-regular. Now consider \(\sigma:V(H)\rightarrow V(H)\) given by \(\sigma(u_1)=v_1, \sigma(u_2)=v_2, \sigma(v_1)=u_2,~\sigma(v_2)=u_1\), \(\sigma(w_1)=w_1, \sigma(w_2)=w_2\), and \(\sigma(w_3)=w_3\). We observe that \(H\) is self-complementary with complementing permutation \(\sigma\). ◻
A \(3\)-partite \(3\)-uniform hypergraph \(H(V_1,V_2,V_3)\) such that \(|V_i|=n_i\), for \(i=1,2,3\) is almost self-complementary if it is isomorphic with its complement \(\bar{H}(V_1,V_2,V_3)\) with respect to \(\tilde{K}_{(n_1,n_2,n_3)}^3\).
This means that, a \(3\)-uniform hypergraph \(H(V_1,V_2, V_3)\) is almost self-complementary if \(\tilde{K}_{(n_1,n_2,n_3)}^3\) can be decomposed into two isomorphic factors with \(H(V_1,V_2, V_3)\) as one of the factors.
In [8], Kamble et al. proved that, “There exists a \(3\)-pasc \(H^3(V_1,V_2,V_3)\) where \(|V_i|=n_i\) for \(i=1,2,3\) if and only if all \(n_1,n_2,n_3\) are odd”. The authors analyzed the cycle structure of complementing permutations of \(3\)-pasc \(H(V_1,V_2, V_3)\). Following remark plays an important role in proving the existence of regular and quasi-regular \(3\)-pasc.
Remark 3.5. Let \(H(V_1,V_2, V_3)\), where \(|V_1|=n_1, |V_2|=n_2, |V_3|=n_3\) be a \(3\)-pasc with complementing permutation \(\sigma\). Let \(u_i\in V_i\) for some \(i=1, 2, 3\).
i) Suppose all cycles of \(\sigma\) are pure. That is \(\sigma(V_i)=V_i\) for \(i=1, 2, 3\). If \(u_i\) is not a special vertex, then \(d_H(u_i)+d_H(\sigma(u_i))=n_jn_k\) where \(j, k\neq i\) and if \(u_i\) is a special vertex, then \(d_H(u_i)+d_H(\sigma(u_i))=n_jn_k-1\) where \(j, k\neq i\).
ii) Suppose cycles of \(\sigma\) are mixed. If \(\sigma\) permutes vertices from all partitioned sets \(V_1\), \(V_2\) and \(V_3\) then \(n_1=n_2=n_3=n\). Furthermore, if \(v\in V\) is not a special vertex, then \(d_H(v)+d_H(\sigma (v))=n^2\) and if \(v\in V\) is a special vertex, then \(d_H(v)+d_H(\sigma (v))=n^2-1\).
iii) Suppose \(\sigma\) permutes vertices from any two partitioned sets say \(V_1\) and \(V_2\). That is \(\sigma(V_1)=V_2, \sigma(V_2)=V_1\) and \(\sigma(V_3)=V_3\). In this case \(n_1=n_2=n\). Furthermore, if \(v\in V_1\) or \(V_2\) is not a special vertex, then \(d_H(v)+d_H(\sigma (v))=nn_3\) and if \(v\) is a special vertex, then \(d_H(v)+d_H(\sigma (v))=nn_3-1\). Similarly, if \(v\in V_3\) is not a special vertex, then \(d_H(v)+d_H(\sigma (v))=n^2\) and if \(v\in V_3\) is a special vertex, then \(d_H(v)+d_H(\sigma (v))=n^2-1\).
We have if \(|V_1|=1, |V_2|=1, |V_3|=1\), then \(K^3_{(1,1, 1)}\) has only one edge, and \(\tilde K^3_{(1, 1,1)}\) is obtained by deleting that edge, which is the null hypergraph. And the null hypergraph on three vertices is regular of degree \(0\).
From the Remark 3.5, we observed that in almost complete \(3\)-pasc \(\tilde{K}_{(n_1,n_2,n_3)}^3\), the degree of special vertex and any other vertex always differ by 1. Hence, decomposition of \(\tilde{K}_{(n_1,n_2,n_3)}^3\) into two isomorphic factors \(H(V_1, V_2, V_3)\) and \(\bar H(V_1, V_2, V_3)\) such that both are regular is not possible. Hence, we conclude that there does not exist a regular \(3\)-pasc \(H(V_1, V_2,V_3)\) such that \(|V_1|=n_1, |V_2|=n_2, |V_3|=n_3\) and \(n_1, n_2, n_3 >1\). Hence, we get the following theorem.
Theorem 3.6. There does not exist a regular \(3\)-pasc \(H(V_1, V_2, V_3)\) with \(|V_i|=n_i, i=1, 2,3\) and \(n_i>1, i=1, 2, 3\).
Theorem 3.7. If there exists a quasi-regular \(3\)-pasc \(H(V_1,V_2, V_2)\) with \(|V_1|=n_1, |V_2|=n_2\) and \(|V_3|=n_3\), then \(n_1, n_2, n_3\) are odd and \(n_1=n_2=n_3\).
Proof. Suppose there exists a quasi-regular \(3\)-partite almost self-complementary \(3\)-uniform hypergraph \(H(V_1,V_2, V_2)\) with \(|V_1|=n_1, |V_2|=n_2\) and \(|V_3|=n_3\). From Result 2.9, we have \(n_1\), \(n_2\) and \(n_3\) are odd. Let \(\sigma\) be its corresponding complementing permutation.
Case 1. Suppose \(\sigma\) is pure complementing permutation. From the Remark 3.5, we have if \(u\in V_1\) is not a special vertex then \[d_H(u)+d_H(\sigma(u))=n_2\cdot n_3. \label{eqn11} \tag{12}\] Since \(H\) is quasi-regular by considering all possible values of degrees in Eq. (12), we get either \(q+q=n_2n_3\) or \(q+(q-1)=n_2n_3\) or \((q-1)+(q-1)=n_2n_3\). We have \(n_2\) and \(n_3\) are odd therefore we get \(q+(q-1)=n_2n_3\) that is \(2q-1=n_2n_3\).
If \(u\in V_1\) is a special vertex then \[d_H(u)+d_H(\sigma(u))=n_2\cdot n_3-1. \label{eqn12} \tag{13}\]
From Eq. (13) we get either \(q+q=n_2n_3-1\) or \(q+(q-1)=n_2n_3-1\) or \((q-1)+(q-1)=n_2n_3-1\). As \(n_2\) and \(n_3\) are odd we get \((q-1)+(q-1)=n_2n_3-1\) that is \(2q-1=n_2n_3\).
Hence, we get \(2q-1=n_2n_3\).
Similarly, if \(v\in V_2\) is not a special vertex then from the Remark 3.5 we get \[d_H(v)+d_H(\sigma(v))=n_1\cdot n_3. \label{eqn13} \tag{14}\]
That is, either \(q+q=n_1n_3\) or \(q+(q-1)=n_1n_3\) or \((q-1)+(q-1)=n_1n_3\). We have \(n_1\) and \(n_3\) are odd therefore we get \(q+(q-1)=n_1n_3\) that is \(2q-1=n_1n_3\).
If \(v\in V_2\) is a special vertex then \[d_H(v)+d_H(\sigma(v))=n_1\cdot n_3-1. \label{eqn14} \tag{15}\]
That is, either \(q+q=n_1n_3-1\) or \(q+(q-1)=n_1n_3-1\) or \((q-1)+(q-1)=n_1n_3-1\). As \(n_1\) and \(n_3\) are odd we get \((q-1)+(q-1)=n_1n_3-1\) that is \(2q-1=n_1n_3-1\).
Hence, we get \(2q-1=n_1n_3\).
And if \(w\in V_3\) is not a special vertex then \[d_H(w)+d_H(\sigma(w))=n_1\cdot n_2. \label{eqn6} \tag{16}\]
That is, either \(q+q=n_1n_2\) or
\(q+(q-1)=n_1n_2\) or \((q-1)+(q-1) =n_1n_2\). We have \(n_1\) and \(n_2\) are odd therefore we get \(2q-1=n_1n_2\).
If \(w\in V_3\) is a special vertex
then \[d_H(w)+d_H(\sigma(w))=n_1\cdot
n_2-1. \label{eqn7} \tag{17}\]
That is either \(q+q=n_1n_2-1\) or \(q+(q-1)=n_1n_2-1\) or \((q-1)+(q-1)=n_1n_2-1\). As \(n_1\) and \(n_2\) are odd we get \((q-1)+(q-1)=n_1n_2-1\) that is \(2q-1=n_1n_2\).
Hence, by considering all possible values of degrees in Eqs. (20) and (21), we get \(2q-1=n_1n_2\).
Hence, we get that \(2q-1=n_2n_2=n_1n_3=n_1n_2\). That is, \(n_1=n_2=n_3\).
Case 2. Suppose \(\sigma\) is mixed complementing permutation and \(\sigma\) permutes vertices of any two partitioned classes say \(V_1\) and \(V_2\) that is \(\sigma(V_1)=V_2, \sigma(V_2)=V_1\) and \(\sigma(V_3)=V_3\). In this case \(n_1=n_2\) say \(n\).
From the Remark 3.5, we have if \(u\in V_1\) or \(V_2\) is not a special vertex then \[d_H(u)+d_H(\sigma(u))=n\cdot n_3. \label{eqn2} \tag{18}\]
Since \(H\) is quasi-regular by considering all possible values of degrees in Eqs. (22), we get be get either \(q+q=nn_3\) or \(q+(q-1)=nn_3\) or \(q-1+(q-1)=nn_3\). We have \(n\) and \(n_3\) are odd therefore we get \(q+(q-1)=nn_3\) that is \(2q-1=nn_3\).
If \(u\in V_1\) or \(V_2\) is a special vertex then \[d_H(u)+d_H(\sigma(u))=n\cdot n_3-1. \label{eqn3} \tag{19}\]
That is, either \(q+q=nn_3-1\) or \(q+(q-1)=nn_3-1\) or \((q-1)+(q-1)=nn_3-1\). As \(n\) and \(n_3\) are odd we get \((q-1)+(q-1)=nn_3-1\) that is \(2q-1=nn_3\).
Hence, we get \(2q-1=nn_3\).
And if \(w\in V_3\) is not a special vertex then \[d_H(w)+d_H(\sigma(w))=n^2. \tag{20}\]
That is, either \(q+q=n^2\) or \(q+(q-1)=n^2\) or \((q-1)+(q-1)=n^2\). We have \(n\) is odd therefore we get \(2q-1=n^2\).
If \(w\in V_3\) is a special vertex then \[d_H(w)+d_H(\sigma(w))=n^2-1. \tag{21}\]
That is, either \(q+q=n^2-1\) or \(q+(q-1)=n^2-1\) or \((q-1)+(q-1)=n^2-1\). As \(n\) is odd we get \((q-1)+(q-1)=n^2-1\) that is \(2q-1=n^2\).
Hence, by considering all possible values of degrees in Eqs. (20) and (21), we get \(2q-1=n^2=n\cdot n_3\). This implies \(n=n_3\). Hence, we get \(n_1=n_2=n_3\).
Case 3. Suppose \(\sigma\) is mixed complementing permutation and \(\sigma\) permutes vertices of all partitioned classes. That is, \(\sigma(V_i)=V_j, \sigma(V_j)=V_k\) and \(\sigma(V_k)=V_i\) for \(i\neq j\neq k\). In this case \(n_1=n_2=n_3\) say \(n\).
The for any \(u\in V_i\) for \(i=1, 2, 3\) from the Remark 3.5, we have if \(u\) is not a special vertex then \[d_H(u)+d_H(\sigma(u))=n^2. \ \tag{22}\]
Since \(H\) is quasi-regular by considering all possible values of degrees in Eqs. (22), we get be get either \(q+q=n^2\) or \(q+(q-1)=n^2\) or \((q-1)+(q-1)=n^2\). We have \(n\) is odd therefore we get \(q+(q-1)=n^2\) that is \(2q-1=n^2\).
If \(u\in V_i\) is a special vertex then \[d_H(u)+d_H(\sigma(u))=n^2-1. \tag{23}\]
By considering all possible values of degrees in Eq. (23), we get
either \(q+q=n^2-1\) or \(q+(q-1)=n^2-1\) or \((q-1)+(q-1)=n^2-1\). As \(n\) is odd we get \((q-1)+(q-1)=n^2\) that is \(2q-1=n^2\).
Hence, \(2q-1=n^2\).
Therefore from case (I), case (II) and case (III) we get, if there exists a quasi-regular \(3\)-pasc \(H(V_1,V_2, V_2)\) with \(|V_1|=n_1, |V_2|=n_2\) and \(|V_3|=n_3\), then \(n_1, n_2, n_3\) are odd and \(n_1=n_2=n_3\). ◻