Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional
En esta tesis estudiamos distintos tipos de convexidades en grafos y parámetros asociados a ellas. Una convexidad en un grafo G es un par (V(G); C) donde C es una familia de subconjuntos de V(G) que satisface las siguientes condiciones: ∅ ∈ C, V(G) ∈ C y C es cerrado bajo intersecciones. A cada conj...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Tesis doctoral acceptedVersion |
| Lenguaje: | Español |
| Publicado: |
Universidad Nacional de General Sarmiento
2024
|
| Materias: | |
| Acceso en línea: | http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2284 |
| Aporte de: |
| Sumario: | En esta tesis estudiamos distintos tipos de convexidades en grafos y parámetros asociados a ellas. Una convexidad en un grafo G es un par (V(G); C) donde C es una familia de subconjuntos de V(G) que satisface las siguientes condiciones: ∅ ∈ C, V(G) ∈ C y C es cerrado bajo intersecciones. A cada conjunto de la familia C se lo llama C-convexo. Presentamos resultados sobre complejidad relacionados con cubrimientos de los vértices de un grafo con p conjuntos convexos y relacionados con particionar los vértices de un grafo con p conjuntos convexos. Presentamos una fórmula para calcular el número de intervalo, otra para el número de cápsula y otra para el tiempo de percolación bajo la P3-convexidad de un grafo caterpillar. Encontramos una relación entre el tiempo de P3-percolación de un grafo de intervalo unitario y un parámetro relacionado con el diámetro de un grafo de intervalo unitario. Presentamos una clase de grafos hereditarios tal que su tiempo de P3-percolación es igual a uno. Presentamos, para una subfamilia dentro de los grafos de Hamming, una fórmula para el número de Carathéodory bajo la P3-convexidad.. |
|---|