# On 3-Regular Bipancyclic Subgraphs of Hypercubes

Authors: Y. M. Borse; S. R. Shaikh
Journal: International Journal of Combinatorics
 (2015)

---

## Abstract

Then-dimensional hypercube Qn is  bipancyclic; that is, it contains a cycle of every even length from 4 to 2n. In this paper, we prove that Qn(n≥3) contains a 3-regular, 3-connected, bipancyclic subgraph with l vertices for every even l from 8 to 2n except 10.


---

## Body

## 1. Introduction

Thecartesian productG1×G2 of two graphs G1 and G2 is a graph with the vertex set V(G1)×V(G2), and any two vertices (u1,u2) and (v1,v2) are adjacent in G1×G2 if and only if either u1=v1 and u2 is adjacent to v2 in G2 or u2=v2 and u1 is adjacent to v1 in G1. A graph G with even number of vertices isbipancyclic if it contains a cycle of every even length from 4 to |V(G)|. ThehypercubeQn of dimension n is a graph obtained by taking cartesian product of the complete graph K2 on two vertices with itself n times; that is, Qn=K2×K2×⋯×K2 (n times). The hypercube Qn is an n-regular, n-connected, bipartite, and bipancyclic graph with 2n vertices. It is one of the most popular interconnection network topologies [1]. The bipancyclicity of a given network is an important factor in determining whether the network topology can simulate rings of various lengths. The connectivity of a network gives the minimum cost to disrupt the network. Regular subgraphs, bipancyclicity, and connectivity properties of hypercubes are well studied in the literature [2–6].SinceQn (n≥2) is bipancyclic, it contains a 2-regular, 2-connected subgraph (cycle) with l vertices for every even integer l from 4 to 2n. Suppose 3≤k≤n. Mane and Waphare [4] proved that Qn contains a spanning k-regular, k-connected, bipancyclic subgraph. So the natural question arises; what are the other possible orders existing for k-regular, k-connected and bipancyclic subgraphs of Qn? As Qn=Qn-k×Qk, Qk can be regarded as a subgraph of Qn. Hence Qn has a k-regular, k-connected, bipancyclic subgraph with 2k vertices. In this paper, we answer the question for k=3. We prove that Qn (n≥3) contains a 3-regular, 3-connected, and bipancyclic subgraph with l vertices for every even integer l from 8 to 2n except 10.


## 2. Proof

The cartesian product of a nontrivial path with the complete graphK2 is aladder graph. Let F be the graph obtained from a path A1,A2,…,Am (m≥4) by adding one extra edge A1A4. We call the graph F×K2 aladder type graph on 2m vertices (see Figure 1).Figure 1Lemma 1.
A ladder graph is bipancyclic.Proof.
LetL be a ladder graph with 2m vertices. Label the vertices of L by Ai’s and Bi’s so that L is the union of the paths P1=A1,A2,…,Am and P2=B1,B2,…,Bm and the m edges AiBi for i=1,2,…,m. Suppose 2≤l≤m. Let P1′ be the subpath of P1 from A1 to Al and let P2′ be the subpath of P2 from B1 to Bl. Then P1′∪P2′∪{A1B1,AlBl} is a cycle of length 2l in L. Hence L has a cycle of every even length from 4 to |V(L)|.The vertices of the hypercubeQn can be labeled by the binary strings of length n so that two vertices are adjacent in Qn if and only if their binary strings differ in exactly one coordinate. Denote by Qn-1j the subgraph of Qn induced by the set of all vertices of Qn each having first coordinate j for j=0,1. Then Qn-10 and Qn-11 are vertex-disjoint and each of them is isomorphic to Qn-1. We can express Qn as Qn=Qn-10∪Qn-11∪D, where D={XY∣X∈V(Qn-10)andY∈V(Qn-11)}. Note that D is a perfect matching in Qn.Lemma 2.
For everym with 4≤m≤2n-1, there exists a ladder type subgraph in Qn (n≥3) with 2m vertices.Proof.
We first prove thatQn contains a Hamiltonian cycle C with a chord e which forms a 4-cycle with three edges of C. This is obvious for n=3. Suppose n≥4. Write Qn as Qn=Qn-10∪Qn-11∪D. By induction, there exists a Hamiltonian cycle C0 in Qn-10 with a chord e which forms a 4-cycle Z0 with three edges of C0. Let C1 be the corresponding Hamiltonian cycle in Qn-11. Let XY be any edge on C0 which is not on Z0 and let X′Y′ be the corresponding edge on C1. Then XX′ and YY′ belong to D. Let C=(C0-XY)∪(C1-X′Y′)∪{XX′,YY′}. Then C is a Hamiltonian cycle in Qn such that e is its chord which forms the 4-cycle Z0 with three edges of C.
Now, we prove thatQn contains a ladder type graph with 2m vertices. Obviously, Q3 itself is a ladder type graph on 8 vertices. Suppose n≥4. By the above part, Qn-1 contains a Hamiltonian cycle C with a chord e which forms a 4-cycle with three edges of C. Label the vertices of C by Ai’s so that C=A1,A2,A3,…,A2n-1,A1 and e=A1A4. Let F be the subgraph of Qn-1 obtained by taking the union of the subpath A1,A2,A3,…,Am of C and the edge A1A4. Then F×K2 is a ladder type subgraph of Qn-1×K2=Qn with 2m vertices.As a consequence of a result of [7], we get the following lemma.Lemma 3.
LetGi be an ni-regular, ni-connected graph for i=1,2. Then the graph G1×G2 is (n1+n2)-regular, (n1+n2)-connected.It is well known that the hypercubeQn does not contain the complete bipartite graph K2,3 as a subgraph. The following result is the main theorem of this paper.Theorem 4.
Letn be an integer such that n≥3. Then there exists a 3-regular, 3-connected, and bipancyclic subgraph of Qn on l vertices if and only if l is an even integer with 8≤l≤2n and l≠10.Proof.
SupposeQn contains a 3-regular subgraph H with l vertices. By Handshaking Lemma, the sum of the degrees of all vertices of a graph is even. Hence 3l is even. Consequently, l is even. The minimum degree of H is three. Therefore H contains an even cycle. Since H is simple, l≥4. If l=4, then H contains a triangle, a contradiction. Thus l≥6. Suppose l=6. Then H must contain a cycle Z of length four. A vertex of H outside Z has at least two neighbours in Z giving a triangle or a K2,3 in Qn, which is a contradiction. Suppose l=10. 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. Write Qn as Qn=Qn-10∪Qn-11∪D. Then e∈D. Therefore H intersects with both Qn-10 and Qn-11. Let Hj be a component of H∩Qn-1j for j=0,1. Then Hj is a subgraph of Qn-1j with minimum degree two and hence it contains a cycle. As Qn is simple bipartite, Hj has at least four vertices. Since |V(H)|=10, Hj is the only component of H in H∩Qn-1j. We may assume that |V(H0)|≤|V(H1)|. Then |V(H0)|=4 or |V(H0)|=5. Let C0 be an even cycle in H0. Then |C0|=4. If H0 has 5 vertices, then the vertex of H0 which is not on C0 is adjacent to at least two vertices of C0 giving a triangle or a K2,3 in Qn-10, a contradiction. Consequently, H0 has 4 vertices. Thus H0=C0. Let C1 be the cycle in Qn-11 corresponding to C0. Since H is 3-regular, each vertex of C0 has one neighbour in H1 along an edge of D. Therefore all vertices of C1 belong to H1. As H1 has six vertices, it has a vertex X which is not on C1. Then X has no neighbour in H0. Thus X has three neighbours in H1. Therefore X has at least two neighbours in the 4-cycle C1 giving a triangle or a K2,3 in Qn-11, a contradiction. Hence l≠10. Thus l is an even integer with 8≤l≤2n and l≠10.
Now, we construct a 3-regular, 3-connected, bipancyclic subgraph ofQn with l vertices for every even integer l with 8≤l≤2n and l≠10. Suppose l=4m for some integer m with 2≤m≤2n-2. Write Qn as Qn=Qn-1×K2. Since Qn-1 is a bipancyclic graph and l/2 is even, there is a cycle C of length l/2 in Qn-1. By Lemma 3, C×K2 is a 3-regular, 3-connected subgraph of Qn with l vertices. Let e be an edge of C. Then (C-e)×K2 is a ladder graph which spans C×K2. By Lemma 1, C×K2 is bipancyclic.
Supposel=4m+2 with 3≤m≤2n-2-1. Write Qn as Qn=Qn-10∪Qn-11∪D. As 4≤m+1≤2n-2, there exists a ladder type subgraph L1 in Qn-10 on 2m+2 vertices by Lemma 2. Label the vertices of L1 by Ai’s and Bi’s so that A1,A2,…,Am+1 and B1,B2,…,Bm+1 are paths and AiBi is an edge of L1 for i=1,2,…,m+1. Let L2 be the ladder type subgraph of Qn-11 on 2m+2 vertices corresponding to L1. Label the vertices of L2 by A1′,A2′,…,Am+1′ and B1′,B2′,…,Bm+1′, where the vertex Ai′ corresponds to Ai, and the vertex Bi′ corresponds to Bi for every i=1,2,…,m+1. Let L1′ be the graph obtained from L1 by deleting the edges A2B2 and A4B4. Let L2′ be the graph obtained from L2 by deleting two vertices A1′ and B1′. Then L1′ is a subgraph of Qn-10 with 2m+2 vertices and L2′ is a ladder subgraph of Qn-11 with 2m vertices.
LetH=L1′∪L2′∪D2, where D2=A2A2′,B2B2′,Am+1Am+1′,Bm+1Bm+1′⊂D (see Figure 2). Then H is a 3-regular subgraph of Qn with 4m+2=l vertices. We claim that H is bipancyclic and 3-connected.Figure 2Claim 1.
H is bipancyclic.Clearly,C=A1,A2,…,Am+1,Am+1′,Am′,…,A2′,B2′, B3′,…,Bm+1′,Bm+1,Bm,…,B1,A1 is a Hamiltonian cycle in H. By deleting two vertices A2′ and B2′ and then adding the edge A3′B3′ to C, we get a cycle of length 4m in H. Similarly, we obtain a cycle of length 4m-2 in H from C by deleting four vertices A2′,A3′,B2′,B3′ and then adding the edge A4′B4′. Now, by deleting six vertices A1,A2,B1,B2,A2′,B2′ from C adding the edges A3B3 and A3′B3′ gives a cycle of length 4m-4 in H. Suppose m=3. Then H has 4m+2=14 vertices. We get a cycle of length 4 and a cycle of length 6 in the ladder L2′ as, by Lemma 1, it is a bipancyclic graph on six vertices. Thus H contains a cycle of every even length from 4 to 14. Suppose m≥4. Then L1′ has at least 10 vertices. Let L be the ladder in H formed by two paths A5,A6,…,Am+1,Am+1′,Am′,…,A2′ and B5,B6, …,Bm+1,Bm+1′,Bm′,…,B2′ and the matching AiBi and Aj′Bj′ for i=5,6,…,m+1 and j=2,3,…,m+1. By Lemma 1, L is bipancyclic. Hence L contains a cycle of every even length from 4 to |V(L)|=4m-6. Thus H contains a cycle of every even length from 4 to |V(H)|=4m+2=l. Therefore H is bipancyclic.Claim 2.
H is 3-connected.SinceH contains a Hamiltonian cycle, it is 2-connected. It suffices to prove that deletion of any two vertices from H leaves a connected graph. Let S⊂V(H) with |S|=2. We prove that H-S is connected. Let S={X,Y}. Suppose S intersects both V(L1′) and V(L2′). We may assume that X∈V(L1′) and Y∈V(L2′). Being Hamiltonian graphs, both L1′ and L2′ are 2-connected. Hence L1′-X and L2′-Y are connected. There are at least two edges from the set D2 which connects L1′-X to L2′-Y in H-S. Therefore H-S is connected.SupposeS⊂V(L2′). Then S∩V(L1′)=ϕ and {A2′,B2′,Am+1′,Bm+1′}∖S≠ϕ. Obviously, L1′ is connected. Suppose L2′-S is connected. Then it is joined to L1′ through at least two edges from the set D2. This implies that H-S is connected. Suppose L2′-S is not connected. Then one vertex of S belongs the path A2′,A3′,…,Am+1′ and the other vertex belongs to the path B2′,B3′,…,Bm+1′. Let C=A2′,A3′,…,Am+1′,Bm+1′,Bm′,…,B2′,A2′ be a Hamiltonian cycle of L2′. Then C-S has exactly two components, say, T1 and T2 with vertex set V(T1) and V(T2). Note that T1 or T2 may have a single vertex. Therefore L2′-S has two components one with vertex set V(T1) and the other with vertex set V(T2). It is easy to see that Ti contains a vertex from the set {A2′,B2′,Am+1′,Bm+1′}∖S and hence has a neighbour in L1′ along an edge of the set D2 for i=1,2. Consequently, each component of L2′-S has a neighbour in L1′ in the graph H-S. This implies that H-S is connected.SupposeS⊂V(L1′). Then L2′ is connected. Let F={A2,B2,Am+1,Bm+1}∖S. Then F≠ϕ and F⊂V(L1′-S). If each component of L1′-S contains a vertex of the set F, then all the components of L1′-S are connected to L2′ by the edges of the set D2 giving H-S connected. Therefore it suffices to prove that each component of L1′-S contains a vertex of the set F. If L1′-S is connected, then we are done. Suppose L1′-S is not connected. Consider the case when m=3. Then L1′ is the union of the two 4-cycles A1, A2, A3, A4, A1 and B1, B2, B3, B4, B1, and the two edges A1B1, A3B3. Each of the vertices A2, B2, A4, B4 has degree two in L1′. If S∩{A2,B2,A4,B4}≠ϕ, then L1′-S is connected. Therefore S⊂{A1,A3,B1,B3}. Thus S={A1,A3}, {A1,B1}, {A1,B3}, {A3,B1}, {A3,B3} or {B1,B3}. In any case, each component of L1′-S contains a vertex of the set F. Suppose m≥4. Then A1,A2,…,Am+1,Bm+1,Bm,…,B1,A1 is a Hamiltonian cycle in L1′. Therefore L1′-S has only two components. It follows that one component of L1′-S contains a vertex from {A2,B2}∖S and the other component contains a vertex from the set {Am+1,Bm+1}∖S. Hence the vertex set of each component of L1′-S intersects F. Consequently, H-S is connected. Therefore H is 3-connected.Thus, from Claims 1 and 2,H is a 3-regular, 3-connected, bipancyclic subgraph of Qn with l vertices.



---

*Source: 638767-2015-05-05.xml*