Embedding geodesic and balanced cycles into hypercubes
Pao-Lien Lai, Chang‐Hsiung Tsai, Hong-Chun Hsu · 2009
Abstract: A graph G is said to be pancyclic if it contains cycles of all lengths from 4 to |V (G) | in G. For any two vertices u, v ∈ V (G), a cycle is called a geodesic cycle with u and v if a shortest path joining u and v lies on the cycle. Let G be a bipartite graph. For any two vertices u and v in G, a cycle C is called a balanced cycle between u and v if dC(u, v) = max{dC(x, y) | dG(x, u) and dG(y, v) are even, resp. for all x, y ∈ V (G)}. A bipartite graph G is geodesic bipancyclic (respectively, balanced bipancyclic) if for each pair of vertices u, v ∈ V (G), it contains a geodesic cycle (respectively, balanced cycle) of every even length of k satisfying max{2dG(u, v), 4} ≤ k ≤ |V (G) | between u and v. In this paper, we prove that Qn is geodesic bipancyclic and balanced bipancyclic if n ≥ 2. Key–Words: Hypercube; Interconnection networks; Edge-bipancyclic; Geodesic bipancyclic; Balanced bipan-cyclic