Directed Hamiltonicity in Generalized Kneser Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911723910332416 |
|---|---|
| author | Mehry, Shahram |
| author_facet | Mehry, Shahram |
| contents | We prove that the canonical orientation of the generalized Kneser graph $KG(n,k,s)$ contains a directed Hamiltonian cycle for all integers $s \geq 3$ and $n>sk$. Furthermore, we establish that the dichromatic number of this oriented graph is exactly $k$. As a special case, our results apply to the $s$-stable Kneser graphs $K_{s\text{-stab}}(n,k)$, resolving their directed Hamiltonicity and dichromatic number. Our proof adapts the class graph framework of Ledezma and Pastine to the directed setting, leveraging cyclic rotations and friend class adjacencies to construct a single directed cycle spanning all vertices. This work provides a unified and strengthened perspective on the Hamiltonian properties of Kneser-type graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12553 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Directed Hamiltonicity in Generalized Kneser Graphs Mehry, Shahram Combinatorics Commutative Algebra We prove that the canonical orientation of the generalized Kneser graph $KG(n,k,s)$ contains a directed Hamiltonian cycle for all integers $s \geq 3$ and $n>sk$. Furthermore, we establish that the dichromatic number of this oriented graph is exactly $k$. As a special case, our results apply to the $s$-stable Kneser graphs $K_{s\text{-stab}}(n,k)$, resolving their directed Hamiltonicity and dichromatic number. Our proof adapts the class graph framework of Ledezma and Pastine to the directed setting, leveraging cyclic rotations and friend class adjacencies to construct a single directed cycle spanning all vertices. This work provides a unified and strengthened perspective on the Hamiltonian properties of Kneser-type graphs. |
| title | Directed Hamiltonicity in Generalized Kneser Graphs |
| topic | Combinatorics Commutative Algebra |
| url | https://arxiv.org/abs/2511.12553 |