Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional

González, Lucía María

dc.contributor	Grippo, Luciano N.
dc.creator	González, Lucía María
dc.date	2024
dc.date.accessioned	2025-07-04T15:00:33Z
dc.date.available	2025-07-04T15:00:33Z
dc.date.issued	2024
dc.identifier.citation	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.
dc.identifier.uri	http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2284
dc.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..
dc.description	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.
dc.description	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.
dc.description	Fil: González, Lucía María. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina.
dc.format	application/pdf
dc.format.extent	101 p.
dc.language.iso	spa
dc.publisher	Universidad Nacional de General Sarmiento
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	https://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject	Grafos
dc.subject	Grafos Caterpillar
dc.subject	Grafos de intervalo unitario
dc.subject	Grafos de Hamming
dc.subject	Convexidades en grafos
dc.subject	3-convexidad
dc.subject	3*- convexidad
dc.subject	Convexidad digital
dc.subject	Convexidad monofónica
dc.subject	Complejidad computacional
dc.subject	Problemas de cubrimientos con conjuntos convexos y particiones en conjuntos convexos
dc.subject	Fórmulas
dc.subject	Número de cápsula convexa
dc.subject	Número de percolación
dc.subject	Número de intervalo
dc.subject	Graphs
dc.subject	Caterpillar graphs
dc.subject	Unit interval graphs
dc.subject	Hamming graphs
dc.subject	Convexities in graphs
dc.subject	3-convexity
dc.subject	3*-convexity
dc.subject	Digital convexity
dc.subject	Monophonic convexity
dc.subject	Computational complexity
dc.subject	Problems of coverings with convex sets and partitions in convex sets
dc.subject	Formulas
dc.subject	Hull number
dc.subject	Percolation number
dc.subject	Interval number
dc.subject	Grafo de intervalo unitário
dc.subject	Convexidades em grafos
dc.subject	3-convexidade
dc.subject	Número de intervalo
dc.subject	Cápsula e tempo de percolação
dc.title	Sobre convexidades en grafos : fórmulas y problemas vinculados con complejidad computacional
dc.type	info:eu-repo/semantics/doctoralThesis
dc.type	info:ar-repo/semantics/tesis doctoral
dc.type	info:eu-repo/semantics/acceptedVersion
ungs.creador.correo	lgonzale@campus.ungs.edu.ar
ungs.tesis.co-director	Dratman, Ezequiel