Hamiltonian paths in the permutation digraphs $P(n,n-2)$
For $1\leq k<n$, let $P(n,k)$ be the directed overlap graph whose vertices are the $k$-permutations of $[n]$ and whose arcs are the $(k+1)$-permutations. Isaak proved that $P(n,n-2)$ has no directed Hamiltonian cycle for $n\geq4$ and asked whether it nevertheless has a directed Hamiltonian path. We answer this question affirmatively by showing that $P(n,n-2)$ has a Hamiltonian path.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.15287
curl -X POST /api/v1/records/arxiv/2608.15287/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.15287/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'