Strongly hyper-hamiltonian-laceability of hypercubes

Sun-Yuan Hsieh, Zhe Nan Guo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Suppose that G = (V0 U V1, E) is a bipartite graph with two partite sets V0 and V1 of equal size. Let x and y be two arbitrary distinct vertices and let w be another vertex different from x and y. G is said to be strongly hyper-Hamiltonian-laceable if G - w satisfies the following three properties. P1: There is a (|V0| + |V 1| - 2)-length path between x and y, where x and y are in the same partite set and w is In the other partite set; P2: There is a (|V0| + |V1| - 3)-length path between x and y, where z and y are in different partite sets and w is in any partite set; P3: There is a (|V 0| + |V1| - 4)-length path between x and y, where x, y, w are in the same partite set. Let Fe be the set of faulty edges of an n-dimensional hypercube Qn. In this paper, we show that Qn - Fe (the graph obtained by deleting all edges of Fe from Qn) remains strongly hyper-Hamiltonian-laceable when |Fe| ≤ n - 3.

Original languageEnglish
Title of host publicationProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
EditorsH.R. Arabnia
Pages1081-1083
Number of pages3
Volume3
Publication statusPublished - 2004
EventProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04 - Las Vegas, NV, United States
Duration: 2004 Jun 212004 Jun 24

Other

OtherProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
CountryUnited States
CityLas Vegas, NV
Period04-06-2104-06-24

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Strongly hyper-hamiltonian-laceability of hypercubes'. Together they form a unique fingerprint.

  • Cite this

    Hsieh, S-Y., & Guo, Z. N. (2004). Strongly hyper-hamiltonian-laceability of hypercubes. In H. R. Arabnia (Ed.), Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04 (Vol. 3, pp. 1081-1083)