Ubicando pares de vértices en ciclos hamiltonianos.
| dc.contributor.advisor | Sanhueza Matamala, Nicolás | es |
| dc.contributor.author | Zúñiga Cavieres, Daniel | es |
| dc.date.accessioned | 2026-01-26T19:01:00Z | |
| dc.date.available | 2026-01-26T19:01:00Z | |
| dc.date.issued | 2026 | |
| dc.description | Tesis presentada para optar al grado de Magíster en Ciencias de la Computación. | es |
| dc.description.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. | es |
| dc.description.campus | Concepción | es |
| dc.description.departamento | Departamento de Informática y Ciencias de la Computación | es |
| dc.description.facultad | Facultad de Ingeniería | es |
| dc.identifier.uri | https://repositorio.udec.cl/handle/11594/13660 | |
| dc.language.iso | es | es |
| dc.publisher | Universidad de Concepción | es |
| dc.rights | CC BY-NC-ND 4.0 DEED Attribution-NonCommercial-NoDerivs 4.0 International | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject | Grafos | es |
| dc.subject | Vértices | es |
| dc.subject | Ciclos hamiltonianos | es |
| dc.title | Ubicando pares de vértices en ciclos hamiltonianos. | es |
| dc.type | Thesis | en |