Embedding Cycles into Hypercubes with Prescribe Vertices in the Specific Order
Lih‐Hsing Hsu, Cheng‐Kuan Lin, Jimmy J.M. Tan, Chun‐Nan Hung · 2011
In this paper, we are interesting in a new cycle embedding problem. Let x1, x2,..., xkbe any k-vertices. Can we find a cycle C in the hypercube Qnsuch that C traverses these k vertices in the specific order? In this paper, we study k = 4. Let l be any even integer satisfying h(x1, x2) + h(x2,x3) + h(x3, x4) + h(x4, x1) ≤ I ≤ 2n. For n ≥ 5, we will prove that there exists a cycle C in Qnof length I such that C traverses these 4 vertices in the specific order except for the case that I ∈ {6,8} when (x1, x3, x2, x4, x1) forms a cycle of length 4.