Caracterización estructural de los ́arboles de thinness propia 2

Mostrar todas las versiones(2)

La thinness propia de un grafo es un invariante que generaliza a los grafos de intervalos propios. Todo grafo tiene un valor numérico de thinness propia y los grafos con thinness propia 1 coinciden con los grafos de intervalos propios. Un grafo es k-thin propio si sus vértices pueden ordenarse de ma...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Maqueda, Juan Ignacio
Otros Autores: Bonomo, Flavia
Formato: Tesis de grado publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2023
Materias:
ARBOLES
THINNESS PROPIA
CARACTERIZACIONES
TREES
PROPER THINNESS
CHARACTERIZATIONS
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000532_Maqueda
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id seminario:seminario_nCOM000532_Maqueda
record_format dspace
spelling seminario:seminario_nCOM000532_Maqueda2025-09-29T12:12:20Z Caracterización estructural de los ́arboles de thinness propia 2 Maqueda, Juan Ignacio Bonomo, Flavia ARBOLES THINNESS PROPIA CARACTERIZACIONES TREES PROPER THINNESS CHARACTERIZATIONS La thinness propia de un grafo es un invariante que generaliza a los grafos de intervalos propios. Todo grafo tiene un valor numérico de thinness propia y los grafos con thinness propia 1 coinciden con los grafos de intervalos propios. Un grafo es k-thin propio si sus vértices pueden ordenarse de manera que exista una partición de los vértices en k clases cumpliendo que para cada tripla de vértices r < s < t, tales que existe una arista entre r y t, se cumplen que si r y s pertenecen a la misma clase, entonces existe una arista entre s y t, y si s y t pertenecen a la misma clase, entonces existe una arista entre r y s. La thinness propia de un grafo es el menor valor de k tal que el grafo sea k-thin propio. En este trabajo nos enfocamos en el cálculo de la thinness propia para los árboles. Caracterizamos los árboles de thinness propia 2, tanto estructuralmente como por sus subgrafos inducidos minimales prohibidos. También mostramos por que los resultados obtenidos para árboles de thinness propia 2 no pueden ser generalizados a árboles de thinness propia 3. The proper thinness of a graph is an invariant that generalizes the concept of a proper interval graph. Every graph has a numerical value of proper thinness and the graphs with proper thinness 1 are exactly the proper interval graphs. A graph is proper k-thin if its vertices can be ordered in such a way that there is a partition of the vertices into k classes satisfying that for each triple of vertices r < s < t, such that there is an edge between r and t, it is true that if r and s belong to the same class, then there is an edge between s and t, and if s and t belong to the same class, then there is an edge between r and s. The proper thinness is the smallest value of k such that the graph is proper k-thin. In this work we focus on the calculation of proper thinness for trees. We characterize trees of proper thinness 2, both structurally and by their minimal forbidden induced subgraphs. We also show why the results obtained for trees of proper thinness 2 cannot be generalized to trees of proper thinness 3. Fil: Maqueda, Juan Ignacio. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2023 info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/seminario_nCOM000532_Maqueda
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv spa
topic ARBOLES
THINNESS PROPIA
CARACTERIZACIONES
TREES
PROPER THINNESS
CHARACTERIZATIONS
spellingShingle ARBOLES
THINNESS PROPIA
CARACTERIZACIONES
TREES
PROPER THINNESS
CHARACTERIZATIONS
Maqueda, Juan Ignacio
Caracterización estructural de los ́arboles de thinness propia 2
topic_facet ARBOLES
THINNESS PROPIA
CARACTERIZACIONES
TREES
PROPER THINNESS
CHARACTERIZATIONS
description La thinness propia de un grafo es un invariante que generaliza a los grafos de intervalos propios. Todo grafo tiene un valor numérico de thinness propia y los grafos con thinness propia 1 coinciden con los grafos de intervalos propios. Un grafo es k-thin propio si sus vértices pueden ordenarse de manera que exista una partición de los vértices en k clases cumpliendo que para cada tripla de vértices r < s < t, tales que existe una arista entre r y t, se cumplen que si r y s pertenecen a la misma clase, entonces existe una arista entre s y t, y si s y t pertenecen a la misma clase, entonces existe una arista entre r y s. La thinness propia de un grafo es el menor valor de k tal que el grafo sea k-thin propio. En este trabajo nos enfocamos en el cálculo de la thinness propia para los árboles. Caracterizamos los árboles de thinness propia 2, tanto estructuralmente como por sus subgrafos inducidos minimales prohibidos. También mostramos por que los resultados obtenidos para árboles de thinness propia 2 no pueden ser generalizados a árboles de thinness propia 3.
author2 Bonomo, Flavia
author_facet Bonomo, Flavia
Maqueda, Juan Ignacio
format Tesis de grado
Tesis de grado
publishedVersion
author Maqueda, Juan Ignacio
author_sort Maqueda, Juan Ignacio
title Caracterización estructural de los ́arboles de thinness propia 2
title_short Caracterización estructural de los ́arboles de thinness propia 2
title_full Caracterización estructural de los ́arboles de thinness propia 2
title_fullStr Caracterización estructural de los ́arboles de thinness propia 2
title_full_unstemmed Caracterización estructural de los ́arboles de thinness propia 2
title_sort caracterización estructural de los ́arboles de thinness propia 2
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2023
url https://hdl.handle.net/20.500.12110/seminario_nCOM000532_Maqueda
work_keys_str_mv AT maquedajuanignacio caracterizacionestructuraldelosarbolesdethinnesspropia2
_version_ 1851370956909445120

Ejemplares similares