-partite self-complementary and almost self-complementary -uniform hypergraphs

Abstract

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,...,V_r$ so that every edge in the edge set $E\left(H\right)$, consists of precisely one vertex from each set $V_i$, $i=1,2,\dots ,r$. It is denoted as $H^r(V_1,V_2,\dots ,V_r)$ or $H_{(n_1,n_2,\dots ,n_r)}^r$ if $\left|V_i\right|=n_i$ for $i=1,2,\dots r$. In this paper we define $r$-partite self-complementary and almost self-complementary $r$-uniform hypergraph. We prove that, there exists an $r$-partite self-complementary $r$-uniform hypergraph $H^r(V_1,V_2,\dots ,V_r)$ where $\left|V_i\right|=n_i$ for $i=1,2,\dots ,r$ if and only if at least one of $n_1,n_2,\dots ,n_r$ is even. And we prove that, there exists an $r$-pasc $H^r(V_1,V_2,\dots ,V_r)$ where $\left|V_i\right|=n_i$ for $i=1,2,\dots ,r$ if and only if $n_1,n_2,\dots ,n_r$ are odd. Further, we analyze the cycle structure of complementing permutations of $r$-partite self-complementary $r$-uniform hypergraphs and $r$-partite almost self-complementary $r$-uniform hypergraphs.

Keywords:

• $r$-partite $r$-uniform hypergraph
• $r$-partite self-complementary $r$-uniform hypergraph
• $r$-partite almost self-complementary $r$-uniform hypergraph
• Complementing permutation

1 Introduction

Let $V$ be a finite set with $n$ vertices. By $\left(\genfrac{}{}{0ex}{}{V}{k}\right)$ we denote the set of all $k$-subsets of $V$. A $k$-uniform hypergraph is a pair $H=(V;E)$, where $E\subset \left(\genfrac{}{}{0ex}{}{V}{k}\right)$. $V$ is called a vertex set, and $E$ an edge set of $H$. Two $k$-uniform hypergraphs $H=(V;E)$ and $H^{\prime }=(V^{\prime };E^{\prime })$ are isomorphic if there is a bijection $\sigma :V\to V^{\prime }$ such that $\sigma$ induces a bijection of $E$ onto $E^{\prime }$. If $H=(V;E)$ is isomorphic to $H^{\prime }=(V;\left(\genfrac{}{}{0ex}{}{V}{k}\right)-E)$, then $H$ is called a self-complementary $k$-uniform hypergraph. Every permutation $\pi :V\to V$ which induces a bijection ${\pi }^{\prime }:E\to \left(\genfrac{}{}{0ex}{}{V}{k}\right)-E$ is called a self-complementing permutation.

A. Symański, A. P. Wojda [1–3] and S. Gosselin [4], independently characterized $n$ and $k$ for which there exist $k$-uniform self-complementary hypergraphs of order $n$ and gave the structure of corresponding complementing permutations.

A $k$-uniform hypergraph $H=(V;E)$ is called almost self-complementary if it is isomorphic with $H^{\prime }=(V;\left(\genfrac{}{}{0ex}{}{V}{k}\right)-E-\left\{e\right\})$ where $e$ is an element of the set $\left(\genfrac{}{}{0ex}{}{V}{k}\right)$. Almost self-complementary $k$-uniform hypergraph of order $n$ may be called self-complementary in $K_n^k-e$. The almost self-complementary 2-uniform hypergraphs i.e. almost self-complementary graphs are introduced by Clapham in [5]. In [6], almost self-complementary $3$-uniform hypergraphs are considered. And in [7], Wodja generalized corresponding results of [5] for $k=2$ and of [6] for $k=3$ for any $k\ge 2$.

A hypergraph $H$ is said to be $r$-partite $r$-uniform [8] if its vertex set $V$ can be partitioned into non-empty sets $V_1,V_2,\dots ,V_r$ so that every edge in the edge set $E\left(H\right)$, consists of precisely one vertex from each set $V_i$, $i=1,2,\dots ,r$. It is denoted as $H^r(V_1,V_2,\dots ,V_r)$ or $H_{(n_1,n_2,\dots ,n_r)}^r$ if $\left|V_i\right|=n_i$ for $i=1,2,\dots ,r$. An $r$-partite $r$-uniform hypergraph $H$ with the vertex set $V={\bigcup }_{i=1}^r{V}_i,V_i\cap V_j=\varphi ,\forall i\ne j$ and the edge set $E=\{e:e\subset V,\left|e\right|=r$ and $e\cap V_i\ne \varphi ,$ for $i=1,2,\dots ,r\}$ is called a complete $r$-partite $r$-uniform hypergraph. It is denoted as $K^r(V_1,V_2,\dots ,V_r)$ or $K_{(n_1,n_2,\dots ,n_r)}^r$. We observe that, the total number of edges in $K_{(n_1,n_2,\dots ,n_r)}^r$ is ${\prod }_{i=1}^r{n}_i$. Given an $r$-partite $r$-uniform hypergraph $H=H^r(V_1,V_2,\dots ,$ $V_r)$, we define its $r$-partite complement to be the $r$-partite $r$-uniform hypergraph $\bar{H}={\bar{H}}^r(V_1,V_2,\dots ,V_r)$ where $V\left(\bar{H}\right)=V\left(H\right)$ and $E\left(\bar{H}\right)=E\left(K^r(V_1,V_2,\dots ,V_r)\right)-E\left(H\right)$.

We say $\bar{H}$ is the complement of $H$ with respect to $K^r(V_1,V_2,\dots ,V_r)$. An $r$-partite $r$-uniform hypergraph $H=H^r(V_1,V_2,\dots ,V_r)=H^r\left(V\right)$ is said to be self-complementary if it is isomorphic to its $r$-partite complement $\bar{H}={\bar{H}}^r(V_1,V_2,\dots ,V_r)={\bar{H}}^r\left(V\right)$, that is there exists a bijection $\sigma :V\to V$ such that $e$ is an edge in $H$ if and only if $\sigma \left(e\right)$ is an edge in $\bar{H}$.

T. Gangopadhyay and S. P. Rao Hebbare [9] studied bi-partite self-complementary graphs, i.e. $2$-partite self-complementary $2$-uniform hypergraphs (r$=$2). They characterized the structural properties of bi-partite complementing permutations. In the present paper we study $r$-partite self-complementary $r$-uniform hypergraphs and $r$-partite almost self-complementary $r$-uniform hypergraphs.

In Section 2, we prove the existence of $r$-partite self-complementary $r$-uniform hypergraphs. In Section 3, we prove the existence of $r$-partite almost self-complementary $r$-uniform hypergraphs. In Sections 4 and 5 we analyze the cycle structure of complementing permutations of $r$-partite self-complementary $r$-uniform hypergraphs and the cycle structure of complementing permutations of $r$-partite almost self-complementary $r$-uniform hypergraphs respectively.

We use the shortform “$r$-psc” for $r$-partite self-complementary $r$-uniform hypergraph.

2 Existence of $r$-partite self-complementary $r$-uniform hypergraphs

The concept of an $r$-partite self-complementary $r$-uniform hypergraph with partition $(V_1,V_2,\dots ,V_r)$ of vertex set $V$ can be interpreted as a partitioning of the edge set of $K^r(V_1,V_2,\dots ,V_r)$ into two isomorphic factors. We note that a partitioning of the edge set of $K^r(V_1,V_2,\dots ,V_r)$ into two isomorphic factors is possible only if $K^r(V_1,V_2,\dots ,V_r)$ has an even number of edges i.e. ${\prod }_{i=1}^r{n}_i$ is even and this is true if and only if at least one of $n_1,n_2,\dots ,n_r$ is even. Conversely if we can construct an $r$-psc given that at least one $n_i$ is even then we get a necessary and sufficient condition for existence of $r$-psc. Towards this we have the following theorem.

Theorem 2.1

There exists an $r$-psc $H^r(V_1,V_2,\dots ,V_r)$ where $\left|V_i\right|=n_i$ for $i=1,2,\dots ,r$ if and only if at least one of $n_1,n_2,\dots ,n_r$ is even.

Proof

Firstly we construct an $r$-psc $H^r(V_1,V_2,\dots ,V_r)$ given that at least one of $\left|V_i\right|=n_i,i=1,2,\dots ,r$ is even. Without loss of generality, let us suppose that $n_1$ is even. That is $n_1=2t$ for some positive integer $t$ (say).

Let $V_i=\{u_1^i,u_2^i,\dots ,u_{n_i}^i\}$ for $i=1,2,\dots ,r$. Consider the complete $(r-1)$-partite $(r-1)$-uniform hypergraph, $K^{r-1}(V_2,V_3,\dots ,V_r)=K_{n_2,n_3,\dots ,n_r}^{r-1}$.

Consider the following partition of edge set of $K_{n_1,n_2,n_3,\dots ,n_r}^r$.

$E=\{e\cup \left\{u_j^1\right\}\mid e$ is an edge in $K_{n_2,n_3,\dots ,n_r}^{r-1}$ and $j=1,3,\dots ,2t-1\}$

$\bar{E}=\{e\cup \left\{u_j^1\right\}\mid e$ is an edge in $K_{n_2,n_3,\dots ,n_r}^{r-1}$ and $j=2,4,\dots ,2t\}$.

Let $H=H^r(V_1,V_2,\dots ,V_r)$ be the $r$-partite $r$-uniform hypergraph with edge set $E$. Fig. 1 gives a diagrammatic description of $H$. To prove that $H$ is $r$-psc, we define a bijection $\sigma :V\left(H\right)\to V\left(H\right)$ as $\sigma ={\prod }_{i=1}^r(u_1^i{u}_2^i...u_{n_i}^i)$. It can be easily checked that $H=H^r(V_1,V_2,\dots ,V_r)$ is self-complementary with $\sigma$ as its complementing permutation.

Fig. 1 Edge set of $H_{(n_1,n_2,\dots ,n_r)}^r$ and ${\bar{H}}_{(n_1,n_2,\dots ,n_r)}^r$.

It is clear that the partitioning of the edge set of $K^r(V_1,V_2,\dots ,V_r)$ into two isomorphic factors is not possible when $K^r(V_1,V_2,\dots ,V_r)$ has an odd number of edges. In the next section we define an $r$-partite almost self-complementary $r$-uniform hypergraph and give a condition on number of vertices for its existence.

3 Existence of $r$-partite almost self-complementary $r$-uniform hypergraphs

Definition 3.1

Almost Complete $r$-partite $r$-uniform Hypergraph The hypergraph ${\tilde{K}}_{(n_1,n_2,\dots ,n_r)}^r=K_{(n_1,n_2,\dots ,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,\dots ,n_r)}^r$ called the deleted edge. Vertices of $e$ will be called the special vertices.

Definition 3.2

Almost Self-complementary $r$-partite $r$-uniform Hypergraph An $r$-partite $r$-uniform hypergraph $H(V_1,V_2,\dots ,V_r)$ such that $\left|V_i\right|=n_i$ for $i=1,2,\dots ,r$ is almost self-complementary if it is isomorphic with its complement $\bar{H}(V_1,V_2,\dots ,V_r)$ with respect to ${\tilde{K}}_{(n_1,n_2,\dots ,n_r)}^r$.

We use the shortform “$r$-pasc” for $r$-partite almost self-complementary $r$-uniform hypergraph.

A complete $r$-partite $r$-uniform hypergraph will have an odd number of edges if each of $n_1,n_2,\dots ,n_r$ is odd. In the next theorem we prove that this condition is sufficient as well for the existence of an $r$-pasc. The proof is constructive in nature. Since the special vertices are to be treated differently and since each set in the partition contains exactly one special vertex, we start with $V_i=V_i^{\prime }\cup \left\{x_i\right\}$ such that $V_i^{\prime }$ contains even number of vertices for $i=1,2,\dots ,r$. To construct $r$-pasc, we consider the complete $r-1$-partite $r-1$-uniform hypergraph on $V_2,V_3,\dots ,V_r$ and then add each vertex of $V_1$ on each of these edges in such a way that we get the desired construction. The idea is the same as in the construction of Theorem 2.1.

Theorem 3.3

There exists an $r$-pasc $H^r(V_1,V_2,\dots ,V_r)$ where $\left|V_i\right|=n_i$ for $i=1,2,\dots ,r$ if and only if $n_1,n_2,\dots ,n_r$ are odd.

Proof

We construct an $r$-pasc $H^r(V_1,V_2,\dots ,V_r)$ where $\left|V_i\right|=n_i$ for $i=1,2,\dots ,r$ when each $n_i$ is odd. Let $n_i=2t_i+1$, for some positive integer $t_i$, for $i=1,2,\dots ,r$.

Let $V_i^{\prime }=\{u_1^i,u_2^i,\dots ,u_{2t_i}^i\}$ and $V_i=V_i^{\prime }\cup \left\{x_i\right\}$, for $i=1,2,\dots ,r$.

Consider the complete $r-1$-partite $r-1$-uniform hypergraph $K_{(n_2,n_3,\dots ,n_r)}^{r-1}$ with edge set $E\left(K\right)$.

Consider the following partition of the edge set of ${\tilde{K}}_{(n_1,n_2,n_3,\dots ,n_r)}^r$, where $\{x_1,x_2,\dots ,x_r\}$ is the deleted edge.

$E_1=\{e\cup \left\{u_i^1\right\}\mid e$ $\in E\left(K\right),i=1,3,\dots ,2t_1-1\}$,

${\bar{E}}_1=\{e\cup \left\{u_i^1\right\}\mid e$ $\in E\left(K\right),i=2,4,\dots ,2t_1\}$,

$E_{x_1}=\{\{x_1,u_{p_2}^2,u_{p_3}^3,\dots ,u_{p_r}^r\}\mid u_{p_i}^i\in V_i^{\prime },$ and $i=2,3,\dots ,r$ and $p_2=1,3,\dots ,2t_2-1\}$,

${\bar{E}}_{x_1}=\{\{x_1,u_{p_2}^2,u_{p_3}^3,\dots ,u_{p_r}^r\}\mid u_{p_i}^i\in V_i^{\prime },$ and $i=2,3,\dots ,r$ and $p_2=2,4,\dots ,2t_2\}$.

Now we have to consider edges containing $k$ special vertices along with $x_1$ for $k=1,2,\dots ,r-2$. For a given $k$, we have to consider all combinations of $k$ special vertices $x_{j_1},x_{j_2},\dots ,x_{j_k}$ from $r-1$ special vertices and remaining $r-k-1$ vertices from $V_{s_1}^{\prime },V_{s_2}^{\prime },\dots ,V_{r-k-1}^{\prime }$ where $j_1,j_2,\dots ,j_k,s_1,s_2,\dots ,s_{r-k-1}$ are distinct and belong to the set $\{2,3,\dots ,r\}$.

Let $\left(r\right)=\{2,3,\dots ,r\}$. For $k=1,2,\dots ,r-2$, let $J_k=\{j_1,j_2,\dots ,j_k\}\subset \left(r\right)$ and $J_k^{\prime }=\{s_1,s_2,\dots ,s_{r-k-1}\}=\left(r\right)\setminus J_k$. Note that for each $k$, there are $\left(\genfrac{}{}{0ex}{}{r-1}{k}\right)$ several $k$-subsets $J_k$. We consider all possible $k$-subsets.

For given $k$, we divide the edges containing $k$ special vertices along with $x_1$ into two parts as follows.

Let,

$E_{x_1{x}_{j_1}{x}_{j_2}...x_{j_k}}=\{\{x_1,x_{j_1},x_{j_2},\dots ,x_{j_k},u_{p_{s_1}}^{s_1},u_{p_{s_2}}^{s_2},\dots ,u_{p_{s_{r-k-1}}}^{s_{r-k-1}}\}\mid j_1,j_2,\dots ,j_k\in J_k,$ $x_{j_m}\in V_{j_m},m=1,2,\dots ,k;s_1,\dots ,s_{r-k-1}\in J_k^{\prime },u_{p_{s_i}}^{s_i}\in V_{s_i}^{\prime },i=1,2,3,\dots ,r-k-1,$ and $p_{s_1}=1,3,5,\dots ,2t_{s_1}-1\}$.

${\bar{E}}_{x_1{j}_1{j}_2...j_k}=\{\{x_1,x_{j_1},x_{j_2},\dots ,x_{j_k},u_{p_{s_1}}^{s_1},u_{p_{s_2}}^{s_2},\dots ,u_{p_{s_{r-k-1}}}^{s_{r-k-1}}\}\mid j_1,j_2,\dots ,j_k\in J_k,$ $x_{j_m}\in V_{j_m},m=1,2,\dots ,k;s_1,\dots ,s_{r-k-1}\in J_k^{\prime },u_{p_{s_i}}^{s_i}\in V_{s_i}^{\prime },i=1,2,3,\dots ,r-k-1,$ and $p_{s_1}=2,4,6,\dots ,2t_{s_1}\}$.

Since $k\le r-2,r-k-1\ge 1$. Hence the above partition is always a valid partition.

For given $k$ let, $E_{x_1}^k={\bigcup }_{J_k\subset \left(r\right)}{E}_{x_1{x}_{j_1}{x}_{j_2}...x_{j_k}}$ and ${\bar{E}}_{x_1}^k={\bigcup }_{J_k\subset \left(r\right)}{\bar{E}}_{x_1{x}_{j_1}{x}_{j_2}...x_{j_k}}$.

Clearly, $E_1\cup {\bar{E}}_1\cup E_{x_1}\cup {\bar{E}}_{x_1}\cup ({\bigcup }_{k=1}^{r-2}{E}_{x_1}^k\cup {\bar{E}}_{x_1}^k)$ gives a partition of the edge set of ${\tilde{K}}^r(V_1,V_2,\dots ,V_r)$.

Let $H=H^r(V_1,V_2,\dots ,V_r)$ be the $r$-partite $r$-uniform hypergraph with edge set $E=E_1\cup E_{x_1}\cup \left({\bigcup }_{k=1}^{r-2}{E}_{x_1}^k\right)$. To prove $H$ is $r$-pasc we define a bijection $\sigma :V\left(H\right)\to V\left(H\right)$ such that $\sigma ={\prod }_{i=1}^k\left((u_1^i{u}_2^i...u_{n_i-1}^i)\left(x_i\right)\right)$. It can be easily checked that $H=H^k(V_1,V_2,\dots ,V_k)$ is almost self-complementary with $\sigma$ as its complementing permutation.

4 Complementing permutations of $r$-partite self-complementary $r$-uniform hypergraphs

Let $V=\{V_1,V_2,\dots ,V_r\}$ be a partition of $V$. Any edge of $K^r(V_1,V_2,\dots ,V_r)$ is a $r$-subset of $V$ containing exactly one vertex from each of the partitioned sets $V_i$, $i=1,2,\dots ,r$. Hence it is of the form $e=\{u_1,u_2,\dots ,u_r\}$ where $u_i\in V_i$, $i=1,2,\dots ,r$. If any $r$-subset of $V$ contains more than one vertex from any one of the partitioned sets then we call it as an invalid edge. Hence any $r$-subset (r-tuple) of vertices in $V$ is an invalid edge if and only if it contains at least two vertices from the same set of the partition. A permutation $\sigma$ on $V$ is said to a complementing permutation of an $r$-psc $H$, if $\sigma \left(e\right)$ is an edge in $E\left(\bar{H}\right)$ whenever $e$ is an edge in $H$. If $\sigma$ is a complementing permutation then the corresponding mapping induced on the set of edges of $K_{(n_1,n_2,\dots ,n_r)}^r$ is denoted by ${\sigma }^{\prime }$.

Definition 4.1

Let $V=\{V_1,V_2,\dots ,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 4.2

Let $V=\{V_1,V_2,\dots ,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\le j\le 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.

First we characterize those permutations $\sigma$ on $V$ for which $\sigma \left(e\right)$ is an edge in $K_{(n_1,n_2,\dots ,n_r)}^r$ whenever $e$ is an edge in $K_{(n_1,n_2,\dots ,n_r)}^r$. We call such permutation as a valid permutation.

Lemma 4.3

Let $V=\{V_1,V_2,\dots ,V_r\}$ be a partition of $V$ and $\sigma$ be a valid permutation on $V$. If $C$ is a cycle of $\sigma$ containing two consecutive vertices from a single set of the partition say $V_i$ for some $i,1\le i\le r$ then $\sigma$ must contain ${\sigma }_{p_i}$ where ${\sigma }_{p_i}$ is a pure permutation on $V_i$.

Proof

If $C$ is a $2$-cycle then we are done.

Let $C=(u_1{u}_2{v}_1{v}_2{v}_3\cdots v_j),j\ge 1$ such that $u_1,u_2\in V_i$.

Claim 1: $v_1,v_2,\dots ,v_j\in V_i$.

Proof of 1: Suppose not. That is for at least one $k,1\le k\le j$, $v_k\notin V_i$. Choose that $k$ for which $v_k\notin V_i$ and $\sigma \left(v_k\right)\in V_i$. This is possible since $C=(u_1{u}_2{v}_1{v}_2\cdots v_j),j\ge 1$ is a cycle of $\sigma$ with $u_1\in V_i$. Now $u_1,v_k$ belong to different sets of the partition and hence any valid edge containing $u_1$ and $v_k$ will give $\sigma \left(u_1\right)$ and $\sigma \left(v_k\right)$ both belonging to $V_i$, thus giving an invalid edge, a contradiction to $\sigma$ is valid.

Claim 2: If there exists $u\in V_i$ not belonging to the cycle $C$ then $u$ belongs to $C^{\prime }$ where $C^{\prime }$ is another cycle of $\sigma$ disjoint from $C$ and contains vertices only from $V_i$.

Proof of claim 2: Let $C^{\prime }=(u{w}_1{w}_2\cdots w_k)$ where at least one of the $w_1,w_2,\dots ,w_k$ (if any such exists) does not belong to $V_i$. Choose $w_s$ such that $w_s\notin V_i$ and $\sigma \left(w_s\right)\in V_i$. Such a choice is possible since $u\in V_i$ and $C^{\prime }=(u{w}_1{w}_2\cdots w_k)$ is a cycle of $\sigma$. Now any valid edge containing $u_1,w_s$ from different sets will give an invalid edge containing $\sigma \left(u_1\right),\sigma \left(w_s\right)$ from some $V_i$, a contradiction to $\sigma$ is valid.

Hence $\sigma$ contains ${\sigma }_{p_i}$.

Lemma 4.4

Let $V=\{V_1,V_2,\dots ,V_r\}$ be a partition of $V$ and $\sigma$ be a valid permutation on $V$. If $C$ is a cycle of $\sigma$ containing vertices from $V_1,V_2,\dots ,V_t,$ $t\ge 2$ then

(i) $C=(u_1{u}_2\cdots u_t{u}_{t+1}{u}_{t+2}\cdots u_{2t}\cdots u_{(q-1)t+1}\cdots u_{qt})$ where $u_{it+j}\in V_j$ for all $i=0,1,\dots ,q-1$ and $j=1,2,\dots ,t$.

(ii) $\sigma$ must contain ${\sigma }_{m_t}$ where ${\sigma }_{m_t}$ is a mixed permutation on $V_1,V_2,\dots ,V_t$.

Proof

Since $C$ is a cycle containing vertices from $V_1,V_2,\dots ,V_t$, it must have length at least $t$ and because of Lemma 4.3 no two consecutive vertices of $C$ belong to the same set of the partition. The first $t$ vertices of $C$ must be one each from $V_1,V_2,\dots ,V_t$ in some order. If not that is suppose $C=(u_1{u}_2\cdots u_t\cdots )$ such that $u_i,u_j\in V_k$ with $i$ and $j$ are not consecutive and $u_{i-1},u_{j-1}$ belong to different $V_i$’s for $i=1,2,\dots ,t$ then any valid edge containing $u_{i-1}$ and $u_{j-1}$ will give $\sigma \left(u_{i-1}\right)=u_i$ and $\sigma \left(u_{j-1}\right)=u_j$ both belonging to $V_k$, giving an invalid edge, a contradiction. Without loss of generality let $C=(u_1,u_2,\dots ,u_t,\dots )$ where $u_j\in V_j,j=1,2,\dots ,t$.

Claim 1: $C=(u_1{u}_2\cdots u_t{u}_{t+1}{u}_{t+2}\cdots u_{2t}\cdots u_{(q-1)t+1}\cdots u_{qt})$, for $q\ge 1$ where $u_{it+j}\in V_j$ for all $i=1,2,\dots ,q-1$ and $j=1,2,\dots ,t$.

Proof of claim 1: Suppose not. Let $s$ and $k$ be the smallest such that $u_{st+k}\notin V_k$. That is $u_{st+k}\in V_j$ for some $j\ne k$.

Case (i) Suppose $k=1$. That is $u_{st+1}\notin V_1$. Then $u_{st+1}\in V_j$ for some $j\ne 1$. That is $u_{st+1}\in V_j,1<j\le t$. We have $u_{j-1}\in V_{j-1}$ and $u_{st}\in V_t$. Hence $u_{j-1}$ and $u_{st}$ belong to a valid edge but $\sigma \left(u_{j-1}\right)=u_j$ and $\sigma \left(u_{st}\right)=u_{st+1}$ both belong to $V_j$, a contradiction to $\sigma$ is valid.

Case (ii) Suppose $k>1$. $u_{st+k}\in V_j,j\ge 1,j\ne k$.

Suppose $j=1$, that is $u_{st+k}\in V_1$. We have that $u_{st}\in V_t$ and $u_{st+(k-1)}\in V_{k-1}$. Thus $u_{st}$ and $u_{st+(k-1)}$ belong to a valid edge whereas $\sigma \left(u_{st}\right)=u_{st+1}$ and $\sigma \left(u_{st+(k-1)}\right)=u_{st+k}$ both belong to $V_1$, a contradiction.

Suppose $j>1$. We have $u_{j-1}\in V_{j-1}$ and $u_{st+(k-1)}\in V_{k-1}$. Thus $u_{j-1}$ and $u_{st+(k-1)}$ belong to a valid edge but $\sigma \left(u_{j-1}\right)=u_j$ and $\sigma \left(u_{st+(k-1)}\right)=u_{st+k}$ both belong to $V_j$, which is a contradiction.

Hence length of $C$ must be multiple of $t$.

Claim 2: Every cycle of $\sigma$ containing the vertices from $V_1,V_2,\dots ,V_t,t\ge 2$ must be of the above type $C$ with the same ordering of $V_1,V_2,\dots ,V_t$.

Proof of claim 2: Suppose $\sigma$ contains a cycle $C^{\prime }(\ne C)$ containing vertices from $V_1,V_2,\dots ,V_t$. Suppose for some $v_i\in V_i$ in $C^{\prime }$, $\sigma \left(v_i\right)\in V_k,k\ne i+1$ then for any edge $e$ containing $u_{k-1}$ in $C$ and $v_i$, $\sigma \left(e\right)$ is an invalid edge, a contradiction.

Claim 3: All the vertices of $V_1,V_2,\dots ,V_t$ belong to cycles of type $C$.

Proof of claim 3: Suppose not. That is there is a cycle $C^{\prime \prime }$ in $\sigma$ containing vertices from at least one of the sets $V_1,V_2,\dots ,V_t$ and vertices from $S=\{V_{t+1},V_{t+2},\dots ,V_r\}$. Without loss, let us suppose that $C^{\prime \prime }$ contain vertices from $V_1$ and $S$. Choose a vertex $u\in V_j$ where $V_j\in S$ from $C^{\prime \prime }$ such that $\sigma \left(u\right)\in V_1$. Clearly, $u\notin V_t$ and $u_{qt}$ in $C$ belongs to $V_t$. Any valid edge $e$ containing $u$ and $u_{qt}$ gives $\sigma \left(e\right)$ to be invalid, a contradiction.

Hence $\sigma$ must contain ${\sigma }_{m_t}$.

Further, $\left|V_1\right|=\left|V_2\right|=\cdots =\left|V_t\right|=q^{\prime }t$ for some $q^{\prime }\ge 1$.

From Lemmas 4.3 and 4.4 we immediately get the following theorem which characterizes all valid permutations.

Theorem 4.5

(i) Any valid permutation $\sigma$ on $V$ is of the form $\sigma ={\prod }_{i=1}^k{\sigma }_{m_{t_i}}$ ${\prod }_{j=1}^s{\sigma }_{p_j}$, where ${\sigma }_{m_{t_i}}$ is a mixed permutation on $V_{t_1+t_2+\cdots +t_{i-1}+1},$

$V_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,V_{t_1+t_2+\cdots +t_{i-1}+t_i}$ for $i=1,2,\dots ,k$ such that $t_1+t_2+\cdots +t_k=t$ and ${\sigma }_{p_j}\left(V_{t+j}\right)=V_{t+j}$ for $j=1,2,\dots ,s$ and $t+s=r$.

$\left(ii\right)$ There cannot be a mixed permutation on $V_1,V_2,\dots ,V_t$ unless $\left|V_1\right|=\left|V_2\right|=\cdots =\left|V_t\right|=qt$, for some $q\ge 1$.

The following remark gives a relation between the length of a cycle containing a particular edge in ${\sigma }^{\prime }$ and the lengths of cycles in $\sigma$ containing the vertices of that edge where $\sigma$ is a valid permutation.

Remark 4.6

Let $e^{\prime }=\{u_1,u_2,\dots ,u_r\}$ be any edge in $K_{n_1,n_2,\dots ,n_r}^r$. Then the length of the cycle in ${\sigma }^{\prime }$ containing the edge $e^{\prime }$ is the least common multiple of the lengths of cycles in $\sigma$ containing the vertices $u_1,u_2,\dots ,u_r$ except for the edge which contains $t$ vertices $u_{i_1},u_{i_2},\dots ,u_{i_t}$ which belong to a cycle $C$ of mixed permutation ${\sigma }_m$ on $t$ sets (out of $V_1,V_2,\dots ,V_r$) of length $qt$ such that $u_{i_{j+1}}={\sigma }^q\left(u_{i_j}\right)$ for $j=1,2,\dots ,t$. For such an edge, length of the corresponding cycle in ${\sigma }^{\prime }$ depends on $q$ instead of $qt$. Further $\sigma$ will be a complementing permutation if and only if every cycle in the induced mapping ${\sigma }^{\prime }$ is of even length.

Following theorem gives the cycle structure of the complementing permutation of an $r$-psc.

Theorem 4.7

A permutation $\sigma$ is a complementing permutation of $r$-psc $H^r(V_1,V_2,\dots ,V_r)$ if and only if following hold

(i) $\sigma$ is valid, that is $\sigma ={\prod }_{i=1}^k{\sigma }_{m_{t_i}}{\prod }_{j=1}^s{\sigma }_{p_j}$, where ${\sigma }_{m_{t_i}}$ is a mixed permutation on $V_{t_1+t_2+\cdots +t_{i-1}+1},$ $V_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,V_{t_1+t_2+\cdots +t_{i-1}+t_i}$ for $i=1,2,\dots ,k$ such that $t_1+t_2+\cdots +t_k=t$ and ${\sigma }_{p_j}\left(V_{t+j}\right)=V_{t+j}$ for $j=1,2,\dots ,s$ and $t+s=r$.

(ii) either all the cycles in ${\sigma }_{m_{t_i}}$ are of length even multiple of $t_i$ for at least one $i$, $i=1,2,\dots ,k$ or all the cycles in ${\sigma }_{p_j}$ are of even length for at least one $j$, $j=1,2,\dots ,s$ .

Proof

Suppose $\sigma$ is a complementing permutation of an $r$-psc $H^r(V_1,V_2,\dots ,V_r)$. Clearly, $\sigma$ must be valid. From Theorem 4.5, we have that $\sigma ={\prod }_{i=1}^k{\sigma }_{m_{t_i}}{\prod }_{j=1}^s{\sigma }_{p_j}$. For convenience we denote ${\sigma }_{m_{t_i}}$ by ${\sigma }_{m_i}$.

Firstly we prove that for at least one $i$, $i=1,2,\dots ,k$ either all the cycles in ${\sigma }_{m_i}$ are of length even multiple of $t_i$ or for at least one $j$, $j=1,2,\dots ,s$ all cycles in ${\sigma }_{p_j}$ are of even length.

Suppose not. That is for each $i,i=1,2,\dots ,k$, ${\sigma }_{m_i}$ contains at least one cycle of length odd multiple of $t_i$ and for each $j,j=1,2,\dots ,s$, ${\sigma }_{p_j}$ contains at least one cycle of odd length. Let for each $i=1,2,\dots ,k$, $C_i$ be a cycle in ${\sigma }_{m_i}$ of length odd multiple of $t_i$ and for $j=1,2,\dots ,s$, $C_j^{\prime }$ be a cycle in ${\sigma }_{p_j}$ of odd length. Let length of $C_i$ be $q_i{t}_i$ where $q_i$ is odd for $i=1,2,\dots ,k$ and length of $C_j^{\prime }$ be $L_j^{\prime }$ where $L_j^{\prime }$ is odd for $j=1,2,\dots ,s$. Let $u_i\in C_i,i=1,2,\dots ,k$ and $v_j\in C_j^{\prime },j=1,2,\dots ,s$.

Consider the edge, $$e^{\prime }=\{u_1,{\sigma }^{q_1}\left(u_1\right),{\sigma }^{2q_1}\left(u_1\right),\dots ,{\sigma }^{(t_1-1)q_1}\left(u_1\right),u_2,{\sigma }^{q_2}\left(u_2\right),{\sigma }^{2q_2}\left(u_2\right),\dots ,{\sigma }^{(t_2-1)q_2}\left(u_2\right),\dots ,u_k,{\sigma }^{q_k}\left(u_k\right),{\sigma }^{2q_k}\left(u_k\right),\dots ,{\sigma }^{(t_k-1)q_k}\left(u_k\right),v_1,v_2,\dots ,v_s\}$$in $K_{(n_1,n_2,\dots ,n_r)}^r$. The length of the cycle of ${\sigma }^{\prime }$ containing the edge $e^{\prime }$ is the least common multiple of $q_1,q_2,\dots ,q_k,L_1^{\prime },L_2^{\prime },\dots ,L_s^{\prime }$ which is odd, a contradiction. Hence, either at least one $q_i,i=1,2,\dots ,k$ is even or at least one $L_j^{\prime },j=1,2,\dots ,s$ is even. Therefore, either for at least one $i$, $i=1,2,\dots ,k$ all the cycles in ${\sigma }_{m_i}$ are of length even multiple of $t_i$ or for at least one $j$, $j=1,2,\dots ,s$ all the cycles in ${\sigma }_{p_j}$ are of even length.

The following result proved by Gangopadhyay and S. P. Rao Hebbare [9], on the cycle structure of the complementing permutations of a bipartite self-complementary graph (2-partite self-complementary 2-uniform hypergraphs) follows from Theorem 4.7.

Corollary 4.8

A permutation $\sigma$ is a complementing permutation of bipartite self-complementary graph $G(V_1,V_2)$ if and only if either

(i) $\sigma ={\sigma }_{p_1}{\sigma }_{p_2}$ with all cycles in ${\sigma }_{p_1}$ or ${\sigma }_{p_2}$ are of even length or (ii) $\sigma ={\sigma }_m$ and every cycle of ${\sigma }_m$ is of length a multiple of $4$ and takes vertices alternately from $V_1$ and $V_2$.

5 Complementing permutations of $r$-partite almost self-complementary $r$-uniform hypergraphs

Given an $r$-pasc $H$, let the edges of $H$ be colored red and the remaining edges of ${\tilde{K}}_{(n_1,n_2,\dots ,n_r)}^r$ be colored green. Since the 2 factors are isomorphic, there is a permutation $\sigma$ of the vertices of ${\tilde{K}}_{(n_1,n_2,\dots ,n_r)}^r$ that induces a mapping of the red edges onto the green edges. We consider $\sigma$ as a permutation of the vertices of $K_{(n_1,n_2,\dots ,n_r)}^r$ and denote by ${\sigma }^{\prime }$ the corresponding mapping induced on the set of edges of $K_{(n_1,n_2,\dots ,n_r)}^r$. Thus ${\sigma }^{\prime }$ maps each red edge onto a green edge. However, the mapping ${\sigma }^{\prime }$ need not necessarily map each green edge onto a red edge. This would be so if ${\sigma }^{\prime }$ mapped $e$ onto itself, but it may be that ${\sigma }^{\prime }$ maps $e$ onto a red edge and some green edge onto e. Such a $\sigma$ (which, for definiteness we shall always assume induces a mapping from red to green) will (as for $r$-psc) be called a complementing permutation. It will be useful to consider the cycles of the induced mapping ${\sigma }^{\prime }$.

For the rest of the section we denote the deleted edge by $e=\{x_1,x_2,\dots ,x_r\}$ where $x_i\in V_i$ for $i=1,2,\dots ,r$ and call it as the missing edge. And the corresponding vertices $x_1,x_2,\dots ,x_r$ are called as the special vertices.

It is clear that the length of the cycle of ${\sigma }^{\prime }$ containing the edge $e=\{x_1,x_2,\dots ,x_r\}$ must be odd and all the other cycles of ${\sigma }^{\prime }$ must be of even length.

If $\sigma$ is any permutation on $V$, for $\sigma$ to be a complementing permutation it has to be valid and hence Theorem 4.5 holds. Remark 4.6 gives the relation between the lengths of cycles in $\sigma$ and ${\sigma }^{\prime }$. In addition an extra requirement that exactly one cycle of ${\sigma }^{\prime }$ containing the deleted edge is of odd length and all the other cycles of ${\sigma }^{\prime }$ are of even length changes the cycle structure of complementing permutation of $r$-pasc from that of $r$-psc. And we have the following theorem.

Theorem 5.1

A permutation $\sigma$ is a complementing permutation of $r$-pasc $H^r(V_1,V_2,\dots ,V_r)$ if and only if $\sigma$ is valid, that is $\sigma ={\prod }_{i=1}^k{\sigma }_{m_{t_i}}{\prod }_{j=1}^s{\sigma }_{p_j}$ where each ${\sigma }_{m_{t_i}},i=1,2,\dots ,k$ permutes vertices belonging to $t_i$ number of sets of the partition $V_{t_1+t_2+\cdots +t_{i-1}+1},V_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,V_{t_1+t_2+\cdots +t_{i-1}+t_i}$ and ${\sigma }_{p_j}\left(V_{t+j}\right)=V_{t+j}$ for $j=1,2,\dots ,s$ and $t+s=r$. Further, either

$\left(1\right)$ $\sigma ={\prod }_{i=1}^k{\sigma }_{m_{t_i}}{\prod }_{j=1}^s{\sigma }_{p_j}$ where ${\prod }_{j=1}^s{\sigma }_{p_j}=\left(x_{t+1}\right)\cdots \left(x_{t+s}\right){\prod }_{\alpha }{C}_{\alpha }$, where each $C_{\alpha }$ is a cycle of even length containing vertices from a single set of the partition. And for $i=1,2,\dots ,k$, ${\sigma }_{m_{t_i}}=(x_{t_1+t_2+\cdots +t_{i-1}+1}{x}_{t_1+t_2+\cdots +t_{i-1}+2}\cdots x_{t_1+t_2+\cdots +t_{i-1}+t_i}){\prod }_{\beta }{C}_{\beta }$, where each $C_{\beta }$ is a valid mixed cycle of length even multiple of $t_i$ containing vertices from $V_{t_1+t_2+\cdots +t_{i-1}+1},V_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,V_{t_1+t_2+\cdots +t_{i-1}+t_i}$.

or

$\left(2\right)$ Among all the ${\sigma }_{p_j}$’s, $j=1,2,\dots ,s$, exactly one ${\sigma }_{p_j}$ say ${\sigma }_{p_1}$ is such that ${\sigma }_{p_1}=C{\prod }_{\gamma }{C}_{\gamma }$ where $C$ is a cycle of odd length greater than 1 containing the vertex $x_{t+1}$ and $C_{\gamma }$ is a cycle of even length containing vertices from $V_{t+1}$. Hence $\sigma =\left({\prod }_{i=1}^k{\sigma }_{m_{t_i}}\right)\left({\prod }_{j=2}^s{\sigma }_{p_j}\right){\sigma }_{p_1}$ where ${\prod }_{j=2}^s{\sigma }_{p_j}=\left(x_{t+2}\right)\cdots \left(x_{t+s}\right){\prod }_{\alpha }{C}_{\alpha }$ where each $C_{\alpha }$ is a cycle of even length containing vertices from a single set of the partition. For each $i=1,2,\dots ,k$, ${\sigma }_{m_{t_i}}$ is as in $\left(1\right)$.

or

$\left(3\right)$ Among all the ${\sigma }_{m_{t_i}}$’s, $i=1,2,\dots ,k$, exactly one ${\sigma }_{m_{t_i}}$ say ${\sigma }_{m_{t_1}}$ is such that ${\sigma }_{m_{t_1}}=C{\prod }_{\delta }{C}_{\delta }$ where $C$ is a valid mixed cycle on $V_1,V_2,\dots ,V_{t_1}$ having length odd multiple $q_1$ of $t_1$ ( $q_1>1)$, $t_1$ is even and $C$ contains the special vertices $x_1,x_2,\dots ,x_{t_1}$ such that ${\sigma }^{q_1}\left(x_1\right)=x_2,{\sigma }^{q_1}\left(x_2\right)=x_3,\dots ,{\sigma }^{q_1}\left(x_{t_1-1}\right)=x_{t_1},{\sigma }^{q_1}\left(x_{t_1}\right)=x_1$ and all other vertices from $V_1,V_2,\dots ,$ $V_{t_1}$. Each $C_{\delta }$ is a valid mixed cycle on $V_1,V_2,\dots ,V_{t_1}$ of length even multiple of $t_1$. Hence $\sigma ={\sigma }_{m_{t_1}}\left({\prod }_{i=2}^k{\sigma }_{m_{t_i}}\right)\left({\prod }_{j=1}^s{\sigma }_{p_j}\right)$ where for $i=2,3,\dots ,k$, ${\sigma }_{m_{t_i}}$ is as in $\left(1\right)$ and ${\prod }_{j=1}^s{\sigma }_{p_j}$ is as in $\left(1\right)$.

Proof

Suppose $\sigma$ is a complementing permutation of an $r$-pasc $H^r(V_1,V_2,\dots ,V_r)$. Clearly, $\sigma$ is valid. From Theorem 4.5, we have that $\sigma ={\prod }_{i=1}^k{\sigma }_{m_{t_i}}{\prod }_{j=1}^s{\sigma }_{p_j}$ where ${\sigma }_{m_1}$ permutes vertices belonging to $V_1,V_2,\dots ,V_{t_1}$, ${\sigma }_{m_2}$ permutes vertices belonging to $V_{t_1+1},V_{t_1+2},\dots ,V_{t_1+t_2}$ and so on ${\sigma }_{m_k}$ permutes vertices belonging to $V_{t_1+t_2+\cdots +t_{k-1}+1},$

$V_{t_1+t_2+\cdots +t_{k-1}+2},\dots ,V_{t_1+t_2+\cdots +t_{k-1}+t_k}$ and ${\sigma }_{p_j}\left(V_{t+j}\right)=V_{t+j}$ for $j=1,2,\dots ,s$ and $t+s=r$. For convenience we denote ${\sigma }_{m_{t_i}}$ by ${\sigma }_{m_i}$.

Consider the deleted edge, $e=\{x_1,x_2,\dots ,x_{t_1},x_{t_1+1},\dots ,x_{t_1+t_2},\dots ,x_{t_1+t_2+\cdots +t_{k-1}+1},\dots ,x_{t_1+t_2+\cdots +t_k=t},x_{t+1},x_{t+2},\dots ,x_{t+s=r}\}$. We must have the length of the cycle of ${\sigma }^{\prime }$ containing $e$ to be odd.

First we prove that all the special vertices belonging to any particular mixed permutation must belong to the same cycle, that is for each $i=1,2,\dots ,k$, the special vertices $x_{t_1+t_2+\cdots +t_{i-1}+1},x_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,$ $x_{t_1+t_2+\cdots +t_{i-1}+t_i}$ belong to the same cycle of ${\sigma }_{m_i}$.

Suppose not. That is suppose for some $i,i=1,2,\dots ,k$, the special vertices $x_{t_1+t_2+\cdots +t_{i-1}+1},x_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,x_{t_1+t_2+\cdots +t_{i-1}+t_i}$ do not belong to the same cycle of ${\sigma }_{m_i}$. That is at least one vertex among these vertices belongs to a different cycle. Without loss, suppose the vertices $x_{t_1+t_2+\cdots +t_{i-1}+1},x_{t_1+t_2+\cdots +t_{i-1}+2},$ $...,$ $x_{t_1+t_2+\cdots +t_{i-1}+t_i-1}$ belong to a cycle $C_1$ and the vertex $x_{t_1+t_2+\cdots +t_{i-1}+t_i}$ belongs to a cycle $C_2$ of ${\sigma }_{m_i}$ of lengths $L_1$ and $L_2$ respectively. Clearly, $L_1=t_i{q}_1$ and $L_2=t_i{q}_2$ for some positive integers $q_1$ and $q_2$. Note that both $q_1$ and $q_2$ must be odd. Since if either $q_1$ or $q_2$ is even then the cycle of ${\sigma }^{\prime }$ containing the edge $e$ is of even length, a contradiction. Hence both $q_1$ and $q_2$ are odd. Further, since $L_1=t_i{q}_1$ and $L_2=t_i{q}_2$ there are vertices in $C_1$ and $C_2$ other than the special vertices which along with the remaining special vertices will form a valid edge and belong to a distinct cycle of ${\sigma }^{\prime }$ not containing $e$ and at the same time having the same odd length as that of the cycle containing $e$, a contradiction. Hence, for each $i=1,2,\dots ,k$, the special vertices $x_{t_1+t_2+\cdots +t_{i-1}+1},x_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,x_{t_1+t_2+\cdots +t_{i-1}+t_i}$ belong to the same cycle of ${\sigma }_{m_i}$. Moreover, the length of this cycle is $t_i{q}_i$, where $q_i$ is odd.

Let $C_{m_i}$ be the cycle in ${\sigma }_{m_i}$ containing the special vertices $x_{t_1+t_2+\cdots +t_{i-1}+1},x_{t_1+t_2+\cdots +t_{i-1}+2},\dots ,x_{t_1+t_2+\cdots +t_{i-1}+t_i}$ and having length $L_i=t_i{q}_m^i$ respectively for $i=1,2,\dots ,k$, where each $q_m^i$ is odd.

If $C_{m_i}^{\prime }$ is any other cycle in ${\sigma }_{m_i}$ for any $i=1,2,\dots ,k$ having length $q{t}_i$ then $q$ must be even otherwise we will get a cycle of ${\sigma }^{\prime }$ of odd length not containing the edge $e$.

Let $C_{p_j}$ be the cycle in ${\sigma }_{p_j}$ of length $L_j^{\prime }$ containing the special vertex $x_{t+j}\in V_{t+j}$, for each $j,j=1,2,\dots ,s$. Note that each $L_j^{\prime },j=1,2,\dots ,s$ is odd. If not then, the cycle of ${\sigma }^{\prime }$ containing the edge $e$ will be of even length, a contradiction.

If $C_{p_j}^{\prime }$ is any other cycle in ${\sigma }_{p_j}$ for any $j=1,2,\dots ,s$ then it must be of even length.

Observe that for any $1\le i\le k$ and $1\le j\le s$, at most one of $q_m^i$ and $L_j^{\prime }$ can be greater than 1. If not then we will get a cycle of ${\sigma }^{\prime }$ of odd length not containing $e$, a contradiction. Further,

(1) If for some $i,i=1,2,\dots ,k$, $q_m^i>1$ then $t_i$ must be even with ${\sigma }^{q_m^i}\left(x_{t_1+t_2+\cdots t_{i-1}+l}\right)=x_{t_1+t_2+\cdots t_{i-1}+l+q_m^i(mod{t}_i)}$ and $q_m^n=1$ for $n=1,2,\dots ,k;$ $n\ne i$.

(2) If for some $j,j=1,2,\dots ,s$, $L_j^{\prime }>1$ then for any vertex $u\ne x_{t+j}$ in $C_{p_j}$, the cycle of ${\sigma }^{\prime }$ containing the special vertices other than $x_{t+j}$ and $u$ is of odd length which contains the edge $e$ as well. And all the other cycles of ${\sigma }^{\prime }$ are of even length.

The cycle structure of complementing permutations of bipartite ($r=2$) almost self-complementary $2$-hypergraphs (graphs) can be obtained from Theorem 5.1 as stated in the following corollary.

Corollary 5.2

$\sigma$ is a complementing permutation of $2$-pasc (bipartite almost self-complementary graph) $H^2(V_1,V_2)$ if and only if $\sigma$ is valid that is $\sigma ={\sigma }_m$ or $\sigma ={\sigma }_{p_1}{\sigma }_{p_2}$ where ${\sigma }_m$ permutes vertices belonging to $V_1,V_2$ and ${\sigma }_{p_1}$, ${\sigma }_{p_2}$ permute vertices belonging to $V_1$ and $V_2$ respectively. Further, either

$\left(i\right)$ $\sigma ={\sigma }_{p_1}{\sigma }_{p_2}$ where ${\sigma }_{p_1}$ and ${\sigma }_{p_2}$ have exactly one fixed special vertex $x_1$ and $x_2$ respectively, and all the other cycles of ${\sigma }_{p_1}$ and ${\sigma }_{p_2}$ are of even length.

or

$\left(ii\right)$ $\sigma ={\sigma }_{p_1}{\sigma }_{p_2}$ where exactly one of ${\sigma }_{p_1}$ and ${\sigma }_{p_2}$ has exactly one cycle of odd length $L>1$ containing the special vertex and the other has exactly one fixed special vertex. All the other cycles of ${\sigma }_{p_1}$ and ${\sigma }_{p_2}$ are of even length.

or

$\left(iii\right)$ $\sigma ={\sigma }_m$ has a unique cycle of length $4h+2$ containing the special vertices $x_1,x_2$ with ${\sigma }^{2h+1}\left(x_1\right)=x_2,h\ge 0$ and all the other cycles are of length a multiple of $4$.

Acknowledgment

Authors wish to thank Professor N. S. Bhave for fruitful discussions.