The Kneser Graph $K(n,k)$ has as vertices all $k$-subsets of $\{1,\ldots,n\}$ and edges connecting two vertices if they are disjoint. The $s$-stable Kneser Graph $K_{s-\text{stab}}(n, k)$ is obtained from the Kneser graph by deleting vertices with elements at cyclic distance less than $s$. In this article, we show that connected $s$-Stable Kneser graphs are Hamiltonian.
@article{10_37236_12739,
author = {Agustina V. Ledezma and Adri\'an Pastine},
title = {\(s\)-stable {Kneser} graphs are {Hamiltonian}},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {3},
doi = {10.37236/12739},
zbl = {8097661},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12739/}
}
TY - JOUR
AU - Agustina V. Ledezma
AU - Adrián Pastine
TI - \(s\)-stable Kneser graphs are Hamiltonian
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/12739/
DO - 10.37236/12739
ID - 10_37236_12739
ER -
%0 Journal Article
%A Agustina V. Ledezma
%A Adrián Pastine
%T \(s\)-stable Kneser graphs are Hamiltonian
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/12739/
%R 10.37236/12739
%F 10_37236_12739
Agustina V. Ledezma; Adrián Pastine. \(s\)-stable Kneser graphs are Hamiltonian. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/12739
