On the existence of Hamiltonian paths in the cover graph of \(M\)(\(n\)) (Q1868855): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:37, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the existence of Hamiltonian paths in the cover graph of \(M\)(\(n\)) |
scientific article |
Statements
On the existence of Hamiltonian paths in the cover graph of \(M\)(\(n\)) (English)
0 references
28 April 2003
0 references
The poset \(M(n)\) has as its elements the \(n\)-tuples of integers \({\mathbf a}=(a_1,a_2,\ldots,a_n)\) satisfying \(0=a_1=\ldots =a_j<a_{j+1}<\ldots <a_n\leq n\) for some \(j\geq 0\). The order relation is defined by \({\mathbf a}\leq{\mathbf b}\) if and only if \(a_i\leq b_i\) for \(1\leq i\leq n\). The authors show that the cover graph \(M(n)\) has a Hamiltonian path if and only if \({n+1 \choose 2}\) is odd and \(n\neq 5\).
0 references
Hamiltonian path
0 references
Gray code
0 references
cover graph
0 references
augmentation poset
0 references