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
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

Publication series

NameProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
Volume3

Other

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

All Science Journal Classification (ASJC) codes

  • General Engineering

Fingerprint

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

Cite this