No label defined (Q4529441)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1743965
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1743965 |
Statements
18 March 2003
0 references
Hamiltonian graph
0 references
hypercube
0 references
0.7959209084510803
0 references
Consider the \(n\)-dimensional hypercube \(Q_n\). The vertices are represented as subsets of \(\{1,\dots,n\}\) and two subsets are adjacent if and only if their symmetric difference has exactly one element. For \(n=2k+1\), the authors consider two subgraphs of \(Q_n\). By deleting the two vertices \(\emptyset\) and \(\{1,\dots,n\}\), we get the subgraph \(R_n\). Adapting the proof that \(Q_n\) is Hamiltonian by \textit{F. T. Leighton} [Introduction to parallel algorithms and architecutres: arrays, trees, hypercubs (Morgan Kaufmann publishers, San Mateo, CA) (1992; Zbl 0743.68007)], the authors prove that \(R_n\) is Hamiltonian. Secondly, the subgraph \(H_n\) is induced by those vertices which have (in their subset representation) \(k\) or \(k+1\) elements. The authors show (partly using heavy computations) that \(H_5\) has exactly \(48\) oriented Hamilton cycles and \(H_7\) has at least \(2112\) oriented Hamilton cycles. Furthermore, Hamilton cycles for \(H_9\) and \(H_{11}\) are given.
0 references