scientific article; zbMATH DE number 1743965
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.
- scientific article; zbMATH DE number 790411
- scientific article; zbMATH DE number 1990668
- scientific article; zbMATH DE number 434488
- Hamiltonian Cycles with Prescribed Edges in Hypercubes
- Un nouvel encadrement du nombre de cycle Hamiltoniens du n-cube. (New bounds for the number of Hamiltonian cycles of the n-cube)
- On symmetric subgraphs of the 7-cube: An overview
- Trimming and gluing Gray codes
- Classification of the Hamiltonian cycles in binary hypercubes
- Gray codes and symmetric chains
- On subdivision graphs which are 2-steps Hamiltonian graphs and hereditary non 2-steps Hamiltonian graphs
- Spanning multi-paths in hypercubes
- On the central levels problem
- Regular subgraphs of hypercubes
- scientific article; zbMATH DE number 1990668 (Why is no real title available?)
- scientific article; zbMATH DE number 2322 (Why is no real title available?)
- scientific article; zbMATH DE number 790411 (Why is no real title available?)
- Gray codes and symmetric chains
- On the central levels problem
- On generalized middle-level problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4529441)