Fault-free pairwise independent Hamiltonian paths on faulty hypercubes

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

Abstract

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P1= 〈u1, u2, . . ., un〉 and P2 = 〈v1, v 2, . . ., vn〉 of G are said to be independent if u1 = v1, un = vn, and ui ≠ vi for all 1 < i < n. A set of Hamiltonian paths {P 1, P2, . . ., Pk} of G are mutually independent if any two different Hamiltonian paths in the set are independent. It is well-known that an n-dimensional hypercube Qn is bipartite with two partite sets of equal-size. Let F be the set of faulty edges of Qn such that |F| ≤ n -2. In this paper, we show that Qn - F contains (n - |F| - 1)-mutually independent Hamiltonian paths between any two vertices from different partite sets, where n ≥ 2.

Original languageEnglish
Title of host publicationAdvances in Computer Systems Architecture - 11th Asia-Pacific Conference, ACSAC 2006, Proceedings
PublisherSpringer Verlag
Pages373-379
Number of pages7
ISBN (Print)3540400567, 9783540400561
DOIs
Publication statusPublished - 2006
Event11th Asia-Pacific Conference on Advances in Computer Systems Architecture, ACSAC 2006 - Shanghai, China
Duration: 2006 Sep 62006 Sep 8

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4186 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th Asia-Pacific Conference on Advances in Computer Systems Architecture, ACSAC 2006
CountryChina
CityShanghai
Period06-09-0606-09-08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fault-free pairwise independent Hamiltonian paths on faulty hypercubes'. Together they form a unique fingerprint.

Cite this