Hamiltonicidad de Grafos Estables de Kneser

AGUSTINA VICTORIA LEDEZMA; ADRIÁN PASTINE

Córdoba

Encuentro; Segundo Encuentro Argentino de Cuerpos Finitos y Temas Afines.; 2019

El grafo de Kneser KG(n,k) tiene como vértices los subconjuntos de cardinalidad k de el conjunto {1,?,n}, y como aristas {A,B} si A y B son disjuntos. El subgrafo de Kneser s-estable, KGs−stab(n,k) se obtiene al eliminar los vértices con elementos cuya distancia cíclica sea menor o igual a s. Muchas propiedades de los grafos estables de Kneser han sido estudiadas en los últimos años, por ejemplo su número cromático, número de independencia, y grupo de automorfismos. En este trabajo estudiaremos la existencia de ciclos hamiltonianos en los grafos s-estables de Kneser, es decir la existencia de un ciclo que pase por todos los vértices del grafo.