5-Regular Subgraphs in Hypercubes

Borse, Y. M.; Shaikh, S. R.; Saraf, J. B.

doi:10.61091/ars159-14

Abstract

1. Introduction
2. Preliminaries
3. Proof of Theorem 3
4. Construction of 5-regular Subgraphs of Qn
5. Connectivity
6. Bipancyclicity
Acknowledgment
Conflict of Interest

References

Ars Combinatoria

Volume 159
Pages: 165-178

Research article

5-Regular Subgraphs in Hypercubes

^¹, ^¹, ^¹

¹Department of Mathematics, Savitribai Phule Pune University, Ganeshkhind, Pune 411007, India

Received: 07/10/2019
Accepted: 06/04/2020
Published: 30/06/2024

Copyright Link
License

Abstract

One of the fundamental properties of the hypercube $Q_{n}$ is that it is bipancyclic as $Q_{n}$ has a cycle of length $l$ for every even integer $l$ with $4 \leq l \leq 2^{n}$ . We consider the following problem of generalizing this property: For a given integer $k$ with $3 \leq k \leq n$ , determine all integers $l$ for which there exists an $l$ -vertex, $k$ -regular subgraph of $Q_{n}$ that is both $k$ -connected and bipancyclic. The solution to this problem is known for $k = 3$ and $k = 4$ . In this paper, we solve the problem for $k = 5$ . We prove that $Q_{n}$ contains a $5$ -regular subgraph on $l$ vertices that is both $5$ -connected and bipancyclic if and only if $l \in {32, 48}$ or $l$ is an even integer satisfying $52 \leq l \leq 2^{n}$ . For general $k$ , we establish that every $k$ -regular subgraph of $Q_{n}$ has $2^{k}, 2^{k} + 2^{k - 1}$ or at least $2^{k} + 2^{k - 1} + 2^{k - 3}$ vertices.

Keywords: Hypercube,

k

-connected, Regular, Bipancyclic, Subgraphs

1. Introduction

A graph $G = (V, E)$ on $n$ vertices is an $n$ -vertex graph. A $2 n$ -vertex graph is bipancyclic if it has a cycle of length $l$ for all even integers $l$ satisfying $4 \leq l \leq 2 n .$ The Cartesian product of two graphs $G$ and $H$ is the graph $G H$ with vertex set $V (G) \times V (H)$ in which two vertices $(x, y)$ and $(u, v)$ are adjacent if and only if either $x = u$ and $y$ is adjacent to $v$ in $H,$ or $y = v$ and $x$ is adjacent to $u$ in $G .$ Throughout the paper $n$ denote a positive integer.

The $n$ -dimensional hypercube $Q_{n}$ is the Cartesian product of $n$ copies of the complete graph $K_{2} .$ It is an $n$ -regular, $n$ -connected, bipartite, and bipancyclic graph on $2^{n}$ vertices with diameter $n .$ Because of such rich properties, hypercubes are one of the most widely used interconnection network topologies [1]. The connectivity of a network is an important parameter to evaluate the reliability and fault tolerance of a network [2]. Bipancyclicity is a fundamental property of the hypercube networks as it allows the embedding of cycles of various lengths effectively into hypercubes. Cycle networks are used to design simple algorithms with low communication cost and it has applications in image processing and signal processing [1,3].

We consider the following problem of generalizing the property of bipancyclicity of hypercubes to the existence of $l$ -vertex, $k$ -regular subgraphs for various values of $l$ that are also $k$ -connected and bipancyclic. This will give subgraphs of $Q_{n}$ with less number of vertices which retain the important properties of $Q_{n}$ such as regularity, high connectivity, and bipancyclicity.

Problem 1. For a given integer $k$ with $3 \leq k \leq n,$ determine all integers $l$ for which there exists an $l$ -vertex, $k$ -regular subgraph of $Q_{n}$ that is both $k$ -connected and bipancyclic.

This problem is also related to the problem of embedding regular graphs into hypercubes. Cybenko et al. [4] proved that the problem of deciding whether or not a given graph is embeddable into a hypercube is NP-complete, in fact, the problem is NP-complete even for trees [5].

Since the hypercube $Q_{n}$ is a bipartite graph, every regular subgraph of it has even number of vertices. For $k = 3,$ Ramras [6] established that every even integer from 8 to $2^{n}$ except 10 can be the number of vertices of a 3-regular subgraph of $Q_{n} .$ Borse and Shaikh [7] improved this result by showing that such a 3-regular subgraph can be bipancyclic also. They solved the above problem for $k = 3$ and $k = 4$ in [7] and [8], receptively. They established that, for $k \in {3, 4},$ $Q_{n}$ has a $k$ -regular, $k$ -connected, bipancyclic subgraph on $l$ vertices if and only if $l = 2^{k}$ or $l$ is an even integer with $2^{k} + 2^{k - 1} \leq l \leq 2^{n} .$ The problem remains open for $k \geq 5.$

Besides hypercubes, the special case $k = 3$ of the above problem is settled for the class of the Cartesian product of cycles in [9] and for the class of the Cartesian product of paths in [10]. Also, Borse et al. [11] proved the existence of a factorization of the Cartesian product of $r$ cycles, each of length a power of 2, into isomorphic $k$ -regular, $k$ -connected and bipancyclic subgraphs with the number of vertices a power of 2, for $2 \leq k < 2 r .$ Moreover, the number of vertices of a smallest $k$ -regular subgraph of an $r$ -regular graph $G$ is related to the conditional $k$ -edge-connectivity of $G$ [12].

In this paper, we settle Problem 1 for the case $k = 5.$ The following is the main result of the paper.

Theorem 1 (Main Theorem). For $n \geq 5,$ there exists a $5$ -regular, $5$ -connected and bipancyclic subgraph of the hypercube $Q_{n}$ on $l$ vertices if and only if $l \in {32, 48}$ or $l$ is an even integer such that $52 \leq l \leq 2^{n} .$

For general $k,$ Borse and Shaikh [8] obtained the following result about the non-existence of $k$ -regular subgraphs of $Q_{n}$ on a certain number of vertices.

Theorem 2 ([8]). For a given integer $k$ with $1 \leq k \leq n,$ every subgraph of $Q_{n}$ with minimum degree at least $k$ either is isomorphic to $Q_{k}$ or has at least $2^{k} + 2^{k - 1}$ vertices.

In this paper, we improve this theorem as follows.

Theorem 3. For a given integer $k$ with $2 \leq k \leq n,$ if $H$ is a subgraph of $Q_{n}$ with minimum degree at least $k,$ then one of the following holds:

$H$ is isomorphic to $Q_{k} .$
$H$ is a spanning subgraph of the subgraph of $Q_{n}$ induced by $V (C Q_{k - 2})$ for some cycle $C$ of length six.
$H$ has at least $2^{k} + 2^{k - 1} + 2^{k - 3}$ vertices.

Thus, if $2 \leq k \leq n$ and $1 \leq l < 2^{k} + 2^{k - 1} + 2^{k - 3}$ with $l \notin {2^{k}, 2^{k} + 2^{k - 1}},$ then $Q_{n}$ does not have a $k$ -regular subgraph on $l$ vertices and hence no $k$ -regular, $l$ -vertex graph is embeddable into $Q_{n} .$

We provide preliminary results in Section 2 and prove Theorem 3 in Section 3. The proof of Main Theorem 1 is divided into the next three sections. A construction of 5-regular subgraphs of $Q_{n}$ is given in Section 4. The connectivity and bipancyclicity properties of these subgraphs are dealt in Section 5 and Section 6, respectively.

2. Preliminaries

We can write $Q_{n}$ as $Q_{n - k} Q_{k}$ for $0 \leq k \leq n,$ where $Q_{0}$ is the complete graph $K_{1} .$ A $k$ -cycle means a cycle of length $k .$ We need the following lemmas.

Lemma 1 ([3]). Let $G_{i}$ be an $m_{i}$ -regular and $m_{i}$ -connected graph for $i = 1, 2.$ Then the graph $G_{1} G_{2}$ is $(m_{1} + m_{2})$ -regular and $(m_{1} + m_{2})$ -connected.

Lemma 2 ([13]). If $P$ and $Q$ are non-trivial paths and one of them has an even number of vertices, then the graph $P Q$ is bipancyclic.

Hence $C K_{2}$ is bipancyclic if $C$ is a non-trivial path or a cycle of length at least three.

Lemma 3 ([8]). For $n \geq 3,$ the hypercube $Q_{n}$ has a Hamiltonian cycle $C$ with a chord $e$ such that there is a $4$ -cycle in $Q_{n}$ containing $e$ and three edges of $C .$

Lemma 4 ([8]). Let $l$ be an even integer such that $6 \leq l \leq 2^{n} - 2.$ Then there exists an $l$ -cycle $C$ in $Q_{n}$ containing six vertices $x,$ $y,$ $z,$ $u,$ $v,$ $w$ and there are two vertices $g,$ $h$ in $V (Q_{n}) - V (C)$ such that

$g$ is adjacent to $x,$ $y,$ $z;$
$h$ is adjacent to $u,$ $v,$ $w;$
$x u,$ $u y$ and $y v$ are edges of $C .$

We obtain a similar result as follows.

Lemma 5. Let $l$ be an even integer such that $8 \leq l \leq 2^{n} - 2.$ Then there exists an $l$ -cycle $C$ in $Q_{n}$ and a vertex $u$ in $V (Q_{n}) - V (C)$ having four pairwise non-adjacent neighbours in $C .$

Proof. Suppose $n = 4.$ Clearly, $C = < v_{1}, v_{2}, \dots, v_{8}, v_{1} >$ is a required 8-cycle in $Q_{4}$ as shown by bold lines in Figure 1. Replacing the edge $v_{1} v_{2}$ of $C$ by a path of length 3 avoiding $u$ gives a 10-cycle $C^{'}$ and replacing the edge $v_{3} v_{4}$ of $C^{'}$ by a path of length 3 or 5 that is edge-disjoint with $C^{'}$ produces required 12-cycle and 14-cycle. Thus the result holds for $n = 4.$

Suppose $n \geq 5.$ Write $Q_{n}$ as $Q_{n - 2} Q_{2} .$ Then $Q_{n}$ is obtained from four copies $Q_{n - 2}^{1},$ $Q_{n - 2}^{2},$ $Q_{n - 2}^{3},$ $Q_{n - 2}^{4}$ of $Q_{n - 2}$ such that $Q_{n - 2}^{i}$ is joined to $Q_{n - 2}^{i + 1}$ for $i = 1, 2, 3$ by a matching between their corresponding vertices. Vertices of $Q_{n - 2}^{1}$ are joined to the corresponding vertices of $Q_{n - 2}^{4} .$

Since $n - 2 \geq 3,$ by Lemma 3, each $Q_{n - 2}^{i}$ contains a Hamiltonian cycle $C^{i}$ with a chord $e_{i}$ such that there is a 4-cycle in $Q_{n - 2}^{i}$ containing $e_{i}$ and three edges from $C^{i} .$ For simplicity let $r = 2^{n - 2} .$ Label the set of vertices of $Q_{n - 2}^{i}$ by ${v_{p}^{i} | p = 1, 2, \dots, r}$ so that $C^{i} = < v_{1}^{i}, v_{2}^{i}, \dots, v_{r}^{i}, v_{1}^{i} >$ and $e = v_{2}^{i} v_{r - 1}^{i} .$ We now construct a cycle $Z$ of length $l$ in $Q_{n},$ as required, from the cycles $C^{1}, C^{2}, C^{3}, C^{4}$ and the chord $e_{1}$ of $C^{1} .$ If $8 \leq l \leq 2^{n - 1} + 4,$ then $l = 2 t + 6,$ where $1 \leq t = l / 2 - 3 \leq 2^{n - 2} - 1 = r - 1.$ In this case, take $Z$ as the cycle shown in Figure 2(a). If $2^{n - 1} + 6 \leq l \leq 2^{n} - 4,$ then $l = 2 m + 2^{n - 1}$ with $3 \leq m = l / 2 - 2^{n - 2} \leq 2^{n - 1} - 2^{n - 2} - 2 = r - 2.$ In this case, choose $Z$ to be the cycle shown in Figure 2(b). Finally, for $l = 2^{n} - 2$ take $Z$ as the cycle given in Figure 2(c). In each case, $Z$ is a cycle of length $l$ in $Q_{n},$ and further, the vertex $v_{1}^{1}$ is not on $Z$ but it has four pairwise non-adjacent neighbours $v_{2}^{1}, v_{r}^{1}, v_{1}^{2}, v_{1}^{4}$ in $Z .$ This completes the proof.

3. Proof of Theorem 3

In this section, we prove Theorem 3. For a graph $G,$ let $G [S]$ denote the induced subgraph of $G$ on a vertex subset $S \subseteq V (G) .$ The minimum degree of $G$ is denoted by $δ (G) .$ If $G$ is isomorphic to a graph $H,$ then we write $G ≅ H .$ Since $Q_{n} = Q_{n_{-} 1} K_{2},$ we can split $Q_{n}$ into two copies $Q_{n - 1}^{0}$ and $Q_{n - 1}^{1}$ of $Q_{n - 1} .$ If $H$ is a subgraph of $Q_{n - 1}^{0},$ then there is a subgraph $H^{'}$ of $Q_{n - 1}^{1}$ isomorphic to $H$ such that the vertex set of $H^{'}$ is the set of neighbours of $H$ in $Q_{n - 1}^{1} .$ We say that $H^{'}$ is the subgraph of $Q_{n - 1}^{1}$ corresponding to $H .$

We need the following result.

Lemma 6 ([8]). For a given integer $k$ with $1 \leq k < n,$ if $H$ is a subraph of $Q_{n}$ isomorphic to $Q_{k},$ then every vertex in $V (Q_{n}) - V (H)$ has at most one neighbour in $H .$

Proof of Theorem 3. By Theorem 2, (i) holds or $| V (H) | \geq 2^{k} + 2^{k - 1} .$ Suppose (i) does not hold. Then $| V (H) | \geq 2^{k} + 2^{k - 1} .$ We prove, by induction on $k,$ that (ii) holds if $| V (H) | = 2^{k} + 2^{k - 1},$ otherwise (iii) holds. Suppose $k = 2.$ Then $| V (H) | = 6$ or $| V (H) | \geq 7 .$ If $| V (H) | = 6,$ then it follows that $H$ is a chordless 6-cycle or a 6-cycle with a chord and so (ii) holds. If $| V (H) | \geq 7 > 2^{2} + 2^{2 - 1} + 2^{2 - 3},$ then (iii) follows. Thus the result is true for $k = 2.$

Suppose $k \geq 3.$ Assume that the result holds for the subgraphs of $Q_{n}$ of minimum degree at least $k - 1.$ Let $e$ be an edge of $H .$ Without loss of generality, we may assume that the end vertices of $e$ differ in the first coordinate only. Write $Q_{n} = Q_{n - 1}^{0} \cup Q_{n - 1}^{1} \cup D,$ where $D$ is the set of all edges in $Q_{n}$ whose end vertices differ in the first coordinate only. Then $e \in D .$ Hence $H$ intersects both $Q_{n - 1}^{0}$ and $Q_{n - 1}^{1}$ . Let $H_{i} = H \cap Q_{n - 1}^{i}$ for $i = 0, 1.$ Then $δ (H_{i}) \geq k - 1.$ We may assume that $| V (H_{0}) | \leq | V (H_{1}) | .$

By induction hypothesis, $H_{0} ≅ Q_{k - 1}$ or $H_{0}$ is a spanning subgraph of $Q_{n} [V (C Q_{k - 3})]$ for some $6$ -cycle $C$ or $| V (H_{0}) | \geq 2^{k - 1} + 2^{k - 2} + 2^{k - 4} .$ Hence $| V (H_{0}) | = 2^{k - 1}$ or $| V (H_{0}) | = 3 (2^{k - 2})$ or $| V (H_{0}) | \geq 2^{k - 1} + 2^{k - 2} + 2^{k - 4} .$ We consider these three cases separately.

Case (i). Suppose $| V (H_{0}) | \geq 2^{k - 1} + 2^{k - 2} + 2^{k - 4} .$

Consider $| V (H) | = | V (H_{1}) | + | V (H_{0}) | \geq 2 | V (H_{0}) | = 2^{k} + 2^{k - 1} + 2^{k - 3}$ as $| V (H_{1}) | \geq | V (H_{0}) | .$ Therefore (iii) holds.

Case (ii). Suppose $| V (H_{0}) | = 2^{k - 1} .$

In this case, $H_{0}$ is isomorphic to $Q_{k - 1} .$ As $δ (H) \geq k,$ each vertex of $H_{0}$ has a neighbour in $H_{1} .$ Let $W_{1}$ be the subgraph of $Q_{n - 1}^{1}$ corresponding to $H_{0} .$ Then $W_{1} ≅ Q_{k - 1}$ and $V (W_{1}) \subseteq V (H_{1}) .$ Let $W_{2}$ be the subgraph of $H_{1}$ induced by $V (H_{1}) - V (W_{1}) .$ Observe that no vertex of $W_{2}$ has a neighbour in $H_{0}$ and by Lemma 6, it has at most one neighbour in $W_{1} .$ Therefore $δ (W_{2}) \geq k - 1.$ By Theorem 2, $W_{2} ≅ Q_{k - 1}$ or $| V (W_{2}) | \geq 2^{k - 1} + 2^{k - 2} .$ In the later case, (iii) holds as $| V (H)) | = | V (H_{0}) | + | V (W_{1}) | + | V (W_{2}) | \geq 2^{k - 1} + 2^{k - 1} + 2^{k - 1} + 2^{k - 2} > 2^{k} + 2^{k - 1} + 2^{k - 3} .$ Suppose $W_{2} ≅ Q_{k - 1} .$ Then the subgraph of $Q_{n}$ induced by the vertices of $H_{0}, W_{1}, W_{2}$ is isomorphic to $P_{3} Q_{k - 1} = (P_{3} K_{2}) Q_{k - 2},$ where $P_{3}$ is a path on three vertices. Since $P_{3} K_{2}$ is a 6-cycle with a chord, (ii) holds.

Case (iii). $H_{0}$ is a spanning subgraph of $Q_{n} [V (C Q_{k - 3})]$ for some $6$ -cycle $C .$

We consider two subcases depending on whether the cycle $C$ has a chord or not.

Subcase (i). Suppose $C$ is chordless.

Then $H_{0}$ is $(k - 1)$ -regular and in fact, $H_{0} ≅ C Q_{k - 3} .$ Let $W_{1}$ be the subgraph of $Q_{n - 1}^{1}$ corresponding to $H_{0} .$ Then $V (W_{1}) \subseteq V (H_{1}) .$ If $V (W_{1}) = V (H_{1}),$ then $W_{1} = H_{1} .$ As $H ≅ H_{0} K_{2} ≅ (C Q_{k - 3}) K_{2} ≅ C Q_{k - 2},$ (ii) follows. Suppose $V (H_{1}) - V (W_{1}) \neq \emptyset .$ Let $W_{2}$ be the subgraph of $H_{1}$ induced by $V (H_{1}) - V (W_{1}) .$ As $Q_{n}$ is triangle-free, it follows from Lemma 6 that every vertex of $W_{2}$ has at most three neighbours in $W_{1} .$ This shows that $δ (W_{2}) \geq k - 3.$ By Theorem 2, $| V (W_{2}) | \geq 2^{k - 3} .$ Thus $| V (H) | = | V (H_{0}) | + | V (W_{1}) | + | V (W_{2}) | \geq 3 (2^{k - 2}) + 3 (2^{k - 2}) + 2^{k - 3} = 2^{k} + 2^{k - 1} + 2^{k - 3} .$ Therefore (iii) holds in this case.

Subcase (ii). Suppose $C$ has a chord.

Then $C$ is a spanning subgraph of $P_{3} K_{2}$ and hence $H_{0}$ is a spanning subgraph of $P_{3} Q_{k - 2} .$ Let $1, 2, 3$ be the vertices of the path $P_{3}$ in order and let $L_{i}$ the copy of $Q_{k - 2}$ in $H_{0}$ corresponding to the vertex $i$ for $i \in {1, 2, 3} .$ Let $R_{i}$ be the subgraph of $Q_{n - 1}^{1}$ corresponding to $L_{i}$ for $i \in {1, 2, 3} .$ Then $R_{i} ≅ Q_{k - 2} .$ Since the degree of every member of $V (L_{1}) \cup V (L_{3})$ is $k - 1$ in $H_{0},$ we have $V (R_{1}) \subseteq V (H_{1})$ and $V (R_{3}) \subseteq V (H_{1}) .$ If $V (H_{1}) = V (R_{1}) \cup V (R_{2}) \cup V (R_{3}),$ then (ii) holds (see Figure 3(a)). Suppose $V (H_{1}) - V (R_{1}) \cup V (R_{2}) \cup V (R_{3})$ is non-empty and let $W_{3}$ be the subgraph of $H_{1}$ induced by this set. Then, by Lemma 6, $δ (W_{3}) \geq k - 2.$ Therefore, by Theorem 2, $W_{3} ≅ Q_{k - 2}$ or $| V (W_{3}) | \geq 2^{k - 2} + 2^{k - 3} .$ In the later case, (iii) holds.

Suppose $W_{3} ≅ Q_{k - 2} .$ It follows from Lemma 6 that every vertex of $W_{3}$ has a neighbour in $R_{i}$ for $i = 1, 3$ but no neighbour in $R_{2} .$ Suppose $V (R_{2}) \cap V (H_{1}) = \emptyset .$ Then $V (H_{1}) = V (R_{1}) \cup V (R_{3}) \cup V (W_{3})$ (see Figure 3(b)). It follows that $H = Z Q_{k - 2},$ where $Z$ is a 6-cycle whose six vertices correspond to $L_{1}, L_{2}, L_{3}, R_{3}, W_{3}, R_{1}$ in order, and so, (ii) holds. Suppose $V (R_{2}) \cap V (H_{1}) \neq \emptyset .$ Then the graph $R_{2} \cap H_{1}$ has minimum degree at least $k - 3$ and hence, it has at least $2^{k - 3}$ vertices by Theorem 2. Thus $| V (H) | = | V (H_{0}) | + | V (R_{1}) | + | V (R_{3}) | + | V (W_{3}) | + | V (R_{2} \cap H_{1}) | \geq 6 (2^{k - 2}) + 2^{k - 3} .$ Therefore (iii) holds. This completes the proof.

Corollary 1. Every $5$ -regular subgraph of $Q_{n}$ has $32, 48$ or at least $52$ vertices.

4. Construction of $5$ -regular Subgraphs of $Q_{n}$

In this section, we give a construction of an $l$ -vertex, $5$ -regular subgraph of the hypercube $Q_{n} .$ Suppose $Q_{n}$ has a 5-regular subgraph on $l$ vertices. Then $l$ is an even integer and by Corollary 1, we have $l \in {32, 48}$ or $52 \leq l \leq 2^{n} .$ We prove that for every such $l$ there exists a $5$ -regular subgraph of $Q_{n}$ with $n \geq 6$ that is both $5$ -connected and bipancyclic. The case when $l$ is a multiple of 4 follows trivially from the following result.

Theorem 4 ([8]). If $n \geq 4$ and $l$ is an even integer such that $l = 16$ or $24 \leq l \leq 2^{n},$ then there exists a $l$ -vertex, $4$ -regular subgraph of $Q_{n}$ that is both $4$ -connected and bipancyclic.

Lemma 7. If $n \geq 6$ and $l$ is a multiple of $4$ such that $l \in {32, 48}$ or $52 \leq l \leq 2^{n},$ then there exists a $5$ -regular, $5$ -connected and bipancyclic subgraph of $Q_{n}$ on $l$ vertices.

Proof. We can write $l = 4 m,$ where $m = 8$ or $m$ is an integer such that $12 \leq m \leq 2^{n - 2} .$ Express $Q_{n}$ as $Q_{n - 1} K_{2} .$ Since $n - 1 \geq 4,$ $Q_{n - 1}$ has a $4$ -regular, $4$ -connected and bipancyclic subgraph $H$ on $2 m$ vertices by Theorem 4. Therefore, by Lemma 1, the graph $H K_{2}$ is a $5$ -regular and $5$ -connected subgraph of $Q_{n}$ on $4 m = l$ vertices. As $H$ is bipancyclic, it has a Hamiltonian cycle and so has a Hamiltonian path. Hence, by Lemma 2, $H K_{2}$ is bipancyclic.

Suppose $l$ is an even integer such that $52 \leq l \leq 2^{n}$ but not a multiple of 4. Then $n \geq 6$ and $54 \leq l \leq 2^{n} - 2.$ We have the following four cases.

$(i)$ $l = 16 k + 2$ with $4 \leq k \leq 2^{n - 4} - 1$
$(i i)$ $l = 16 k + 6$ with $3 \leq k \leq 2^{n - 4} - 1.$
$(i i i)$ $l = 16 k + 10$ with $3 \leq k \leq 2^{n - 4} - 1.$
$(i v)$ $l = 16 k + 14$ with $3 \leq k \leq 2^{n - 4} - 1.$

Case (i). $l = 16 k + 2$ with $4 \leq k \leq 2^{n - 4} - 1.$

In this case, $n \geq 7$ and $66 \leq l \leq 2^{n} - 14.$ Write $Q_{n} = Q_{n - 3} Q_{3} .$ By Lemma 5, $Q_{n - 3}$ contains a cycle $C$ of length $2 k$ and there is a vertex $g \in V (Q_{n - 3}) - V (C)$ with four pairwise non-adjacent neighbours $x, y, z, w$ in $C .$ Let $V (Q_{3}) = {a_{0}, a_{1}, \dots, a_{7}}$ so that $a_{0}, a_{1}, a_{2}, a_{3}, a_{0}$ and $a_{4}, a_{5}, a_{6}, a_{7}, a_{4}$ are 4-cycles and $a_{0} a_{7}, a_{1} a_{6}, a_{2} a_{5}$ and $a_{3} a_{4}$ are edges of $Q_{3} .$ Then $C Q_{3}$ is a 5-regular subgraph of $Q_{n}$ with $16 k$ vertices containing a copy $C^{i}$ of $C$ corresponding to the vertex $a_{i}$ of $Q_{3} .$ Let $g_{i}, x_{i}, y_{i}, z_{i}, w_{i}$ be the vertices of $Q_{n - 3}^{i}$ corresponding to the vertices $g, x, y, z, w,$ respectively.

Let $L_{1}$ be the subgraph of $Q_{n}$ with $V (L_{1}) = {x_{i}, y_{i}, z_{i}, w_{i}, g_{i} : i = 0, 7}$ and $E (L_{1}) = {g_{i} x_{i}, g_{i} y_{i}, g_{i} z_{i}, g_{i} w_{i} : i = 0, 7} \cup {g_{0} g_{7}} .$ We define a graph $H_{1}$ from $C Q_{3}$ and $L_{1}$ as follows. $H_{1} = (C Q_{3}) \cup L_{1} - {x_{0} x_{7}, y_{0} y_{7}, z_{0} z_{7}, w_{0} w_{7}} (s e e F i g u r e 4) .$ Clearly, $H_{1}$ is a 5-regular subgraph of $Q_{n}$ on $16 k + 2 = l$ vertices.

Now, to construct $5$ -regular subgraphs in Cases (ii), (iii) and (iv), we choose a cycle $C$ in $Q_{n - 3}$ of length $2 k$ by Lemma 4. Then there are six vertices $x,$ $y,$ $z,$ $u,$ $v,$ $w$ on $C$ and two vertices $g, h$ in $V (Q_{n - 3}) - V (C)$ such that $g$ is adjacent to $x,$ $y,$ $z,$ and $h$ is adjacent to $u,$ $v,$ $w,$ and $x u,$ $u y,$ $y v$ are edges of $C .$ Let $H = C Q_{3} .$ Then $H$ is a 5-regular subgraph of $Q_{n}$ on $16 k$ vertices. As in Case (i), let $C^{i}$ be a copy of $C$ corresponding to the vertex $a_{i}$ of $Q_{3}$ and let $g_{i}, h_{i}, x_{i}, y_{i}, z_{i}, u_{i}, v_{i}, w_{i}$ be the vertices of $Q_{n - 3}^{i}$ corresponding to $g, h, x, y, z, u, v, w,$ respectively.

Figure 4. The Subgraph $H_{1}$ on $16 k + 2$ Vertices

Case (ii). Suppose $l = 16 k + 6$ with $3 \leq k \leq 2^{n - 4} - 1.$

Clearly, $54 \leq l \leq 2^{n} - 10.$ Let $L_{2}$ be the subgraph of $Q_{n}$ with vertex set ${g_{i}, x_{i}, y_{i}, z_{i} : i = 0, 1, 2, 5, 6, 7}$ and edge set ${g_{i} x_{i}, g_{i} y_{i}, g_{i} z_{i} : i = 0, 1, 2, 5, 6, 7} \cup {g_{0} g_{1}, g_{1} g_{2}, g_{2} g_{5}, g_{5} g_{6}, g_{6} g_{7}, g_{7} g_{0}} .$ Define a subgraph $H_{2}$ of $Q_{n}$ from the graphs $H$ and $L_{2}$ as follows. $H_{2} = (H \cup L_{2}) - {x_{0} x_{1}, y_{0} y_{1}, z_{0} z_{1}, x_{2} x_{5}, y_{2} y_{5}, z_{2} z_{5}, x_{6} x_{7}, y_{6} y_{7}, z_{6} z_{7}} .$ The graph $H_{2}$ is depicted in Figure 5. It is easy to see that $H_{2}$ is a 5-regular subgraph of $Q_{n}$ on $l$ vertices.

Figure 5. The Subgraph $H_{2}$ on $16 k + 6$ Vertices

Case (iii). $l = 16 k + 10$ with $3 \leq k \leq 2^{n - 4} - 1.$

Consider the three edge sets: $F_{1} = {g_{0} g_{1}, g_{1} g_{2}, g_{2} g_{5}, g_{5} g_{6}, g_{6} g_{7}, g_{7} g_{0}},$ $F_{2} = {h_{2} h_{3}, h_{3} h_{4}, h_{4} h_{5}, h_{5} h_{2}},$ and $F_{3} = {x_{0} x_{7}, y_{0} y_{7}, z_{0} z_{7}, x_{1} x_{2}, y_{1} y_{2}, z_{1} z_{2}, x_{5} x_{6}, y_{5} y_{6}, z_{5} z_{6}, u_{2} u_{3}, v_{2} v_{3}, w_{2} w_{3}, u_{4} u_{5}, v_{4} v_{5}, w_{4} w_{5}} .$

Let $L_{3}$ be the subgraph of $Q_{n}$ with vertex set
${g_{i}, x_{i}, y_{i}, z_{i} : i = 0, 1, 2, 5, 6, 7} \cup {h_{j}, u_{j}, v_{j}, w_{j} : j = 2, 3, 4, 5}$ and edge set ${g_{i} x_{i}, g_{i} y_{i}, g_{i} z_{i} : i = 0, 1, 2, 5, 6, 7} \cup {h_{j} u_{j}, h_{j} v_{j}, h_{j} w_{j} : j = 2, 3, 4, 5} \cup F_{1} \cup F_{2} .$ We now define a subgraph $H_{3}$ of $Q_{n}$ which is shown in Figure 6 as $H_{3} = (H \cup L_{3}) - F_{3}$ Clearly, $H_{3}$ is a 5-regular subgraph of $Q_{n}$ on $16 k + 10$ vertices.

Figure 6. The subgraph $H_{3}$ on $16 k + 10$ vertices

Case (iv). $l = 16 k + 14$ with $3 \leq k \leq 2^{n - 4} - 1.$

We define the four edge sets $M_{1}, M_{2}, M_{3}, M_{4}$ as follows.

$M_{1} = {g_{0} g_{1}, g_{1} g_{2}, g_{2} g_{3}, g_{3} g_{4}, g_{4} g_{5}, g_{5} g_{6}, g_{6} g_{7}, g_{7} g_{0}};$ $M_{2} = {h_{0} h_{1}, h_{1} h_{2}, h_{2} h_{5}, h_{5} h_{6}, h_{6} h_{7}, h_{7} h_{0}};$ $M_{3} = {u_{0} u_{7}, v_{0} v_{7}, w_{0} w_{7}, u_{1} u_{6}, v_{1} v_{6}, w_{1} w_{6}, u_{2} u_{5}, v_{2} v_{5}, w_{2} w_{5}}$ and $M_{4} = {x_{0} x_{1}, y_{0} y_{1}, z_{0} z_{1}, x_{2} x_{3}, y_{2} y_{3}, z_{2} z_{3}, x_{4} x_{5}, y_{4} y_{5}, z_{4} z_{5}, x_{6} x_{7}, y_{6} y_{7}, z_{6} z_{7}} .$ Let $L_{4}$ be the subgraph of $Q_{n}$ having vertex set ${g_{i}, x_{i}, y_{i}, z_{i} : i = 0, 1, \dots, 7} \cup {h_{j}, u_{j}, v_{j}, w_{j} : j = 0, 1, 2, 5, 6, 7}$ and edge set ${g_{i} x_{i}, g_{i} y_{i}, g_{i} z_{i} : i = 0, 1, \dots, 7} \cup {h_{j} u_{j}, h_{j} v_{j}, h_{j} w_{j} : j = 0, 1, 2, 5, 6, 7} \cup M_{1} \cup M_{2} .$ We define a subgraph $H_{4}$ of $Q_{n}$ as follows. $H_{4} = (H \cup L_{4}) - (M_{3} \cup M_{4}) .$ The graph $H_{4}$ is shown in Figure 7. Clearly, it is a 5-regular subgraph of $Q_{n}$ on $16 k + 14$ vertices.

Figure 7. The subgraph $H_{4}$ on $16 k + 14$ vertices

Thus we have constructed $5$ -regular subgraphs $H_{1},$ $H_{2},$ $H_{3},$ and $H_{4}$ of the hypercube $Q_{n}$ on $l$ vertices in each of the four cases. In the next two sections, we prove that these subgraphs are $5$ -connected and bipancyclic.

5. Connectivity

In this section, we prove that all the four subgraphs $H_{1}, H_{2}, H_{3},$ and $H_{4}$ of $Q_{n}$ that are constructed in Section 4 and shown in Figures 4, 5, 6, and 7, respectively are $5$ -connected.
If $F$ is the matching in $H_{i}$ consisting of edges having one end vertex in the lower side (L) and the other end vertex in the upper side (R) in the figure of $H_{i},$ then $F$ is an edge-cut of $H_{i} .$ The graph $H_{i} - F$ has two components and further, the components are 4-connected and isomorphic to each other. We prove that these components together with the matching $F$ give a 5-connected graph. We first prove the following observations for general graphs.

Lemma 8. Let $G$ be a simple $k$ -connected graph and let $v_{1}, v_{2}, \dots, v_{k}$ be distinct vertices of $G .$ Let $\hat{G}$ be a new graph obtained from $G$ by adding a new vertex $u$ and $k$ edges $u v_{i}$ for $i = 1, 2, \dots, k .$ Then $\hat{G}$ is $k$ -connected.

Proof. The graph $\hat{G}$ is shown in Figure 8(a). Suppose $S \subseteq V (\hat{G})$ with $| S | < k .$ If $u \notin S,$ then $S \subseteq V (G)$ and so $G - S$ is connected. Therefore $\hat{G} - S$ is connected as the vertex $u$ has a neighbour in $G - S .$ Suppose $u \in S .$ Then $S - {u}$ contains at most $k - 2$ vertices of $G$ and hence $G - (S - {u}) = \hat{G} - S$ is connected. Thus $\hat{G}$ is $k$ -connected.

Lemma 9. Let $G$ be a simple $k$ -connected graph with at least $2 k$ vertices and an independent set ${u_{1}, u_{2}, \dots, u_{r}},$ where $1 \leq r \leq k .$ Suppose $G^{'}$ is a simple graph obtained from $G$ by adding a new vertex $u$ and $k$ new edges each having one end vertex $u$ including the $r$ edges $u u_{1}, u u_{2}, \dots, u u_{r} .$ Let $H$ be the graph obtained from the graph $G^{'} K_{2}$ by deleting the matching consisting of $r$ edges between the two copies of $G^{'}$ corresponding to the vertices $u_{1}, u_{2}, \dots, u_{r} .$ Then the graph $H$ is $(k + 1)$ -connected.

Proof. The graph $H$ is shown in Figure 8(b). The graph $G^{'} K_{2}$ is obtained from $G^{'}$ and a copy $G^{″}$ of $G^{'}$ by adding edges between their corresponding vertices. Let $v$ and $v_{i}$ be the vertices of $G^{″}$ corresponding to $u$ and $u_{i}$ for $1 \leq i \leq r,$ respectively and let $M = {u_{1} v_{1}, u_{2} v_{2}, \dots, u_{r} v_{r}} .$ Then $H = (G^{'} K_{2}) - M .$ Since $G^{'}$ has at least $2 k + 1$ vertices, there are at least $k + 1$ edges in $H$ between $G^{'}$ and $G^{″} .$

Suppose $S \subseteq V (H)$ with $| S | \leq k .$ It is sufficient to prove that $H - S$ is connected. Since $G$ is $k$ -connected, by Lemma 8, the graph $G^{'}$ is $k$ -connected. Suppose $S$ intersects both $V (G^{'})$ and $V (G^{″}) .$ Then both $G^{'} - S$ and $G^{″} - S$ are connected and they are joined to each other by an edge. Hence $H - S$ is connected. Suppose $S \subseteq V (G^{'}) .$ The degree of $u_{i}$ in $G$ is at least $k$ and so it is at least $k + 1$ in $G^{'}$ for any $i \in {1, 2, \dots, r} .$ If $G^{'} - S$ has a component with vertex set a subset of the independent set ${u_{1}, u_{2}, \dots, u_{r}} - S,$ then that component has just one vertex and so $| S | = k + 1,$ a contradiction. Thus every component of $G^{'} - S$ has a neighbour in the connected graph $G^{″}$ in $H - S .$ This shows that $H - S$ is connected.

Figure 8. The Graphs of Lemma 8 and Lemma 9

Let $H_{1}, H_{2}, H_{3},$ and $H_{4}$ be the 5-regular subgraphs of $Q_{n}$ constructed in Section 4. We now prove that these graphs are 5-connected.

Lemma 10. The graph $H_{1}$ is 5-connected.

Proof. The subgraphs of $H_{1}$ induced by $V (C^{0}) \cup V (C^{1}) \cup V (C^{2}) \cup V (C^{3})$ and by $V (C^{4}) \cup V (C^{5}) \cup V (C^{6}) \cup V (C^{7})$ are isomorphic to $C^{0} Z$ for some $4$ -cycle $Z .$ Hence, by Lemma 1, these two subgraphs are 4-connected. Now, by Lemma 9, $H_{1}$ is 5-connected.

Lemma 11. The graph $H_{2}$ is 5-connected.

Proof. The subgraphs of $H_{2}$ induced by $V (C^{0}) \cup V (C^{3})$ and by $V (C^{1}) \cup V (C^{2})$ are isomorphic to $C^{0} K_{2}$ and so, by Lemma 1, they are 3-connected. Hence, by Lemma 9, the upper half subgraph $R$ of $H_{2}$ that is induced by $V (C^{0}) \cup V (C^{1}) \cup V (C^{2}) \cup V (C^{3}) \cup {g_{0}, g_{1}}$ is 4-connected. If $L = H_{2} [V (C^{4}) \cup V (C^{5}) \cup V (C^{6}) \cup V (C^{7}) \cup {g_{6}, g_{7}}],$ then $L$ is isomorphic to $R .$ Thus, by Lemma 9, $H_{2}$ is 5-connected.

Lemma 12. The graph $H_{3}$ is 5-connected.

Proof. By Lemmas 1 and 9, the subgraphs $H_{3} [V (C^{0}) \cup V (C^{3})]$ and $H_{3} [V (C^{1}) \cup V (C^{2}) \cup {g_{1}, g_{2}}]$ of $H_{3}$ are 3-connected. By similar arguments of the proof of Lemma 11, we see that the upper half subgraph $R$ of $H_{3}$ induced by $V (C^{0}) \cup V (C^{1}) \cup V (C^{2}) \cup V (C^{3}) \cup {g_{1}, g_{2}, h_{2}, h_{3}}$ is 4-connected. If $L = H_{3} [V (C^{4}) \cup V (C^{5}) \cup V (C^{6}) \cup V (C^{7}) \cup {g_{5}, g_{6}, h_{4}, h_{5}}],$ then $L$ is isomorphic to $R .$ Now, the result follows from Lemma 9.

Lemma 13. The graph $H_{4}$ is 5-connected.

Proof. Let $V_{1} = V (C^{0}) \cup V (C^{1}) \cup {g_{0}, g_{1}}$ and let $V_{2} = V (C^{2}) \cup V (C^{3}) \cup {g_{2}, g_{3}} .$ By Lemma 9, the subgraphs $H_{4} [V_{1}]$ and $H_{4} [V_{2}]$ of $H_{4}$ are 3-connected. Therefore the graph $H_{4} [V_{1} \cup V_{2}]$ is 4-connected. Hence the graph $R = H_{4} [V_{1} \cup V_{2} \cup {h_{0}, h_{1}, h_{2}}]$ is also 4-connected. The subgraph $L$ of $H_{4}$ induced by $V (H_{4}) - V (R)$ is isomorphic to $R$ and so, it is 4-connected.

We now prove that $H_{4}$ is 5-connected. Suppose $S \subseteq V (H_{4})$ with $| S | \leq 4.$ It is sufficient to prove that $H_{4} - S$ is connected. If $S$ intersects both $V (R)$ and $V (L),$ then $R - S$ and $L - S$ are connected and they are joined to each other by an edge leaving $H_{4} - S$ connected. Suppose $S \subseteq V (R) .$ The set of vertices of $R$ that do not have any neighbour in $V (L)$ is $A = {h_{1}, g_{1}, g_{2}, u_{0}, v_{0}, w_{0}, u_{1}, v_{1}, w_{1}, u_{2}, v_{2}, w_{2}} .$ Assume that $R - S$ has a component $D$ such that $V (D) \subseteq A .$ No member of $A$ is isolated in $R - S$ as each has degree five in $R .$ Hence $δ (D) \geq 1.$ Observe that the subgraph of $H_{4}$ induced by $A$ is the forest as shown in Figure 9. Therefore $D$ is a tree containing at least two pendant vertices. So $| S | = 4$ and every pendant vertex of $D$ is adjacent to all the four members of $S .$ This gives $K_{2, 3}$ as a subgraph of $H_{4}$ and so of $Q_{n},$ a contradiction. Hence every component of $R - S$ has a neighbour in the connected graph $L .$ Therefore $H_{4} - S$ is connected. Similarly, $H_{4} - S$ is connected if $S \subseteq V (L) .$

Figure 9. Subgraph of $H_{4}$ Induced by $A$

6. Bipancyclicity

In this section, we prove that the 5-regular graphs $H_{1},$ $H_{2},$ $H_{3},$ and $H_{4}$ constructed in Section 4 are all bipancyclic.

A ladder on $n \geq 4$ vertices has two edges at its two ends. If we identify one of these two edges with an edge of a $k$ -cycle, then it follows that the resulting graph has cycles of every even length from $k$ to $k + n - 2.$ The following lemma is based on this fact.

Lemma 14. Let $l, m, n$ be even integers and $C$ be an $m$ -cycle conatining an edge $x y$ and $L$ be a ladder on $n$ vertices containing an end edge $x^{'} y^{'} .$ Then the graph $C \cup L \cup {x x^{'}, y y^{'}}$ has cycles of all even lengths from $m + 2$ to $m + n$ (see Figure 10).

Figure 10. The Graph $C \cup L \cup {x x^{'}, y y^{'}}$

Lemma 15. The graph $H_{1}$ is bipancyclic.

Proof. Recall that $H_{1}$ contains the eight copies $C^{0}, C^{1}, \dots, C^{7}$ of a $2 k$ -cycle $C .$ Let $E_{i j}$ be the set of edges of $H_{1}$ with one end vertex in the cycle $C^{i}$ and the other in the cycle $C^{j} .$ Consider the subgraph $W = C^{0} \cup C^{1} \cup C^{2} \cup C^{3} \cup C^{4} \cup C^{5} \cup C^{6} \cup C^{7} \cup E_{03} \cup E_{32} \cup E_{25} \cup E_{54} \cup E_{47} \cup E_{76} \cup E_{61} \cup E_{10}$ of $H_{1} .$ Then $W$ is isomorphic to $C Z,$ where $Z$ is an 8-cycle. By Lemma 2, $W$ is bipancyclic. Therefore $W$ and so $H_{1}$ contains a cycle of every even length from 4 to $16 k = | V (W) | .$ Let $C^{i} =< v_{1}^{i}, v_{2}^{i}, \dots v_{2 k}^{i}, v_{1}^{i} >$ for $i = 0, 1, \dots 7$ such that $v_{1}^{i}$ is the label to the neighbor of $g_{i} .$ Then the cycle shown in Figure 11 is a Hamiltonian cycle of $H_{1} .$ Thus the graph $H_{1}$ is bipancyclic.

Recall that we have written $Q_{n}$ as $Q_{n - 3} Q_{3}$ where the vertices of $Q_{3}$ are labeled by $a_{0}, a_{1}, \dots, a_{7},$ so that $a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{0}$ is a Hamiltonian cycle of $Q_{3}$ with chords $a_{0} a_{3}, a_{1} a_{6}, a_{2} a_{5}$ and $a_{4} a_{7} .$ Furthermore, $C$ is a $2 k$ -cycle in $Q_{n - 3}$ and $C^{i}$ is its copy in $Q_{n}$ corresponding to vertex $a_{i}$ of $Q_{3}$ in the construction of the graphs $H_{2}, H_{3}$ and $H_{4} .$ Let $E_{i j}$ be the matching between cycles $C^{i}$ and $C^{j}$ in $Q_{n}$ corresponding to the edge $a_{i} a_{j}$ of $Q_{3} .$ For each $i,$ label the vertices of $C^{i}$ by $v_{1}^{i}, v_{2}^{i}, \dots, v_{2 k}^{i}$ so that $C^{i} =< v_{1}^{i}, v_{2}^{i}, v_{3}^{i}, v_{4}^{i}, \dots, v_{p}^{i}, \dots, v_{q}^{i}, \dots, v_{2 k}^{i}, v_{1}^{i} >$ and $v_{1}^{i}, v_{3}^{i}, v_{p}^{i}$ are the neighbours of the vertex $g_{i},$ and $v_{2}^{i}, v_{4}^{i}, v_{q}^{i}$ are the neighbours of the vertex $h_{i}$ for some $p, q$ with $4 < p, q \leq 2 k$ and $p \neq q .$ Hence the neighbours $x_{i}, y_{i}, z_{i}$ of $g_{i}$ on $C^{i}$ are relabeled as $v_{1}^{i}, v_{3}^{i}, v_{p}^{i},$ respectively. Similarly, the vertices $u_{i}, v_{i}, w_{i}$ are relabeled as $v_{2}^{i}, v_{4}^{i}, v_{q}^{i},$ respectively.

Lemma 16. The graph $H_{2}$ is bipancyclic.

Proof. The graph $H_{2}$ has $16 k + 6$ vertices. Consider the subgraph $W$ of $H_{2},$ where $W = C^{0} \cup C^{1} \cup C^{2} \cup C^{3} \cup C^{4} \cup C^{5} \cup C^{6} \cup C^{7} \cup E_{03} \cup E_{32} \cup E_{21} \cup E_{16} \cup E_{65} \cup E_{54} \cup E_{47} \cup E_{70} .$ Then $W_{2}$ is isomorphic to $C^{0} Z,$ where $Z$ is an 8-cycle. By Lemma 2, it contains cycles of every even length from 4 to $16 k .$ A cycle $Z$ of length $16 k + 6$ in $H_{2}$ is shown in Figure 12. Furthermore, $Z^{'} = (Z - {g_{1}, g_{6}}) \cup {v_{1}^{1} v_{1}^{6}, g_{0} g_{7}}$ is a cycle of length $16 k + 4$ while $Z^{″} = (Z^{'} - {g_{0}, g_{7}}) \cup {v_{1}^{0} v_{1}^{7}}$ is a cycle of length $16 k + 2$ in $H_{2} .$ Thus $H_{2}$ is bipancyclic.

Figure 12. $(16 k + 6)$ -cycle in $H_{2}$

Figure 13. $l$ -cycles in $H_{3}$ for $l \in {16 k + 6, 16 k + 10}$

.5cm

Lemma 17. The graph $H_{3}$ is bipancyclic.

Proof. The graph $H_{3}$ is on $16 k + 10$ vertices. Consider the subgraph $W$ of $H_{3}$ on $12 k$ vertices defined as $W = C^{0} \cup C^{1} \cup C^{3} \cup C^{4} \cup C^{6} \cup C^{7} \cup E_{03} \cup E_{34} \cup E_{47} \cup E_{67} \cup E_{16} \cup E_{01} .$ Then $W$ is isomorphic to $C^{0} Z,$ where $Z$ is a 6-cycle. Hence $W$ contain cycles of all even lengths from $4$ to $12 k .$ Therefore these cycles are also contained in $H_{3} .$ Let $L$ be the ladder on $4 k$ vertices defined as $L = (C^{2} - v_{1}^{2} v_{2}^{2}) \cup (C^{5} - v_{1}^{5} v_{2}^{5}) \cup {v_{i}^{2} v_{i}^{5} : i = 1, 2, \dots, 2 k} .$ Note that $W$ has a Hamiltonian cycle $Z_{1} =< v_{2}^{1}, v_{3}^{1}, \dots, v_{2 k}^{1}, v_{1}^{1}, v_{1}^{0}, v_{2 k}^{0}, v_{2 k - 1}^{0}, \dots, v_{2}^{0}, v_{2}^{3}, \dots, v_{2 k}^{3}, v_{1}^{3}, v_{1}^{4}, v_{2 k}^{4}, \dots, v_{2}^{4}, v_{2}^{7}, \dots, v_{2 k}^{7}, v_{1}^{7}, v_{1}^{6}, v_{2 k}^{6}, \dots, v_{2}^{6}, v_{2}^{1} > .$ Then the subgraph $Z_{1} \cup L \cup {v_{2}^{2} v_{2}^{1}, v_{2}^{5} v_{2}^{6}}$ of $H_{3}$ has $16 k$ vertices. By Lemma 14, it has cycles of every even length from $12 k + 2$ to $16 k .$ Let $Z_{2}$ and $Z_{3}$ be the cycles of length $16 k + 6$ and $16 k + 10$ as shown in Figure 13(a) and 13(b), respectively. Then $Z_{2}^{'} = (Z_{2} - {g_{0}, g_{1}}) \cup {v_{1}^{0} v_{1}^{1}}$ is a cycle of length $(16 k + 4)$ whereas $(Z_{2}^{'} - {g_{6}, g_{7}}) \cup {v_{1}^{6} v_{1}^{7}}$ is a $(16 k + 2)$ -cycle in $H_{3} .$ Finally, $(Z_{3} - {h_{3}, h_{4}}) \cup {v_{2}^{3} v_{2}^{4}, h_{2} h_{5}}$ is a cycle of length $16 k + 8$ in $H_{3} .$ Thus $H_{3}$ is bipancyclic.

Lemma 18. The graph $H_{4}$ is bipancyclic.

Proof. Recall that $H_{4}$ has $16 k + 14$ vertices. We prove that $H_{4}$ contain cycles of every even length from $4$ to $16 k + 14.$ The subgraph of $H_{4},$ $W = C^{0} \cup C^{3} \cup C^{4} \cup C^{7} \cup E_{03} \cup E_{34} \cup E_{47}$ is bipancyclic as it is isomorphic to $C^{0} P_{4},$ where $P_{4}$ is a path on four vertices. This implies that $H_{4}$ contain cycles of every even length from $4$ to $8 k .$ Consider the Hamiltonian cycle $Z_{1}$ of $W,$ where
$Z_{1} =< v_{2}^{0}, v_{3}^{0}, \dots, v_{2 k}^{0}, v_{1}^{0}, v_{1}^{3}, v_{2 k}^{3}, v_{2 k - 1}^{3}, \dots, v_{k + 2}^{3}, v_{k + 2}^{4}, v_{k + 3}^{4}, \dots, v_{2 k}^{4}, v_{1}^{4}, v_{1}^{7}, v_{2 k}^{7}, v_{2 k - 1}^{7}, \dots, v_{2}^{7}, v_{2}^{4}, v_{3}^{4}, \dots, v_{k + 1}^{4}, v_{k + 1}^{3}, v_{k}^{3}, \dots, v_{2}^{3}, v_{2}^{0} >$ . We get two paths $P$ and $Q$ each of length $4 k$ from $C^{1} \cup C^{6}$ and $C^{2} \cup C^{5},$ respectively as follows. $P =< v_{2}^{1}, v_{3}^{1}, \dots, v_{2 k}^{1}, v_{1}^{1}, v_{1}^{6}, v_{2 k}^{6}, v_{2 k - 1}^{6}, \dots, v_{2}^{6} >,$ $Q =< v_{2}^{2}, v_{3}^{2}, \dots, v_{2 k}^{2}, v_{1}^{2}, v_{1}^{5}, v_{2 k}^{5}, v_{2 k - 1}^{5}, \dots, v_{2}^{5} > .$ Then $L_{1} = P \cup Q \cup ({v_{i}^{1} v_{i}^{2}, v_{i}^{5} v_{i}^{6} : i = 1, 2, \dots, 2 k})$ is a ladder on $8 k$ vertices. Hence, by Lemma 14, $Z_{1} \cup L_{1} \cup {v_{2}^{0} v_{2}^{1}, v_{2}^{2} v_{2}^{3}}$ is a subgraph of $H_{4}$ on $16 k$ vertices contains cycle of length $p$ for every even integer $p$ with $8 k + 2 \leq p \leq 16 k .$

Let $Z_{2}$ and $Z_{3}$ be the cycles in $H_{4}$ of length $16 k + 8$ and $16 k + 14$ as shown in Figures 14(a) and 14(b), respectively. If $Z_{2}^{'} = (Z_{2} - {g_{5}, g_{6}}) \cup {v_{1}^{5} v_{1}^{6}};$ $Z_{2}^{″} = (Z_{2}^{'} - {g_{3}, g_{4}}) \cup {v_{1}^{3}, v_{1}^{4}}$ and $Z_{2}^{‴} = (Z_{2}^{″} - {g_{1}, g_{2}}) \cup {v_{1}^{1}, v_{1}^{2}},$ then $Z_{2}^{'},$ $Z_{2}^{″}$ and $Z_{2}^{‴}$ are cycles of lengths $16 k + 6,$ $16 k + 4$ and $16 k + 2,$ respectively. Finally, $Z_{3}^{'} = (Z_{3} - {h_{5}, h_{6}}) \cup {v_{2}^{5} v_{2}^{6}}$ and $Z_{3}^{″} = (Z_{3}^{'} - {h_{1}, h_{2}}) \cup {v_{2}^{1} v_{2}^{2}}$ are cycles of lengths $16 k + 12$ and $16 k + 10,$ respectively. Hence $H_{4}$ is bipancyclic.

Figure 14. $l$ -cycles in $H_{4}$ for $l \in {16 k + 8, 16 k + 14}$

Remark 1. The problem of the existence of a $k$ -regular subgraph of the hypercube $Q_{n}$ of a given order is completely solved for $k = 3, 4, 5.$ To solve the problem for the general value of $k$ one needs to identify the even integers in between $2^{k}$ and $2^{n}$ that cannot be the order of any $k$ -regular subgraph of $Q_{n}$ . By Theorem 3, we have two intervals $(2^{k}, 2^{k} + 2^{k - 1})$ and $(2^{k} + 2^{k - 1}, 2^{k} + 2^{k - 1} + 2^{k - 3})$ with the property that no even integer belonging to any of these intervals is the order of a $k$ -regular subgraph of $Q_{n}$ . There is no further gap for $k \in {3, 4, 5} .$ However, there seems a further gap for $k \geq 6.$ The next interval of the gaps can be found by characterizing the $k$ -regular subgraph of $Q_{n}$ on $2^{k} + 2^{k - 1} + 2^{k - 3}$ vertices. Thus, Problem 1 remains open for $k \geq 6.$

Acknowledgment

The authors are thankful to the referee for fruitful suggestions to improve the presentation of the paper. The first author is financially supported by DST-SERB, Government of India through the project MTR/2018/000447.

Conflict of Interest

The authors declare no conflict of interest

References:

Leighton, F. T.,1992. Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes. San Mateo, CA: M. Kaufmann Publishers Inc.
Zhao, K., Kumar, A. and Yen, J.,2011. Achieving high robustness in supply distribution networks by rewiring. IEEE Transactions on Engineering Management, 58(3), pp.347-362.
Li, T.K., Tsai, C.H., Tan, J. J.M. and Hsu, L.H., 2003. Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes. Information Processing Letters, 87(2), pp.107-110.
Cybenko, G., Krumme, D. W. and Venkataraman, K. N., 1986. Hypercube embedding is NP-complete. In M. T. Heath (Ed.), Proceedings of the first Conference on Hypercube Multiprocessors (pp. 148-157). Philadelphia, PA: Society for Industrial and Applied Mathematics.
Wagner, A. and Corneil, D., 1990. Embedding trees in a hypercube is NP-complete. SIAM Journal on Computing, 19(3), pp.570-590.
Ramras, M., 1999. Regular subgraphs of hypercubes. Ars Combinatoria, 52, pp.21-32.
Borse, Y. M. and Shaikh, S. R., 2015. On 3-regular bipancyclic subgraphs of hypercubes. International Journal of Combinatorics, Article 638767, 4 pages.
Borse, Y. M. and Shaikh, S. R., 2017. On 4-regular, 4-connected bipancyclic subgraphs of hypercubes. Discrete Mathematics, Algorithms and Applications, 9(3), Article 1750032, 12 pages.
Borse, Y. M. and Saraf, J. B., 2019. Existence of 3-regular subgraphs in Cartesian product of cycles. AKCE International Journal of Graphs and Combinatorics, 16(3), pp.332-342.
Miao, L. and Yang, W., 2018. On 3-regular subgraphs in Cartesian products of paths. Journal of Interconnection Networks, 18(02n03), Article 1850009.
Borse, Y. M., Sonawane, A. V. and Shaikh, S. R., 2019. Factorizations of the product of cycles. AKCE International Journal of Graphs and Combinatorics, 16(3), pp.324-331.
Xu, J.M., 2000. On conditional edge-connectivity of graphs. Acta Mathematicae Applicatae Sinica, 16(4), pp.414-419.
Mane, S. A. and Waphare, B. N., 2011. Regular connected bipancyclic spanning subgraphs of hypercubes. Computers & Mathematics with Applications, 62(9), pp.3551-3554.

[1] Leighton, F. T.,1992. Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes. San Mateo, CA: M. Kaufmann Publishers Inc.

[2] Zhao, K., Kumar, A. and Yen, J.,2011. Achieving high robustness in supply distribution networks by rewiring. IEEE Transactions on Engineering Management, 58(3), pp.347-362.

[3] Li, T.K., Tsai, C.H., Tan, J. J.M. and Hsu, L.H., 2003. Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes. Information Processing Letters, 87(2), pp.107-110.

[4] Cybenko, G., Krumme, D. W. and Venkataraman, K. N., 1986. Hypercube embedding is NP-complete. In M. T. Heath (Ed.), Proceedings of the first Conference on Hypercube Multiprocessors (pp. 148-157). Philadelphia, PA: Society for Industrial and Applied Mathematics.

[5] Wagner, A. and Corneil, D., 1990. Embedding trees in a hypercube is NP-complete. SIAM Journal on Computing, 19(3), pp.570-590.

[6] Ramras, M., 1999. Regular subgraphs of hypercubes. Ars Combinatoria, 52, pp.21-32.

[7] Borse, Y. M. and Shaikh, S. R., 2015. On 3-regular bipancyclic subgraphs of hypercubes. International Journal of Combinatorics, Article 638767, 4 pages.

[8] Borse, Y. M. and Shaikh, S. R., 2017. On 4-regular, 4-connected bipancyclic subgraphs of hypercubes. Discrete Mathematics, Algorithms and Applications, 9(3), Article 1750032, 12 pages.

[9] Borse, Y. M. and Saraf, J. B., 2019. Existence of 3-regular subgraphs in Cartesian product of cycles. AKCE International Journal of Graphs and Combinatorics, 16(3), pp.332-342.

[10] Miao, L. and Yang, W., 2018. On 3-regular subgraphs in Cartesian products of paths. Journal of Interconnection Networks, 18(02n03), Article 1850009.

[11] Borse, Y. M., Sonawane, A. V. and Shaikh, S. R., 2019. Factorizations of the product of cycles. AKCE International Journal of Graphs and Combinatorics, 16(3), pp.324-331.

[12] Xu, J.M., 2000. On conditional edge-connectivity of graphs. Acta Mathematicae Applicatae Sinica, 16(4), pp.414-419.

[13] Mane, S. A. and Waphare, B. N., 2011. Regular connected bipancyclic spanning subgraphs of hypercubes. Computers & Mathematics with Applications, 62(9), pp.3551-3554.

Contents

Ars Combinatoria