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.
A graph \(G= (V,E)\) on \(n\) vertices is an \(n\)-vertex graph. A \(2n\)-vertex graph is bipancyclic if it has a cycle of length \(l\) for all even integers \(l\) satisfying \(4 \leq l \leq 2n.\) The Cartesian product of two graphs \(G\) and \(H\) is the graph \(G \Box 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 < 2r.\) 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\Box 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.
We can write \(Q_n\) as \(Q_{n-k} \Box 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 \Box 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\Box Q\) is bipancyclic.
Hence \(C \Box 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;\)
\(xu,\) \(uy\) and \(yv\) 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_1v_2\) of \(C\) by a path of length 3 avoiding \(u\) gives a 10-cycle \(C'\) and replacing the edge \(v_3v_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} \Box 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^i_{n-2}\) contains a Hamiltonian cycle \(C^i\) with a chord \(e_i\) such that there is a 4-cycle in \(Q^i_{n-2}\) containing \(e_i\) and three edges from \(C^i.\) For simplicity let \(r = 2^{n-2}.\) Label the set of vertices of \(Q^i_{n-2}\) by \(\{v^i_p ~|~ p=1,2,\dots,r\}\) so that \(C^i =~ <v^i_1, v^i_2, \dots, v^i_{r}, v^i_1>\) and \(e = v^i_2 v^i_{r-1}.\) 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= 2t + 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 = 2m + 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. ◻
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 \(\delta(G).\) If \(G\) is isomorphic to a graph \(H,\) then we write \(G\cong H.\) Since \(Q_n = Q_{n_-1} \Box 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^{0}_{n-1} \cup Q^{1}_{n-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^{0}_{n-1}\) and \(Q^{1}_{n-1}\). Let \(H_i= H \cap Q^{i}_{n-1}\) for \(i=0, 1.\) Then \(\delta(H_i) \geq k-1.\) We may assume that \(|V(H_0) | \leq |V(H_1)|.\)
By induction hypothesis, \(H_0 \cong Q_{k-1}\) or \(H_0\) is a spanning subgraph of \(Q_n[V(C \Box 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 \(\delta(H) \geq k,\) each vertex of \(H_0\) has a neighbour in \(H_{1}.\) Let \(W_1\) be the subgraph of \(Q^{1}_{n-1}\) corresponding to \(H_0.\) Then \(W_1 \cong 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 \(\delta(W_2)\geq k-1.\) By Theorem 2, \(W_2\cong 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 \cong 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 \Box Q_{k-1} = (P_3 \Box K_2)\Box Q_{k-2},\) where \(P_3\) is a path on three vertices. Since \(P_3 \Box K_2\) is a 6-cycle with a chord, (ii) holds.
Case (iii). \(H_0\) is a spanning subgraph of \(Q_n[V(C \Box 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 \cong C \Box 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 \cong H_0 \Box K_2 \cong (C \Box Q_{k-3})\Box K_2 \cong C \Box 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 \(\delta(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 \Box K_2\) and hence \(H_0\) is a spanning subgraph of \(P_3\Box 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^{1}_{n-1}\) corresponding to \(L_i\) for \(i\in \{1,2,3\}.\) Then \(R_i \cong 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, \(\delta(W_3) \geq k-2.\) Therefore, by Theorem 2, \(W_3 \cong Q_{k-2}\) or \(|V(W_3)| \geq 2^{k-2} + 2^{k-3}.\) In the later case, (iii) holds.
Suppose \(W_3 \cong 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 \Box 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.
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 = 4m,\) where \(m =8\) or \(m\) is an integer such that \(12 \leq m \leq 2^{n-2}.\) Express \(Q_n\) as \(Q_{n-1} \Box K_2.\) Since \(n-1 \geq 4,\) \(Q_{n-1}\) has a \(4\)-regular, \(4\)-connected and bipancyclic subgraph \(H\) on \(2m\) vertices by Theorem 4. Therefore, by Lemma 1, the graph \(H \Box K_2\) is a \(5\)-regular and \(5\)-connected subgraph of \(Q_n\) on \(4m = l\) vertices. As \(H\) is bipancyclic, it has a Hamiltonian cycle and so has a Hamiltonian path. Hence, by Lemma 2, \(H \Box 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= 16k+2\) with \(4 \leq k \leq 2^{n-4}-1\)
\((ii)\) \(l= 16k+6\) with \(3 \leq k \leq 2^{n-4}-1.\)
\((iii)\) \(l= 16k+10\) with \(3 \leq k \leq 2^{n-4}-1.\)
\((iv)\) \(l= 16k+14\) with \(3 \leq k \leq 2^{n-4}-1.\)
Case (i). \(l = 16k + 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} \Box Q_3.\) By Lemma 5, \(Q_{n-3}\) contains a cycle \(C\) of length \(2k\) 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_0a_7, a_1a_6, a_2a_5\) and \(a_3a_4\) are edges of \(Q_3.\) Then \(C\Box 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 \colon i= 0, 7\}\) and \(E(L_1) = \{g_ix_i,g_iy_i, g_iz_i, g_iw_i\colon i= 0, 7 \} \cup \{g_0g_7\}.\) We define a graph \(H_1\) from \(C \Box Q_3\) and \(L_1\) as follows. \[H_1= (C \Box Q_3) \cup L_1- \{x_0x_7, y_0y_7, z_0z_7, w_0w_7\}~~~~ \rm{ (see~ Figure ~4).}\] Clearly, \(H_1\) is a 5-regular subgraph of \(Q_n\) on \(16k+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 \(2k\) 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 \(xu,\) \(uy,\) \(yv\) are edges of \(C.\) Let \[H = C \Box Q_3.\] Then \(H\) is a 5-regular subgraph of \(Q_n\) on \(16k\) 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^i_{n-3}\) corresponding to \(g, h, x, y, z, u, v, w,\) respectively.
Case (ii). Suppose \(l = 16k+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 \colon i = 0,1,2,5,6,7\}\) and edge set \[\{g_ix_i, g_iy_i, g_iz_i \colon i= 0,1,2,5,6,7 \}\\ \cup \{ g_0g_1, g_1g_2, g_2g_5, g_5g_6, g_6g_7, g_7g_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_0x_1, y_0y_1, z_0z_1, x_2x_5, y_2y_5, z_2z_5, x_6x_7, y_6y_7, z_6z_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.
Case (iii). \(l = 16k+10\) with \(3 \leq k \leq 2^{n-4}-1.\)
Consider the three edge sets: \(F_1=\{ g_0g_1, g_1g_2, g_2g_5, g_5g_6, g_6g_7, g_7g_0\},\) \(F_2 = \{ h_2h_3, h_3h_4, h_4h_5,h_5h_2\},\) and \[F_3 = \{x_0x_7, y_0y_7, z_0z_7, x_1x_2, y_1y_2, z_1z_2,\\ x_5x_6, y_5y_6, z_5z_6, u_2u_3, v_2v_3, w_2w_3, u_4u_5, v_4v_5, w_4w_5\}.\]
Let \(L_3\) be the subgraph of \(Q_n\) with vertex set
\(\{ g_i, x_i, y_i, z_i \colon i=
0,1,2,5,6,7\} \cup \{h_j, u_j, v_j, w_j \colon j= 2,3,4,5\}\)
and edge set \[\{ g_ix_i, g_iy_i, g_iz_i
\colon i= 0,1,2,5,6,7 \} \cup \{h_ju_j, h_jv_j, h_jw_j \colon 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 \(16k +
10\) vertices.
Case (iv). \(l = 16k + 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_0g_1, g_1g_2, g_2g_3, g_3g_4, g_4g_5, g_5g_6, g_6g_7, g_7g_0 \};\] \[M_2 = \{h_0h_1, h_1h_2, h_2h_5, h_5h_6, h_6h_7, h_7h_0\} ;\] \[M_3 = \{ u_0u_7, v_0v_7, w_0w_7, u_1u_6, v_1v_6, w_1w_6 , u_2u_5, v_2v_5, w_2w_5\}\] and \[M_4 = \{ x_0x_1, y_0y_1, z_0z_1, x_2x_3, y_2y_3, z_2z_3, x_4x_5, y_4y_5, z_4z_5, x_6x_7, y_6y_7, z_6z_7\}.\] Let \(L_4\) be the subgraph of \(Q_n\) having vertex set \(\{g_i, x_i, y_i, z_i \colon i = 0,1, \dots,7\} \cup \{h_j, u_j, v_j, w_j \colon j = 0,1,2,5,6,7 \}\) and edge set \(\{ g_ix_i, g_iy_i, g_iz_i \colon i = 0,1, \dots,7 \} \cup \{h_ju_j, h_jv_j, h_jw_j \colon 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 \(16k + 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.
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 \(uv_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 \(2k\) 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 \(uu_1, uu_2, \dots, uu_r.\) Let \(H\) be the graph obtained from the graph \(G' \Box 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' \Box 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_1v_1, u_2v_2, \dots, u_rv_r\}.\) Then \(H = (G' \Box K_2) – M.\) Since \(G'\) has at least \(2k+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. ◻
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\Box 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 \Box 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 \(\delta(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).\) ◻
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 \(xy\) and \(L\) be a ladder on \(n\) vertices containing an end edge \(x'y'.\) Then the graph \(C\cup L \cup \{xx', yy'\}\) has cycles of all even lengths from \(m+2\) to \(m+n\) (see Figure 10).
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 \(2k\)-cycle \(C.\) Let \(E_{ij}\) 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 \Box 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 \(16k = |V(W)|.\) Let \(C^i= <v_1^i, v_2^i, \dots v_{2k}^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} \Box 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_0a_3, a_1a_6, a_2a_5\) and \(a_4a_7.\) Furthermore, \(C\) is a \(2k\)-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_{ij}\) be the matching between cycles \(C^i\) and \(C^j\) in \(Q_n\) corresponding to the edge \(a_ia_j\) of \(Q_3.\) For each \(i,\) label the vertices of \(C^i\) by \(v^i_1, v^i_2, \dots, v^i_{2k}\) so that \(C^i =< v^i_1, v^i_2, v^i_3, v^i_4, \dots, v^i_p, \dots, v^i_q, \dots, v^i_{2k}, v^i_1>\) and \(v^i_1, v^i_3, v^i_p\) are the neighbours of the vertex \(g_i,\) and \(v^i_2, v^i_4, v^i_q\) are the neighbours of the vertex \(h_i\) for some \(p, q\) with \(4 < p, q \leq 2k\) and \(p \neq q.\) Hence the neighbours \(x_i, y_i, z_i\) of \(g_i\) on \(C^i\) are relabeled as \(v^i_1, v^i_3, v^i_p,\) respectively. Similarly, the vertices \(u_i, v_i, w_i\) are relabeled as \(v^i_2, v^i_4, v^i_q,\) 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 \Box Z,\) where \(Z\) is an 8-cycle. By Lemma 2, it contains cycles of every even length from 4 to \(16k.\) A cycle \(Z\) of length \(16k+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 \(16k+4\) while \(Z''=(Z'-\{g_0, g_7\})\cup \{v_1^0 v_1^7 \}\) is a cycle of length \(16k+2\) in \(H_2.\) Thus \(H_2\) is bipancyclic. ◻
.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 \(12k\) 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 \Box Z,\) where \(Z\) is a 6-cycle. Hence \(W\) contain cycles of all even lengths from \(4\) to \(12k.\) Therefore these cycles are also contained in \(H_3.\) Let \(L\) be the ladder on \(4k\) vertices defined as \[L = (C^2 – v^2_1v^2_2) \cup ( C^5 – v^5_1v^5_2) \cup \{ v^2_iv^5_i \colon i=1,2, \dots, 2k\}.\] Note that \(W\) has a Hamiltonian cycle \(Z_1 = < v^1_2, v^1_3, \dots,v^1_{2k}, v^1_1, v^0_1, v^0_{2k}, v^0_{2k-1},\dots, v^0_2, v^3_2, \dots, v^3_{2k},v^3_1, v^4_1, v^4_{2k},\\ \dots, v^4_2, v^7_2, \dots, v^7_{2k}, v^7_1, v^6_1, v^6_{2k},\dots, v^6_2,v^1_2>.\) Then the subgraph \(Z_1\cup L\cup \{v^2_2 v^1_2, v^5_2 v^6_2\}\) of \(H_3\) has \(16k\) vertices. By Lemma 14, it has cycles of every even length from \(12k + 2\) to \(16k.\) Let \(Z_2\) and \(Z_3\) be the cycles of length \(16k+6\) and \(16k+10\) as shown in Figure 13(a) and 13(b), respectively. Then \(Z_2'=(Z_2-\{g_0, g_1\})\cup \{v^0_1v^1_1\}\) is a cycle of length \((16k+4)\) whereas \((Z_2'-\{g_6, g_7\})\cup \{ v^6_1 v^7_1\}\) is a \((16k+2)\)-cycle in \(H_3.\) Finally, \((Z_3- \{h_3, h_4\})\cup \{v^3_2 v^4_2, h_2h_5\}\) is a cycle of length \(16k+8\) in \(H_3.\) Thus \(H_3\) is bipancyclic. ◻
Lemma 18. The graph \(H_4\) is bipancyclic.
Proof. Recall that \(H_4\)
has \(16k + 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
\Box 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 \(8k.\) Consider the Hamiltonian cycle \(Z_1\) of \(W,\) where
\(Z_1 = <v^0_2, v^0_3, \cdots,
v^0_{2k},v^0_1, v^3_1, v^3_{2k}, v^3_{2k-1}, \cdots,v^3_{k+2},
v^4_{k+2}, v^4_{k+3}, \cdots, v^4_{2k}, v^4_1, v^7_1, v^7_{2k},
v^7_{2k-1},\cdots, v^7_2,v^4_2, v^4_3, \cdots,\\v^4_{k+1},v^3_{k+1},
v^3_{k},\cdots, v^3_2,v^0_2>\). We get two paths \(P\) and \(Q\) each of length \(4k\) from \(C^1\cup C^6\) and \(C^2\cup C^5,\) respectively as follows.
\[P= <v^1_2, v^1_3, \dots, v^1_{2k},
v^1_1, v^6_1,v^6_{2k}, v^6_{2k-1}, \dots, v^6_2>,\] \[Q= <v^2_2, v^2_3, \dots,v^2_{2k}, v^2_1,
v^5_1,v^5_{2k}, v^5_{2k-1}, \dots, v^5_2>.\] Then \[L_1 = P \cup Q \cup (\{v^1_i v^2_i, v^5_i v^6_i
\colon i = 1, 2,\dots, 2k\})\] is a ladder on \(8k\) vertices. Hence, by Lemma 14,
\(Z_1\cup L_1\cup\{v^0_2 v^1_2, v^2_2
v^3_2\}\) is a subgraph of \(H_4\) on \(16k\) vertices contains cycle of length
\(p\) for every even integer \(p\) with \(8k + 2
\leq p \leq 16k.\)
Let \(Z_2\) and \(Z_3\) be the cycles in \(H_4\) of length \(16k+8\) and \(16k+14\) as shown in Figures 14(a) and 14(b), respectively. If \(Z'_2=(Z_2-\{g_5, g_6\})\cup \{v^5_1 v^6_1\};\) \(Z''_2=(Z'_2-\{g_3, g_4\})\cup \{v^3_1, v^4_1\}\) and \(Z'''_2=(Z''_2-\{g_1, g_2\})\cup \{v^1_1, v^2_1\},\) then \(Z_2',\) \(Z_2''\) and \(Z_2'''\) are cycles of lengths \(16k +6,\) \(16k + 4\) and \(16k + 2,\) respectively. Finally, \(Z'_3=(Z_3-\{h_5, h_6\})\cup \{v^5_2 v^6_2\}\) and \(Z''_3=(Z'_3-\{h_1, h_2\})\cup \{v^1_2 v^2_2\}\) are cycles of lengths \(16k + 12\) and \(16k + 10,\) respectively. Hence \(H_4\) is bipancyclic. ◻
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\ge 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.\)
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.
The authors declare no conflict of interest