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: |
| id |
I71-R177-UNGS-2284 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de General Sarmiento |
| institution_str |
I-71 |
| repository_str |
R-177 |
| collection |
Repositorio Institucional Digital de Acceso Abierto (UNGS) |
| language |
Español |
| orig_language_str_mv |
spa |
| topic |
Grafos Grafos Caterpillar Grafos de intervalo unitario Grafos de Hamming Convexidades en grafos 3-convexidad 3*- convexidad Convexidad digital Convexidad monofónica Complejidad computacional Problemas de cubrimientos con conjuntos convexos y particiones en conjuntos convexos Fórmulas Número de cápsula convexa Número de percolación Número de intervalo Graphs Caterpillar graphs Unit interval graphs Hamming graphs Convexities in graphs 3-convexity 3*-convexity Digital convexity Monophonic convexity Computational complexity Problems of coverings with convex sets and partitions in convex sets Formulas Hull number Percolation number Interval number Grafo de intervalo unitário Convexidades em grafos 3-convexidade Número de intervalo Cápsula e tempo de percolação |
| spellingShingle |
Grafos Grafos Caterpillar Grafos de intervalo unitario Grafos de Hamming Convexidades en grafos 3-convexidad 3*- convexidad Convexidad digital Convexidad monofónica Complejidad computacional Problemas de cubrimientos con conjuntos convexos y particiones en conjuntos convexos Fórmulas Número de cápsula convexa Número de percolación Número de intervalo Graphs Caterpillar graphs Unit interval graphs Hamming graphs Convexities in graphs 3-convexity 3*-convexity Digital convexity Monophonic convexity Computational complexity Problems of coverings with convex sets and partitions in convex sets Formulas Hull number Percolation number Interval number Grafo de intervalo unitário Convexidades em grafos 3-convexidade Número de intervalo Cápsula e tempo de percolação González, Lucía María Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional |
| topic_facet |
Grafos Grafos Caterpillar Grafos de intervalo unitario Grafos de Hamming Convexidades en grafos 3-convexidad 3*- convexidad Convexidad digital Convexidad monofónica Complejidad computacional Problemas de cubrimientos con conjuntos convexos y particiones en conjuntos convexos Fórmulas Número de cápsula convexa Número de percolación Número de intervalo Graphs Caterpillar graphs Unit interval graphs Hamming graphs Convexities in graphs 3-convexity 3*-convexity Digital convexity Monophonic convexity Computational complexity Problems of coverings with convex sets and partitions in convex sets Formulas Hull number Percolation number Interval number Grafo de intervalo unitário Convexidades em grafos 3-convexidade Número de intervalo Cápsula e tempo de percolação |
| description |
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.. |
| author2 |
Grippo, Luciano N. |
| author_facet |
Grippo, Luciano N. González, Lucía María |
| format |
Tesis doctoral Tesis doctoral acceptedVersion |
| author |
González, Lucía María |
| author_sort |
González, Lucía María |
| title |
Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional |
| title_short |
Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional |
| title_full |
Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional |
| title_fullStr |
Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional |
| title_full_unstemmed |
Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional |
| title_sort |
sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional |
| publisher |
Universidad Nacional de General Sarmiento |
| publishDate |
2024 |
| url |
http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2284 |
| work_keys_str_mv |
AT gonzalezluciamaria sobreconvexidadesengrafosformulasyproblemasvinculadosconcomplejidadcomputacional |
| _version_ |
1842217816228364288 |
| spelling |
I71-R177-UNGS-22842025-07-04T15:21:16Z Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional González, Lucía María Grippo, Luciano N. Grafos Grafos Caterpillar Grafos de intervalo unitario Grafos de Hamming Convexidades en grafos 3-convexidad 3*- convexidad Convexidad digital Convexidad monofónica Complejidad computacional Problemas de cubrimientos con conjuntos convexos y particiones en conjuntos convexos Fórmulas Número de cápsula convexa Número de percolación Número de intervalo Graphs Caterpillar graphs Unit interval graphs Hamming graphs Convexities in graphs 3-convexity 3*-convexity Digital convexity Monophonic convexity Computational complexity Problems of coverings with convex sets and partitions in convex sets Formulas Hull number Percolation number Interval number Grafo de intervalo unitário Convexidades em grafos 3-convexidade Número de intervalo Cápsula e tempo de percolação 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.. In this thesis, we study different types of convexities in graphs and associated parameters. A convexity of a graph G is a pair (V(G), C) where C is a family of subsets of V(G) satisfying all the following conditions: ∅ ∈ C, V(G) ∈ C and C is closed under intersections. Each set of the family C is called C-convex. We present some complexity results concerning the problems of covering a graph with p convex sets and of partitioning a graph into p convex sets. We also present formulas to compute the P3-interval number, the P3-hull number and the P3-percolation time for a caterpillar, in terms of certain sequences associated with it. In addition, we find a connection between the percolation time of a unit interval graph and a parameter involving the diameter of a unit interval graph related to it. Furthermore, we present a hereditary graph class, defined by forbidden induced subgraphs, such that its percolation time is equal to one. Finally, we present a formula for the Carathéodory number under the P3-convexity in a subfamily of Hamming graphs. Nesta tese, estudamos diferentes tipos de convexidades em grafos e parâmetros associados a elas. Uma convexidade em um grafo G é um par (V(G); C) onde C é uma família de subconjuntos de V(G) que satisfaz as seguintes condições, ∅ ∈ C, V(G) ∈ C, C está fechado sob interseções. Cada subconjunto na família C é chamado de C-convexo. Presentamos resultados relacionados á complexidade, incluindo coberturas de vértices com p conjuntos convexos e partição de vértices em p conjuntos convexos. Também apresentamos fórmulas para calcular o número de intervalo, cápsula e tempo de percolação sob a P3-convexidade de um grafo caterpillar. Além disso, encontramos uma relação entre o tempo de percolação de um grafo de intervalo unitário e um parâmetro relacionado ao diâmetro de um grafo de intervalo unitário. Presentamos uma classe de grafos hereditários tal que seu tempo de P3-percolação é igual a 1. Presentamos, para uma família dentro dos grafos de Hamming, uma fórmula para o número de Carathéodory sob a P3-convexidade. Fil: González, Lucía María. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. 2024 2025-07-04T15:00:33Z 2025-07-04T15:00:33Z 2024 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/acceptedVersion González, L. M. (2024). Sobre convexidades en grafos: fórmulas y problemas vinculados con complejidad computacional. [Tesis de doctorado]. Los Polvorines, Argentina : Universidad Nacional de General Sarmiento. http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2284 spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf 101 p. application/pdf Universidad Nacional de General Sarmiento |