Ubicando pares de vértices en ciclos hamiltonianos.
Loading...
Date
2026
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
En esta tesis daremos una demostración a la conjetura de Enomoto para grafos de tamaño lo suficientemente grande. Enomoto conjeturó que si un grafo con n vértices tiene grado mínimo al menos n/2 + 1, entonces para todo par de vértices x, y existe un ciclo hamiltoniano C tal que la distancia de x a y en el ciclo C es exactamente ⌊n/2⌋. Nuestra demostración no utiliza el Lema de Regularidad de Szemerédi, por lo que el valor mínimo de n para el cual nuestro resultado es cierto es considerablemente menor al conocido hasta la fecha. Nuestra principal herramienta es la Tricotomía de los grafos de Dirac, además de distintos resultados que aseguran la existencia de caminos hamiltonianos entre cualquier par de vértices, y resultados relacionados a grafos expansores robustos.
Description
Tesis presentada para optar al grado de Magíster en Ciencias de la Computación.
Keywords
Grafos, Vértices, Ciclos hamiltonianos