Directed Hamiltonicity in Generalized Kneser Graphs

2025/11/16 by Shahram Mehry, Mehry, Shahram
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2511.12553

openalex publication_date 2025/11/16 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28

Abstract

We prove that the canonical orientation of the generalized Kneser graph KG(n,k,s) contains a directed Hamiltonian cycle for all integers s ≥ 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-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.

Related

• s-Stable Kneser Graph are Hamiltonian
• Kneser graphs are Hamiltonian
• Short proof that Kneser graphs are Hamiltonian for n≥ 4k
• Hamiltonicity of Schrijver graphs and stable Kneser graphs
• Arbitrary Orientations Of Hamilton Cycles In Oriented Graphs