UMA 2022
El grafo de Kneser $Kg(n,k)$ tiene como vértices los subconjuntos de tamaño $k$ de un conjunto base de tamaño $n$. Uno de los problemas abiertos más importantes en lo que respecta a grafos de Kneser es el de Hamiltonicidad, es decir, si todo grafo de Kneser conexo tiene un camino o ciclo que pase por todos los vértices. Como estrategia para la búsqueda de esta estructura, nos enfocamos en encontrar caminos o ciclos en subgrafos de $Kg(n,k)$, con la idea de luego conectarlos para obtener un camino o ciclo de Hamilton en el grafo. Para definir los subgrafos en vez de trabajar con un conjunto base cualquiera, tomamos el conjunto $\{1,2,\ldots,n\}$, y definimos subgrafos poniendo restricciones en los subconjuntos de tamaño $k$. Así, por ejemplo, el grafo estable de $Kg(n,k)$ se obtiene al prohibir que el conjunto tenga elementos consecutivos de manera cíclica. Es decir que un vértice no puede contener subconjuntos de la forma $\{i,i+1\}$ o $\{1,n\}$. En un trabajo anterior demostramos que los grafos estables conexos tienen un ciclo de Hamilton. En este trabajo nos concentramos en buscar caminos y ciclos en los grafos casi estables, cuyos vértices tienen exactamente un par de elementos cíclicamente consecutivos.
Trabajo en conjunto con: Adrián Pastine (IMASL (CONICET) - UNSL).