Tesis Pregrado

Permanent URI for this collection

Now showing 1 - 1 of 1

Sistemas de caminos separadores de vértices en árboles.
(Universidad de Concepción, 2025) Gutiérrez Santibáñez, Milene Catalina; Sanhueza Matamala, Nicolás; Thraves Caro, Christopher
La separación de vértices en un grafo es un problema relevante en teoría de grafos, con aplicaciones en áreas como la codificación, las redes y los problemas de identificación. Un enfoque natural, es separar los vértices a través de familias de caminos. Una familia de caminos separadora de vértices en un grafo es un conjunto de caminos tal que, para cualquier par de vértices, existe un camino en la familia que contiene exactamente uno de estos vértices. En este trabajo nos enfocamos en estudiar el tamaño mínimo de una familia de caminos separadora de vértices en árboles. Nos centramos en estudiar diferentes subfamilias de árboles, considerando propiedades estructurales de ellos. Presentamos resultados exactos para diversas familias de árboles y mejoramos cotas previamente conocidas, extendiéndolas a clases más generales de árboles. Además, demostramos que, en árboles con racimos de tamaño uno, el número de separación no puede determinarse únicamente en función de parámetros locales, lo que ilustra la complejidad del problema.