Embedding cycles into hypercubes with prescribe vertices in the specific order

Lih Hsing Hsu; Cheng Kuan Lin; Jimmy J.M. Tan; Chun Nan Hung

doi:10.1109/CSE.2011.68

Embedding cycles into hypercubes with prescribe vertices in the specific order

Lih Hsing Hsu^*, Cheng Kuan Lin, Jimmy J.M. Tan, Chun Nan Hung

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

In this paper, we are interesting in a new cycle embedding problem. Let x₁, x₂,....x_k be any k-vertices. Can we find a cycle C in the hypercube Q_n such 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(x₁, x₂) + h(x₂, x₃) + h(x₃, x₄) + h(x₄, x₁) ≤ l ≤ 2ⁿ. For n ≥ 5, we will prove that there exists a cycle C in Q _n of length l such that C traverses these 4 vertices in the specific order except for the case that l ∈ {6,8} when 〈x₁, x ₃, x₂, x₄, x₁〉 forms a cycle of length 4.

Original language	English
Title of host publication	Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011
Pages	351-357
Number of pages	7
DOIs	https://doi.org/10.1109/CSE.2011.68
State	Published - 2011
Event	14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011, the 11th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011, and the 10th IEEE Int. Conf. on Ubiquitous Computing and Communications, IUCC 2011 - Dalian, Liaoning, China Duration: 24 Aug 2011 → 26 Aug 2011

Publication series

Name	Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011

Conference

Conference	14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011, the 11th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011, and the 10th IEEE Int. Conf. on Ubiquitous Computing and Communications, IUCC 2011
Country/Territory	China
City	Dalian, Liaoning
Period	24/08/11 → 26/08/11

Keywords

Hamiltonian
bipanconnected
bipancyclic
hypercube
ordered bipancyclic

Access to Document

10.1109/CSE.2011.68

Cite this

Hsu, L. H., Lin, C. K., Tan, J. J. M., & Hung, C. N. (2011). Embedding cycles into hypercubes with prescribe vertices in the specific order. In Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011 (pp. 351-357). Article 6062898 (Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011). https://doi.org/10.1109/CSE.2011.68

Hsu, Lih Hsing ; Lin, Cheng Kuan ; Tan, Jimmy J.M. et al. / Embedding cycles into hypercubes with prescribe vertices in the specific order. Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011. 2011. pp. 351-357 (Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011).

@inproceedings{66e98a791165479e948dc4856c69f692,

title = "Embedding cycles into hypercubes with prescribe vertices in the specific order",

abstract = "In this paper, we are interesting in a new cycle embedding problem. Let x1, x2,....xk be any k-vertices. Can we find a cycle C in the hypercube Qn such 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) ≤ l ≤ 2n. For n ≥ 5, we will prove that there exists a cycle C in Q n of length l such that C traverses these 4 vertices in the specific order except for the case that l ∈ {6,8} when 〈x1, x 3, x2, x4, x1〉 forms a cycle of length 4.",

keywords = "Hamiltonian, bipanconnected, bipancyclic, hypercube, ordered bipancyclic",

author = "Hsu, {Lih Hsing} and Lin, {Cheng Kuan} and Tan, {Jimmy J.M.} and Hung, {Chun Nan}",

year = "2011",

doi = "10.1109/CSE.2011.68",

language = "English",

isbn = "9780769544779",

series = "Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011",

pages = "351--357",

booktitle = "Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011",

note = "14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011, the 11th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011, and the 10th IEEE Int. Conf. on Ubiquitous Computing and Communications, IUCC 2011 ; Conference date: 24-08-2011 Through 26-08-2011",

}

Hsu, LH, Lin, CK, Tan, JJM & Hung, CN 2011, Embedding cycles into hypercubes with prescribe vertices in the specific order. in Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011., 6062898, Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011, pp. 351-357, 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011, the 11th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011, and the 10th IEEE Int. Conf. on Ubiquitous Computing and Communications, IUCC 2011, Dalian, Liaoning, China, 24/08/11. https://doi.org/10.1109/CSE.2011.68

Embedding cycles into hypercubes with prescribe vertices in the specific order. / Hsu, Lih Hsing; Lin, Cheng Kuan; Tan, Jimmy J.M. et al.
Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011. 2011. p. 351-357 6062898 (Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Embedding cycles into hypercubes with prescribe vertices in the specific order

AU - Hsu, Lih Hsing

AU - Lin, Cheng Kuan

AU - Tan, Jimmy J.M.

AU - Hung, Chun Nan

PY - 2011

Y1 - 2011

N2 - In this paper, we are interesting in a new cycle embedding problem. Let x1, x2,....xk be any k-vertices. Can we find a cycle C in the hypercube Qn such 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) ≤ l ≤ 2n. For n ≥ 5, we will prove that there exists a cycle C in Q n of length l such that C traverses these 4 vertices in the specific order except for the case that l ∈ {6,8} when 〈x1, x 3, x2, x4, x1〉 forms a cycle of length 4.

AB - In this paper, we are interesting in a new cycle embedding problem. Let x1, x2,....xk be any k-vertices. Can we find a cycle C in the hypercube Qn such 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) ≤ l ≤ 2n. For n ≥ 5, we will prove that there exists a cycle C in Q n of length l such that C traverses these 4 vertices in the specific order except for the case that l ∈ {6,8} when 〈x1, x 3, x2, x4, x1〉 forms a cycle of length 4.

KW - Hamiltonian

KW - bipanconnected

KW - bipancyclic

KW - hypercube

KW - ordered bipancyclic

UR - http://www.scopus.com/inward/record.url?scp=81455131954&partnerID=8YFLogxK

U2 - 10.1109/CSE.2011.68

DO - 10.1109/CSE.2011.68

M3 - Conference contribution

AN - SCOPUS:81455131954

SN - 9780769544779

T3 - Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011

SP - 351

EP - 357

BT - Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011

T2 - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011, the 11th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011, and the 10th IEEE Int. Conf. on Ubiquitous Computing and Communications, IUCC 2011

Y2 - 24 August 2011 through 26 August 2011

ER -

Hsu LH, Lin CK, Tan JJM, Hung CN. Embedding cycles into hypercubes with prescribe vertices in the specific order. In Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011. 2011. p. 351-357. 6062898. (Proc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp. on Pervasive Systems, Algorithms, and Networks, I-SPA 2011 and 10th IEEE Int. Conf. on IUCC 2011). doi: 10.1109/CSE.2011.68

Embedding cycles into hypercubes with prescribe vertices in the specific order

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this