Sobre grafos casi estables de Kneser

AGUSTINA VICTORIA LEDEZMA; ADRIÁN PASTINE

Neuquén

Congreso; Reunión Anual de la Unión Matemática Argentina 2022; 2022

Unión Matemática Argentina

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 importantesen lo que respecta a grafos de Kneser es el de Hamiltonicidad,es decir, si todo grafo de Kneser conexo tiene un camino o cicloque pase por todos los vértices. Como estrategia para la búsqueda de esta estructura, nos enfocamos en encontrarcaminos o ciclos en subgrafos de $Kg(n,k)$, con la ideade luego conectarlos para obtener un camino o ciclo de Hamilton en el grafo.Para definir los subgrafos en vez de trabajar con un conjuntobase 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 elementosconsecutivos 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.