Large Sets of Almost Hamilton Cycle and Path Decompositions of Complete Bipartite Graphs

Abstract

In this paper, we give necessary and sufficient conditions for the existence of large sets of almost Hamilton cycle decompositions of $\lambda K_{m,n}$. We also give necessary and sufficient conditions for the existence of large sets of almost Hamilton path decompositions of $\lambda K_{n,n}$.

1 Introduction

For a graph $G$, denote the vertex set and the edge set of $G$ by $V(G)$ and $E(G)$, respectively. A $k$-$cycle$ ($x_1,x_2,\ldots ,x_k$) is a graph with $k$ distinct vertices $x_1,x_2,\ldots ,x_k$ and $k$ edges $\{x_1,x_2\},\ldots ,\{x_{k-1},x_k\},$ $\{x_k,x_1\}$. A $k$-$path$ $[x_1,x_2,\ldots ,x_{k+1}]$ is a graph with $k+1$ distinct vertices $x_1,x_2,\ldots ,x_{k+1}$ and $k$ edges $\{x_1,x_2\},\ldots ,\{x_{k-1},x_k\},\{x_{k},x_{k+1}\}$. A $k$-cycle (resp. $k$-path) decomposition of $G$ is a partition of $E(G)$ into $k$-cycles (resp. $k$-paths). A $|V(G)|$-cycle of $G$ is called a Hamilton cycle. A $(|V(G)|-1)$-cycle of $G$ is called an almost Hamilton cycle. The corresponding cycle decompositions are called Hamilton cycle decomposition and almost Hamilton cycle decomposition, respectively. A $(|V(G)|-1)$-path of $G$ is called a Hamilton path. A $(|V(G)|-2)$-path of $G$ is called an almost Hamilton path. The corresponding path decompositions are called Hamilton path decomposition and almost Hamilton path decomposition, respectively. In a decomposition, the cycles or paths are called blocks of the decomposition. A decomposition is said to be simple if it contains no repeated blocks.

Throughout this paper, let $\lambda K_{v}$ be the complete multigraph of order $v$ in which each edge has multiplicity $\lambda$, and let $\lambda K_{m,n}$ be the complete bipartite multigraph with two partite sets $X=Z_m,Y=\overline{Z}_n$ having $m$ and $n$ vertices, respectively, in which each edge has multiplicity $\lambda$. We regard that the elements in $Z_{m}$ are different from those in $\overline{Z}_{n}$, i.e. $i\ne \overline{j}$ for $i \in Z_{m},j\in Z_{n}$. $\overline{j}$ is not a conjugate of $j$. It is only a symbol distinguished from $j$. Without loss of generality, we suppose $m\ge n$ in $\lambda K_{m,n}$. In this paper, we use the convention that if $\lambda$ is not specified, then $\lambda =1$. It is easy to see that,

• if there exists a Hamilton cycle in $K_{m,n}$ then $m=n$;

• if there exists a Hamilton path in $K_{m,n}$ then $m=n$ or $n+1$;

• if there exists an almost Hamilton cycle in $K_{m,n}$ then $m=n+1$;

• if there exists an almost Hamilton path in $K_{m,n}$ then $m=n$ or $n+1$ or $n+2$.

Before we define large sets of cycle and path decompositions, we give a careful and precise explanation of what is meant by the set of all $k$-cycles (resp. $k$-paths) in a graph $G$. For a non-simple graph $G$, each edge in $G$ has an associated pair of vertices called its endpoints. The set containing the two endpoints of an edge is different from the edge itself, because non-simple graphs may contain distinct edges with the same endpoints. But throughout this paper, two cycles (resp. paths) when one can be obtained from the other by replacing edges with edges having the same endpoints, will be regarded as the same cycle (resp. path). For example, there is only one Hamilton cycle in $2K_3$. The set of all Hamilton cycles in $2K_3$ only contains one Hamilton cycle.

A large set of $k$-cycle decompositions of $\lambda K_{v}$ (resp. $\lambda K_{m,n}$) is a partition of all $k$-cycles in $K_{v}$ (resp. $K_{m,n}$) into $k$-cycle decompositions of $\lambda K_{v}$ (resp. $\lambda K_{m,n}$). A large set of $k$-path decompositions of $\lambda K_{v}$ (resp. $\lambda K_{m,n}$) is a partition of all $k$-paths in $K_{v}$ (resp. $K_{m,n}$) into $k$-path decompositions of $\lambda K_{v}$ (resp. $\lambda K_{m,n}$). It is easy to see that every decomposition is simple in a large set.

There are many results regarding the existence of large sets of $k$-cycle decompositions and $k$-path decompositions. Necessary and sufficient conditions for the existence of large sets of $3$-cycle decompositions of $K_{v}$ have been given by Lu [5] and Teirlinck [6, 7], i.e., large sets of Steiner triple systems. In [1, 9], necessary and sufficient conditions for the existence of large sets of Hamilton cycle and path decompositions of $\lambda K_{v}$ have been given. In Kang and Zhang [3] solved the existence problem for large sets of 2-path decompositions of $\lambda K_{v}$. In Zhang [8] obtained a general result by using the finite fields, that is, if $q\ge k\ge 2$ is an odd prime power, then there exists a large set of $(k-1)$-path decomposition of $(k-1)K_q$. We have proved that there exists a large set of almost Hamilton cycle decomposition of $2 K_{v}$ for any $v\equiv 0,1~(\mathrm{mod ~}4)$ except $v=5$ in Zhao and Kang [10]. In Zhao and Kang [4, 11], we determined the spectra for large sets of Hamilton cycle and path decompositions of $\lambda K_{m,n}$.

In this paper, we give necessary and sufficient conditions for the existence of large sets of almost Hamilton cycle decompositions of $\lambda K_{m,n}$. We also give necessary and sufficient conditions for the existence of large sets of almost Hamilton path decompositions of $\lambda K_{n,n}$. The existence of large sets of almost Hamilton path decompositions of $\lambda K_{m,n}$ for $m=n+1,n+2$ is remained to be an open problem.

2 Small Designs

Denote an almost Hamilton cycle decomposition of $\lambda K_{m,n}$ and a large set of such decomposition by AHC$(m,n,\lambda )$ and LAHC$(m,n,\lambda )$, respectively. Denote an almost Hamilton path decomposition of $\lambda K_{m,n}$ and a large set of such decomposition by AHP$(m,n,\lambda )$ and LAHP$(m,n,\lambda )$, respectively. In the following sections, $(Z_m\bigcup \overline{Z}_{n},\mathcal A)$ denotes an AHC$(m,n,\lambda )$ or an AHP$(m,n,\lambda )$.

An AHC$(n+1,n,\lambda )$ consists of $\frac{\lambda (n+1)n}{2n}=\frac{\lambda (n+1)}{2}$ almost Hamilton cycles. And, if there exists an AHC$(n+1,n,\lambda )$ then $2|\lambda n$ and $2|\lambda (n+1)$. Hence, if there exists an AHC$(n+1,n,\lambda )$ then $2|\lambda$.

Lemma 1

There exists an AHC $(n+1,n,\lambda )$ for $\lambda =2x$, where $n$ and $x$ are any positive integers.

Proof

Define the collection $\mathcal A$ of the following $n+1$ almost Hamilton cycles

$$\begin{aligned} C_{i}=(i,\overline{0},i+1,\overline{1},\ldots ,i+n-1,\overline{n-1}),~0\le i\le n, \end{aligned}$$

where addition is modulo $n+1.$ It is easy to verify that $(Z_{n+1}\bigcup \overline{Z}_{n},\mathcal{A})$ is an AHC$(n+1,n,2)$. Repeating every $C_{i}~x$ times, we obtain an AHC$(n+1,n,\lambda )$. $\square$

An AHP$(n,n,\lambda )$ consists of $\frac{\lambda n^2}{2(n-1)}$ blocks. Hence,

if there exists an AHP$(n,n,\lambda )$, then $n$ is even, $n\ge 2$ and $(n-1)|\lambda$, or $n$ is odd, $n\ge 3$ and $2(n-1)|\lambda$.

Lemma 2

There exists an AHP $(n,n,\lambda )$ for $n=2k,\lambda =(2k-1)x$, where $k$ and $x$ are any positive integers.

Proof

Define the collection $\mathcal A$ of the following $2k^2$ almost Hamilton paths

$$\begin{aligned} P_{s,l}&= \Big [s,\overline{s+2l},s+1,\overline{s+2l+1},\ldots ,s+2m-2,\overline{s+2l+2k-2},s+2k-1\Big ],\\&\qquad 0\le s\le 2k-1,~0\le l\le k-1, \end{aligned}$$

where addition is modulo $2k.$ It is easy to verify that $(Z_{n}\bigcup \overline{Z}_{n},\mathcal{A})$ is an AHP$(n,n,2k-1)$. Repeating every $P_{s,l}~x$ times, we obtain an AHP$(n,n,\lambda )$. $\square$

Lemma 3

There exists an AHP $(n,n,\lambda )$ for $n=2k+1,\lambda =4kx$, where $k$ and $x$ are any positive integers.

Proof

Define the collection $\mathcal A$ of the following $(2k+1)^2$ almost Hamilton paths

$$\begin{aligned} P_{s,l}&= \Big [s,\overline{l},s+1,\overline{l+1},\ldots ,s+2m-1,\overline{l+2k-1},s+2k\Big ],\\&\qquad 0\le s\le 2k,~0\le l\le 2k, \end{aligned}$$

where addition is modulo $2k+1.$ It is easy to verify that $(Z_{n}\bigcup \overline{Z}_{n},\mathcal{A})$ is an AHP$(n,n,4k)$. Repeating every $P_{s,l}~x$ times, we obtain an AHP$(n,n,\lambda )$. $\square$

In Lemmas 1, 2, and 3 when $x>1$, all decompositions are not simple decompositions (i.e., containing repeated blocks). In the following sections, we will construct simple decompositions when $x>1$.

3 LAHC$(n+1,n,\lambda )$

Let $Sym(S)$ be the symmetric group on a given set $S$. For a subgroup $T$ of $Sym(S)$, any set of representatives of the right cosets for $T$ in $Sym(S)$ is denoted by $Sym_T(S)$. For any $s\in S$ and two permutations $\xi _1,\xi _2\in Sym(S)$, define $\xi _1\xi _2(s)=\xi _2\left( \xi _1(s)\right)$. In this section, denote $X=Z_{n+1}$ and $Y=\overline{Z}_n$.

Let $C=(x_0,\overline{x}_0,x_1,\overline{x}_1,\ldots ,x_{n-1},\overline{x}_{n-1})$ be an almost Hamilton cycle, where $x_i\in X,~\overline{x}_i\in Y$ for $0\le i\le n-1$. For permutations $\xi \in Sym(X)$ and $\eta \in Sym(Y)$, denote $\xi C=(\xi (x_0),\overline{x}_0,\xi (x_1),\overline{x}_1,\ldots ,\xi (x_{n-1}),\overline{x}_{n-1})$ and $\eta C=\left( x_0,\eta (\overline{x}_0),x_1,\eta (\overline{x}_1),\ldots ,x_{2t},\eta (\overline{x}_{2t})\right)$, where $\xi (x_i),\eta (\overline{x}_j)$ represent the images of the element $x_i,\overline{x}_j$ under the actions of permutations $\xi$ and $\eta$, respectively. We call the unique element in $(X\bigcup Y)\backslash \{x_0,x_1,\ldots ,x_{n-1},\overline{x}_0,\overline{x}_1,\ldots ,\overline{x}_{n-1}\}$ to be the defect of $C$ over the set $X\bigcup Y$. This defect is denoted by $d(C)$. Actually, $(X\bigcup Y)\backslash \{x_0,x_1,\ldots ,x_{n-1},\overline{x}_0,\overline{x}_1,\ldots ,\overline{x}_{n-1}\}=X\backslash \{x_0,x_1,\ldots ,x_{n-1}\}$. Obviously, $\xi (d(C))=d(\xi C)$ for any $\xi \in Sym(X)$.

Take $\eta =\big (\overline{1},\overline{n-1}\big )\big (\overline{2},\overline{n-2}\big )\ldots \Big (\overline{\lfloor \frac{n-1}{2}\rfloor },\overline{n-\lfloor \frac{n-1}{2}\rfloor }\Big )\in Sym(Y)$, which generates a subgroup $G=\langle \eta \rangle$ of $Sym(Y')$ with order two, where $Y'=Y\backslash \{\overline{0}\}$. Then, $|Sym_G(Y')|=\frac{(n-1)!}{2}$. Let $Sym_G(Y')=\{\eta _1,\eta _2,\ldots ,\eta _{(n-1)!/2}\}$. For an almost Hamilton cycle, the shifts of rotation and reflection produce the same almost Hamilton cycle. In what follows, Shift-equivalence means the fact that two almost Hamilton cycles when one can be obtained from the other by rotating or reflecting, will be regarded as the same almost Hamilton cycle. Below, by the shift-equivalence of almost Hamilton cycles, each almost Hamilton cycle in $K_{n+1,n}$ will be denoted by a fixed form as follows.

Under the action of $Sym(X)$, all almost Hamilton cycles in $K_{n+1,n}$ can be separated into the following orbits:

$$\begin{aligned}&\mathcal{O}_{i}\!=\!\Big \{\big (\xi (0),\eta _i(\overline{0}),\xi (1),\eta _i(\overline{1}),\ldots ,\xi (n-1),\eta _i(\overline{n-1})\big ):\xi \in Sym(X)\Big \},\\&\quad ~\eta _i\in Sym_G(Y'). \end{aligned}$$

It is easy to see that $|\mathcal{O}_{i}|=(n+1)!$ for any $\eta _i\in Sym_G(Y')$. And $|Sym_G(Y')||\mathcal{O}_{i}|=\frac{(n-1)!(n+1)!}{2}$ is just the total number of distinct almost Hamilton cycles in $K_{n+1,n}$.

Let $\mathcal A$ be a collection of almost Hamilton cycles in $K_{n+1,n}$. A subgroup $H$ of $Sym(X)$ (resp. $Sym(Y)$) is called a complete automorphism group over $X$ (resp. $Y$) of $\mathcal A$ if the following conditions are satisfied:

• 1. $\alpha C\in \mathcal A$ for any $\alpha \in H$ and $C \in \mathcal{A}$;

• 2. $\forall ~ C,C^{'}\in \mathcal A$, if there exists a permutation $\beta \in Sym(X)$ (resp. $Sym(Y)$) such that $\beta C=C^{'}$, then $\beta \in H$.

When $\mathcal A$ is a collection of almost Hamilton paths in $K_{m,n}$, there is a similar definition of complete automorphism group.

In the following discussions, $\mathcal A$ consists of all almost Hamilton cycles of some AHC$(n+1,n,\lambda )$. We now give a very useful lemma in this paper. The idea behind this construction is to make use of symmetric group, in a similar way as was done in Kang [2].

Lemma 4

• (1) If $(X\bigcup Y,\mathcal A)$ is an AHC $(n+1,n,\lambda )$ then so is $(X\bigcup Y,\xi \mathcal{A})$ $\big ($resp. $(X\bigcup Y,\eta \mathcal{A})\big )$, where $\xi \in Sym(X),~\xi \mathcal{A}=\{\xi C:C\in \mathcal A\}$ $\big ($resp. $\eta \in Sym(Y),~\eta \mathcal{A}=\{\eta C:C\in \mathcal A\}\big );$

• (2) If the system $\mathcal A$ is simple and it has a complete automorphism group $H$ over $X$ $($resp. $Y)$, then all almost Hamilton cycles in $\big \{\xi \mathcal{A}:\xi \in Sym_H(X)\big \}$ $\big ($resp. $\{\eta \mathcal{A}:\eta \in Sym_H(Y)\}\big )$ are pairwise distinct, where $Sym_H(X)~\big ($resp. $Sym_H(Y)\big )$ is any set of right coset representatives for $H$ in $Sym(X)$ $\big ($resp. $Sym(Y)\big )$.

Proof

• (1) The permutation $\xi$ on $X$ induces a permutation on the set $(X\times X)\backslash \triangle _x$, where $\triangle _x=\big \{(x,x):x\in X\big \}.$ Hence, the system $(X\bigcup Y,\xi \mathcal{A})$ is also an AHC$(n+1,n,\lambda )$ by the definition. For $\eta \in Sym(Y)$, the proof is similar.

• (2) Suppose that there exist $C,C^{'}\in \mathcal A$ and $\xi _1\not =\xi _2\in Sym_H(X)$ such that $\xi _1C=\xi _2C^{'}$. Then $(\xi _1\xi _2^{-1})C=C^{'}$ and $\xi _1\xi _2^{-1}\in H$ by the definition of complete automorphism group $H$ over $X$. This implies $H\xi _1=H\xi _2,$ i.e., $\xi _1$ and $\xi _2$ belong to the same coset, which is a contradiction. For the other case, the proof is similar.$\square$

An AHC$(n+1,n,\lambda )$ contains $\lambda (n+1)/2$ almost Hamilton cycles. The total number of distinct almost Hamilton cycles in $K_{n+1,n}$ is $\frac{(n+1)!(n-1)!}{2}$. Hence, an LAHC$(n+1,n,\lambda )$ contains $\frac{n!(n-1)!}{\lambda }$ pairwise disjoint AHC$(n+1,n,\lambda )$s. Clearly, there exists an LAHC$(n+1,n,\lambda )$ only if

$$\begin{aligned} \lambda |n!(n-1)! \, \hbox { and }\, 2|\lambda . \end{aligned}$$

And therefore, the existence spectrum for LAHC$(n+1,n,\lambda )$ only depends on one case: any $n\ge 2$ for $\lambda =2$.

Lemma 5

There exists an LAHC $(n+1,n,2)$ for any positive integer $n\ge 2$.

Proof

Take the AHC$(n+1,n,2)=(X\bigcup Y,\mathcal{A}),$ where $\mathcal{A}=\{C_0,C_1,\ldots ,C_{n}\}$ constructed in Lemma 1 as the base small set. Let $\xi =(0,1,\ldots ,n-1)\in Sym(X)$, which generates a subgroup $H=\langle \xi \rangle$ of $Sym(X)$ with order $n$. Clearly, $C_{i+1}=\xi C_{i}$ for $i\in Z_{n+1}$. Furthermore, $C_{j}=\xi ^{j-i}C_{i}$ for $i,j\in Z_{n+1}$. Now, we have shown that $H$ is a complete automorphism group over $X$ of $\mathcal A$. Let $Sym_H(X)=\{\xi _1,\xi _2,\ldots ,\xi _{n!}\}$, where $\xi _1=e$ (identity permutation). From the beginning of this section, we know that $Sym_G(Y')=\{\eta _1,\eta _2,\ldots ,\eta _{(n-1)!/2}\}$.

Define

$$\begin{aligned} \Omega _{i,j}=\{\xi _i\eta _jC_0,\xi _i\eta _jC_1,\ldots ,\xi _i\eta _jC_{n}\},~1\le i\le n!,~1\le j\le (n-1)!/2, \end{aligned}$$

where for an almost Hamilton cycle $C=(x_0,\overline{x}_0,x_1,\overline{x}_1,\ldots ,x_{n-1},\overline{x}_{n-1})$,

$$\begin{aligned} \xi _i\eta _jC=\big (\xi _i(x_0),\eta _j(\overline{x}_0),\xi (x_1),\eta _j(\overline{x}_1),\ldots ,\xi (x_{n-1}),\eta _j(\overline{x}_{n-1})\big ). \end{aligned}$$

Each $\Omega _{i,j}$ is an AHC$(n+1,n,2)$ by Lemma 4 (1). Similarly, we can prove that $H$ is a complete automorphism group over $X$ of $\Omega _{1,j}$ for any $j,~1\le j\le (n-1)!/2$. We also have the following two facts.

• (1) For a given $\eta _j$, $1\le j \le (n-1)!/2$, all almost Hamilton cycles in $\Omega _{i,j}$ fall into orbit $\mathcal{O}_{j}$, where $1\le i \le n!$;

• (2) For a given $\eta _j$, $1\le j \le (n-1)!/2$, all almost Hamilton cycles in $\{\Omega _{i,j}:~1\le i\le n!\}$ are pairwise distinct by Lemma 4 (2).

Consider the enumeration $|Sym_H(X)|\cdot |Sym_G(Y')|=|\bigcup \limits _{i,j}\Omega _{i,j}|=\frac{n!(n-1)!}{2}$, which is just the desired number of disjoint AHC$(n+1,n,2)$s in an LAHC$(n+1,n,2)$. Therefore, by facts $(1)$ and $(2)$, an LAHC$(n+1,n,2)$ is constructed. $\square$

Combining Lemma 5 and the necessary conditions for the existence of LAHC$(n+1,n,\lambda )$, we obtain the following conclusion.

Theorem 1

There exists an LAHC $(m,n,\lambda )$ if and only if $m=n+1,~\lambda |n!(n-1)!$ and $2|\lambda$.

Proof

By the necessary conditions at the beginning of this section, we need only to prove the sufficiency. By Lemma 5, there exists an LAHC$(n+1,n,2)=\big \{(X\bigcup Y,\mathcal{A}_i):~1\le i\le \frac{n!(n-1)!}{2}\big \}$. For $\lambda |n!(n-1)!$ and $2|\lambda$, define

$$\begin{aligned} \mathcal{B}_j=\bigcup \limits _{i=\frac{j\lambda }{2}+1}^{(j+1)\frac{\lambda }{2}}\mathcal{A}_i,~0\le j\le \frac{n!(n-1)!}{\lambda }-1, \end{aligned}$$

then $\Big \{(X\bigcup Y,\mathcal{B}_j):~0\le j\le \frac{n!(n-1)!}{\lambda }-1\Big \}$ is an LAHC$(n+1,n,\lambda )$. $\square$

Corollary 1

There exists a simple AHC $(n+1,n,\lambda )$ if and only if $2|\lambda , 2\le \lambda \le {n!(n-1)!}$ and $n\ge 2$.

4 LAHP$(n,n,\lambda )$

In this section, denote $X=Z_{n}$ and $Y=\overline{Z}_n$. For permutations $\xi \in Sym(X)$, $\eta \in Sym(Y)$ and an almost Hamilton path $C=\Big [x_0,\overline{x}_0,x_1,\overline{x}_1,\ldots ,$ $x_{n-2},\overline{x}_{n-2},$ $x_{n-1}\Big ]$, where $x_i\in X,~\overline{x}_j\in Y$ for $0\le i\le n-1,0\le j\le n-2$, the definitions of $\xi C$ and $\eta C$ are similar to that of Sect. 3. Denote

$$\begin{aligned} \overline{C}=\Big [\overline{x}_0,{x}_0,\overline{x}_1,{x}_1,\ldots ,\overline{x}_{n-2},{x}_{n-2},\overline{x}_{n-1}\Big ]. \end{aligned}$$

Take $\xi =(0,n-1)(1,n-2)\cdots \Big (\lfloor \frac{n}{2} \rfloor -1,n-\lfloor \frac{n}{2} \rfloor \Big )\in Sym(X)$, which generates a subgroup $G=\langle \xi \rangle$ of $Sym(X)$ with order two. Then, $|Sym_G(X)|={n!}/{2}$. Let $Sym_G(X)=\big \{\xi _1,\xi _2,\ldots ,\xi _{n!/2}\big \}$. So, $Sym(X)=\bigcup \limits _{i=1}^{n!/2}G_{i}$, where each $G_i$ is a right coset.

Lemma 6

All right cosets of $G$ in $Sym(X)$ can be separated into the following $(n-1)!/2$ right coset families $R_i=\{G_{i,0},G_{i,1},\ldots ,G_{i,n-1}\}$, $1\le i\le (n-1)!/2$, such that $G_{i,j+1}=G_{i,j}\beta _i,$ where $j\in Z_n,~\beta _i=\big (\alpha _i(0),\alpha _i(1),\ldots ,\alpha _i(n-1)\big )$ and $\alpha _i$ is the representative of $G_{i,0}$.

Proof

Any right coset $G_{i}$ may be denoted by $G_{i}=G\alpha$ for some $\alpha \in Sym(X)$. In order to prove this Lemma, it suffices to show the following two facts.

• 1. $G\alpha \beta ^i\ne G\alpha \beta ^j$ for $0\le i\ne j\le n-1$, where $\beta =\big (\alpha (0),\alpha (1),\ldots ,\alpha (n-1)\big )$. In fact, suppose there exist $0\le i\ne j\le n-1$ such that $G\alpha \beta ^i=G\alpha \beta ^j$, then $\alpha \beta ^{i-j}\alpha ^{-1}\in G,$ i.e., $\alpha \beta ^{i-j}\alpha ^{-1}=e$ or $\xi$, where $e$ is the identical permutation and $\xi (i)=n-1-i$. However, it is impossible that $\alpha \beta ^{i-j}\alpha ^{-1}=e$, since $\beta ^{i-j}\ne e$. In other hand, if $\alpha \beta ^{i-j}\alpha ^{-1}=\xi ,$ i.e., $\alpha \beta ^{i}=\xi \alpha \beta ^{j}$, then $\alpha (i)=\alpha \beta ^{i}(0)=\xi \alpha \beta ^{j}(0)=\alpha (n-1+j)$. So, $i-j=n-1$ and $\alpha \beta ^{n-1}\alpha ^{-1}=\xi .$ Furthermore, $e=\xi ^2=(\alpha \beta ^{n-1}\alpha ^{-1})^2=\alpha \beta ^{2(n-1)}\alpha ^{-1},$ i.e., $e=\beta ^{2(n-1)}=\beta ^{n-2}$, a contradiction.

• 2. $G\gamma \delta ^i\ne G\alpha \beta ^j$ for $\delta =\big (\gamma (0),\gamma (1),\ldots ,\gamma (n-1)\big ), \gamma \not \in \{\alpha \beta ^i,\xi \alpha \beta ^i\}$ and $0\le i,j\le n-1$.

In fact, suppose there exist $0\le i,j\le n-1$ such that $G\gamma \delta ^i=G\alpha \beta ^j$, then $\gamma \delta ^{i}\beta ^{-j}\alpha ^{-1}\in G,$ i.e., $\gamma \delta ^{i}\beta ^{-j}\alpha ^{-1}=e$ or $\xi$. There are the following two cases.

• (1) Suppose $\gamma \delta ^{i}\beta ^{-j}\alpha ^{-1}=e$, i.e., $\gamma \delta ^{i}=\alpha \beta ^j$, then $\gamma \delta ^{i}(k)=\gamma (i+k),~\alpha \beta ^j(k)=\alpha (j+k)=\alpha \beta ^{j-i}(i+k)$ for $0\le k\le n-1$. So, $\gamma =\alpha \beta ^{j-i}$, a contradiction to the choice of $\gamma$.

• (2) Suppose $\gamma \delta ^{i}\beta ^{-j}\alpha ^{-1}=\xi$, i.e., $\gamma \delta ^{i}=\xi \alpha \beta ^j$, then for $0\le k\le n-1$, $\gamma \delta ^{i}(k)=\gamma (i+k),~\xi \alpha \beta ^j(k)=\alpha \beta ^j(n-1-k)=\alpha (n-1-k+j)=\xi \alpha \beta ^{i+j}(i+k)$.

So, $\gamma =\xi \alpha \beta ^{i+j}$, a contradiction to the choice of $\gamma$. $\square$

Corollary 2

There exists a right coset representative set $Sym_G(X)$, which can be separated into the following $(n-1)!/2$ right coset representative families $\pi _i=\big \{\xi _{i,0},\xi _{i,1},\ldots ,\xi _{i,n-1}\big \},~1\le i\le (n-1)!/2$, such that $\xi _{i,j+1}=\xi _{i,j}\beta _i,$ where $j\in Z_n,~\beta _i=\big (\xi _{i,0}(0),\xi _{i,0}(1),\ldots ,\xi _{i,0}(n-1)\big )$ and $\xi _{1,0}=e$.

In what follows, Shift-equivalence means the fact that two almost Hamilton paths when one can be obtained from the other by reflecting, will be regarded as the same almost Hamilton path. By the shift-equivalence of almost Hamilton paths, each Hamilton path in $K_{n,n}$ will be denoted by a fixed form as follows. Under the action of $Sym(Y)$, half of the almost Hamilton paths in $K_{n,n}$ can be separated into the following orbit families:

$$\begin{aligned} \mathcal{F}_{i}=\{\mathcal{O}_{i,j}:~0\le j\le n-1\},1\le i\le (n-1)!/2, \end{aligned}$$

where $\mathcal{O}_{i,j}=\Big \{\big [ \xi _{i,j}(0),\eta (\overline{0}),\xi _{i,j}(1),\eta (\overline{1}),\ldots ,\xi _{i,j}(n-2),\eta (\overline{n-2}),\xi _{i,j}(n-1)\big ]:~\eta \in Sym(Y)\Big \}.$ Let $\overline{\mathcal{F}}_{i}=\{\overline{\mathcal{O}}_{i,j}:~0\le j\le n-1\}$, $1\le i\le (n-1)!/2$, where $\overline{\mathcal{O}}_{i,j}=\{ \overline{C}:~C\in \mathcal{O}_{i,j}\}$. It is easy to see that $|{\mathcal{F}}_{i}|=|{\overline{\mathcal{F}}}_{i}|=n$ and $|\mathcal{O}_{{i,j}}|=|\overline{\mathcal{O}}_{{i,j}}|=n!$ for $1\le i\le (n-1)!/2,~0\le j\le n-1$. The number of right coset representative families is $(n-1)!/2$. Then, $\frac{(n-1)!}{2}\cdot |{\mathcal{F}}_{i}|\cdot |\mathcal{O}_{{i,j}}|+\frac{(n-1)!}{2}\cdot |{\overline{\mathcal{F}}}_{i}|\cdot |\overline{\mathcal{O}}_{{i,j}}|=(n!)^2$ is just the total number of distinct almost Hamilton paths in $K_{n,n}$.

In the following discussion, $\mathcal A$ consists of all almost Hamilton paths of some AHP$(n,n,\lambda )$. We consider the complete automorphism group over $Y$ of $\mathcal A$ defined in section 3. By similar proof as in Lemma 4, we immediately give another very useful lemma.

Lemma 7

• (1) If $(X\bigcup Y,\mathcal A)$ is an AHP $(n,n,\lambda )$ then so is $(X\bigcup Y,\eta \mathcal{A})$ $\big ($resp. $(X\bigcup Y,\xi \mathcal{A})\big )$, where $\eta \in Sym(Y)$ $($resp. $\xi \in Sym(X)$;

• (2) If the system $\mathcal A$ is simple and it has a complete automorphism group $H$ over $Y$, then all almost Hamilton paths in $\big \{\eta \mathcal{A}:\eta \in Sym_H(Y)\big \}$ are pairwise distinct, where $Sym_H(Y)$ is any set of right coset representatives for $H$ in $Sym(Y)$.

An AHP$(n,n,\lambda )$ contains $\frac{\lambda n^2}{2(n-1)}$ almost Hamilton paths. The total number of distinct almost Hamilton cycles in $K_{n,n}$ is $(n!)^{2}$. Hence, an LAHP$(n,n,\lambda )$ contains ${2(n-1)\left( (n-1)!\right) ^2}/{\lambda }$ pairwise disjoint AHP$(n,n,\lambda )$s. Clearly, there exists an LAHP$(n,n,\lambda )$ only if

$$\begin{aligned} \lambda |2(n-1)\left( (n-1)!\right) ^2 \, \hbox {and}\, \left\{ \begin{array}{ll} \mathrm{even}~n\ge 2~\, \mathrm{and}\, ~(n-1)|\lambda ;\\ \mathrm{odd}~~n\ge 3~\, \mathrm{and}\,~2(n-1)|\lambda . \end{array} \right. \end{aligned}$$

Therefore, the completion of the existence spectrum for LAHP$(n,n,\lambda )$ only depends on two cases: even $n\ge 2$ for $\lambda =n-1$ and odd $n\ge 3$ for $\lambda =2(n-1)$.

Lemma 8

There exists an LAHP $(n,n,\lambda )$ for $n=2k,\lambda =2k-1$, where $k$ is any positive integer.

Proof

For $n=2k,\lambda =2k-1$, take the AHP$(n,n,\lambda )=(Z_{2k}\bigcup \overline{Z}_{2k},\mathcal{A}),$ where $\mathcal{A}=\{P_{s,l}:s\in Z_{2k},l\in Z_k\}$ constructed in Lemma 2 as the base small set. Let $\eta =(\overline{0},\overline{2},\ldots ,\overline{2k-2})(\overline{1},\overline{3},\ldots ,\overline{2k-1})\in Sym(\overline{Z}_{2k})$ , which generates a subgroup $H=\langle \eta \rangle$ of $Sym(\overline{Z}_{2k})$ with order $k$. Clearly, $P_{s,l}=\eta ^{l-l'}P_{s,l'}$ for $s\in Z_{2k},l,l'\in Z_k$. Now, we have shown that $H$ is a complete automorphism group of $\mathcal A$ over $\overline{Z}_{2k}$. Let $Sym_H(\overline{Z}_{2k})=\big \{\eta _1,\eta _2,\ldots ,\eta _{2(2k-1)!}\big \}$, where $\eta _1$ is the identity. From Corollary 2, we know that $Sym_G(Z_{2k})=\bigcup \limits _{i=1}^{(2k-1)!/2}\{\xi _{i,0},\xi _{i,1},\ldots ,\xi _{i,2k-1}\}$. Define $\Omega _{i,j}=\{\xi _{i,0}\eta _jP_{s,l}:0\le s\le 2k-1,0\le l\le k-1\},~1\le i\le \frac{(2k-1)!}{2},~1\le j\le 2(2k-1)!.$ Each $\Omega _{i,j}$ is an AHP$(n,n,\lambda )$ by Lemma 7 (1). Similarly, we can prove that $H$ is a complete automorphism group of $\Omega _{i,1}$ over $\overline{Z}_{2k}$ for $1\le i\le (2k-1)!/2$. We have the facts:

* For given $i$, all almost Hamilton paths in $\big \{\Omega _{i,j}:1\le j \le 2(2k-1)!\big \}$ fall into orbit family ${\mathcal{F}}_{i}$;

In fact, in $\Omega _{i,j}$, for given $l,l'\in Z_k,$ there exists a permutation $\theta \in Sym(\overline{Z}_{2k})$, such that $\xi _{i,0}\eta _jP_{s+1,l'}=\beta _i(\xi _{i,0}\eta _j\theta P_{s,l})=\xi _{i,0}\beta _i\eta _j\theta P_{s,l}=\xi _{i,1}\eta _j\theta P_{s,l}$ for $s\in Z_{2k}$. Furthermore, for given $s_1,s_2\in Z_{2k},$ there exists a permutation $\theta '\in Sym(\overline{Z}_{2k})$, such that

$$\begin{aligned} \xi _{i,0}\eta _jP_{s_2,l'}=\beta ^{s_2-s_1}_i(\xi _{i,0}\eta _j\theta ' P_{s_1,l})=\xi _{i,0}\beta ^{s_2-s_1}_i\eta _j\theta ' P_{s,l}=\xi _{i,s_2-s_1}\eta _j\theta ' P_{s_1,l}. \end{aligned}$$

That is to say, the $k$ Hamilton paths $\xi _{i,0}\eta _jP_{s,0},\xi _{i,0}\eta _jP_{s,1},\ldots ,\xi _{i,0}\eta _jP_{s,k-1}$ belong to the orbit $\mathcal{O}_{i,s},~0\le s\le 2k-1$, which is a member of orbit family ${\mathcal{F}}_{i}$.

* For given $i$, all almost Hamilton paths in $\big \{\Omega _{i,j}:1\le j \le 2(2k-1)!\big \}$ are pairwise distinct by Lemma 7 (2).

Let $\overline{\Omega }_{i,j}=\{\overline{P}:~P\in \Omega _{i,j}\}$. Obviously, for $1\le i \le (2k-1)!/2$, all almost Hamilton paths in $\big \{\overline{\Omega }_{i,j}:~1\le j \le 2(2k-1)!\big \}$ fall into orbit family ${\overline{\mathcal{F}}}_{i}$ and all almost Hamilton paths in $\big \{\overline{\Omega }_{i,j}:~1\le j \le 2(2k-1)!\big \}$ are pairwise distinct.

Consider the enumeration $\frac{2|Sym_G(Z_{2k})|}{2k}\cdot |Sym_H(\overline{Z}_{2k})|=|\bigcup \limits _{i,j}\Omega _{i,j}|+|\bigcup \limits _{i,j}\overline{\Omega }_{i,j}|=2((2k-1)!)^{2}$, which is just the desired number of disjoint AHP$(n,n,\lambda )$s in an LAHP$(n,n,\lambda )$. This completes the proof. $\square$

Lemma 9

There exists an LAHP $(n,n,\lambda )$ for $n=2k+1,\lambda =4k$, where $k$ is any positive integer.

Proof

For $n=2k+1,\lambda =4k$, take the AHP$(n,n,\lambda )=(Z_{2k+1}\bigcup \overline{Z}_{2k+1},\mathcal{A}),$ where $\mathcal{A}=\{P_{s,l}:0\le s,l\le 2m\}$ constructed in Lemma 3 as the base small set. Let $\eta =(\overline{0},\overline{1},\ldots ,\overline{2k})\in Sym(Y)$ , which generates a subgroup $H=\langle \eta \rangle$ of $Sym(Y)$ with order $2k+1$. Clearly, $P_{s,l}=\eta ^{l-l'}P_{s,l'}$ for $s,l,l'\in Z_{2k+1}$. Now, we have shown that $H$ is a complete automorphism group over $Y$ of $\mathcal A$. Let $Sym_H(Y)=\{\eta _1,\eta _2,\ldots ,\eta _{(2k)!}\}$, where $\eta _1=e$. From Corollary 2, we know that $Sym_G(X)=\bigcup \limits _{i=1}^{(2k)!/2}\pi _i$, where $\pi _i=\{\xi _{i,0},\xi _{i,1},\ldots ,\xi _{i,2k}\}$. Define

$$\begin{aligned} \Omega _{i,j}=\{\xi _{i,0}\eta _jP_{s,l}:~0\le s,l\le 2m\},~1\le i\le (2k)!/2,~1\le j\le (2k)!. \end{aligned}$$

Each $\Omega _{i,j}$ is an AHP$(n,n,\lambda )$ by Lemma 7 (1). Similarly, we can prove that $H$ is a complete automorphism group over $Y$ of $\Omega _{i,1}$ for any $i,~1\le i\le (2k)!/2$. We also have the following two facts.

* For a given $\xi _{i,0}$, $1\le i \le (2k)!/2$, all almost Hamilton paths in $\big \{\Omega _{i,j}:~1\le j \le (2k)!\big \}$ fall into orbit family ${\mathcal{F}}_{i}$;

In fact, in $\Omega _{i,j}$, for given $l,l'\in Z_{2k+1},$ there exists a permutation $\theta \in Sym(Y)$, such that $\xi _{i,0}\eta _jP_{s+1,l'}=\beta _i(\xi _{i,0}\eta _j\theta P_{s,l})=\xi _{i,0}\beta _i\eta _j\theta P_{s,l}=\xi _{i,1}\eta _j\theta P_{s,l}$ for $s\in Z_{2k+1}$. Furthermore, for given $s_1,s_2\in Z_{2k+1},$ there exists a permutation $\theta '\in Sym(Y)$, such that

$$\begin{aligned} \xi _{i,0}\eta _jP_{s_2,l'}=\beta ^{s_2-s_1}_i(\xi _{i,0}\eta _j\theta ' P_{s_1,l})=\xi _{i,0}\beta ^{s_2-s_1}_i\eta _j\theta ' P_{s,l}=\xi _{i,s_2-s_1}\eta _j\theta ' P_{s_1,l}. \end{aligned}$$

That is to say, the $2k+1$ Hamilton paths $\xi _{i,0}\eta _jP_{s,0},\xi _{i,0}\eta _jP_{s,1},\ldots ,\xi _{i,0}\eta _jP_{s,2k}$ belong to orbit $\mathcal{O}_{i,s},~0\le s\le 2k-1$, which is a member of orbit family ${\mathcal{F}}_{i}$.

* For a given $\xi _{i,0}$, $1\le i \le (2k)!/2$, all almost Hamilton paths in $\big \{\Omega _{i,j}:~1\le j \le (2k)!\big \}$ are pairwise distinct by Lemma 7 (2).

Let $\overline{\Omega }_{i,j}=\{\overline{P}:~P\in \Omega _{i,j}\}$. Obviously, for $1\le i \le (2k)!/2$, all almost Hamilton paths in $\big \{\overline{\Omega }_{i,j}:~1\le j \le (2k)!\big \}$ fall into orbit family ${\overline{\mathcal{F}}}_{i}$ and all almost Hamilton paths in $\big \{\overline{\Omega }_{i,j}:~1\le j \le (2k)!\big \}$ are pairwise distinct.

Consider the enumeration $2\frac{|Sym_G(X)|}{2k+1}\cdot |Sym_H(Y)|=|\bigcup \limits _{i,j}\Omega _{i,j}|+|\bigcup \limits _{i,j}\overline{\Omega }_{i,j}|=((2k)!)^{2}$, which is just the desired number of disjoint AHP$(n,n,\lambda )$s in an LAHP$(n,n,\lambda )$. This completes the proof. $\square$

Combining Lemmas 8, 9 and the necessary conditions for the existence of LAHP$(n,n,\lambda )$, we obtain the following conclusion. The proof is similar to that of Theorem 1, which is omitted.

Theorem 2

There exists an LAHP $(n,n,\lambda )$ if and only if

$$\begin{aligned} \lambda |2(n-1)((n-1)!)^2 \, \hbox \mathrm{and}\, \left\{ \begin{array}{ll} \mathrm{even}~n\ge 2~\mathrm{and}~(n-1)|\lambda ;\\ \mathrm{odd}~~n\ge 3~\mathrm{and}~2(n-1)|\lambda . \end{array} \right. \end{aligned}$$

Corollary 3

There exist a simple AHP $(n,n,\lambda )$ if and only if

$$\begin{aligned} \left\{ \begin{array}{ll} \mathrm{even}~n\ge 2,~(n-1)|\lambda ~\mathrm{and}~n-1\le \lambda \le 2(n-1)\left( (n-1)!\right) ^{2};\\ \mathrm{odd}~~n\ge 3,~2(n-1)|\lambda ~\mathrm{and}~2(n-1)\le \lambda \le 2(n-1)\left( (n-1)!\right) ^{2}. \end{array} \right. \end{aligned}$$

The remaining problem is to research the existence of LAHP$(m,n,\lambda )$ for $m=n+1$, or $n+2$. Although we have worked hard on it, we could not find effective constructions for these two subcases. It is our future work.