Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1043.68081
Tsai, Chang-Hsiung; Tan, Jimmy J. M.; Liang, Tyne; Hsu, Lih-Hsing
Fault-tolerant Hamiltonian laceability of hypercubes. (English)
[J] Inf. Process. Lett. 83, No. 6, 301-306 (2002). ISSN 0020-0190

Summary: It is known that every hypercube $Q_{n}$ is a bipartite graph. Assume that $n\geqslant2$ and $F$ is a subset of edges with $\vert F\vert <n-2$. We prove that there exists a Hamiltonian path in $Q_{n}-F$ between any two vertices of different partite sets. Moreover, there exists a path of length $2^{n}-2$ between any two vertices of the same partite set. Assume that $n\geqslant3$ and $F$ is a subset of edges with $\vert F\vert <n-3$. We prove that there exists a Hamiltonian path in $Q_{n}-{v}-F$ between any two vertices in the partite set without $v.$ Furthermore, all bounds are tight.

MSC 2000:: *68R10 Graph theory in connection with computer science
05C45 Eulerian and Hamiltonian graphs
68M15 Reliability and testing of computer systems

Keywords: Hamiltonian laceable; Hypercube; Fault tolerance

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]