scientific article; zbMATH DE number 1743965

From MaRDI portal
Publication:4529441





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.











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)