Condiciones tipo-Pósa para potencias de ciclos hamiltonianos.

Abstract: Un resultado clásico de Pósa dice que un grafo en n vértices es hamiltoniano si su secuencia de grados d_1 \leq \dotsb \leq d_n cumple d_i >= i+1, para todo i \leq n/2. Acá, generalizamos este resultado a potencias de ciclos. Una k-potencia de un ciclo hamiltoniano es el grafo que se obtiene de un ciclo al unir los vértices a distancia a lo más k. Demostramos que si G tiene n vértices v_1, …, v_n y se cumple d(v_i) >= (k-2)n/k + i + o(n) para todo i <= n/k, entonces el grafo tiene la (k-1)-potencia de un ciclo hamiltoniano. Esta condición es esencialmente la mejor posible, y el término o(n) no se puede reemplazar por o(n^{1/2}). Esto resuelve una conjetura de Staden y Treglown y responde una pregunta de Balogh, Kostochka y Treglown. Trabajo en conjunto con Richard Lang.

Posted on Sep 21, 2020 in Seminario de Grafos, Seminars