Sobre grafos intersección de arcos y cuerdas en un círculo

Mostrar todas las versiones(3)

Los grafos arco-circulares son los grafos intersección de arcos alrededor de un círculo. Presentamos en esta tesis los principales resultados conocidos sobre esta clase y definimos las principales subclases. Mostramos como a partir de la caracterización formulada por Tucker para grafos arco-circular...

Descripción completa

Detalles Bibliográficos
Autor principal: Durán, Guillermo Alfredo
Otros Autores: Szwarcfiter, Jayme L.
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2000
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n3260_Duran
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n3260_Duran
record_format dspace
spelling tesis:tesis_n3260_Duran2025-03-31T21:15:49Z Sobre grafos intersección de arcos y cuerdas en un círculo Durán, Guillermo Alfredo Szwarcfiter, Jayme L. Los grafos arco-circulares son los grafos intersección de arcos alrededor de un círculo. Presentamos en esta tesis los principales resultados conocidos sobre esta clase y definimos las principales subclases. Mostramos como a partir de la caracterización formulada por Tucker para grafos arco-circular propios surgen nuevas caracterizaciones para esta subclase y deducimos características de las estructuras prohibidas minimales para arco-circulares. Se estudian todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan, excepto en una de ellas que se demuestra que es vacía. Este resultado asegura que dado un grafo arco-circular propio no unitario, si es clique-Helly debe ser arco-circular Helly. Los grafos circulares son los grafos intersección de cuerdas dentro de un círculo. También aquí presentamos una reseña de los resultados más importantes y definimos las principales subclases, demostrando algunas relaciones de inclusión entre ellas. Damos una condición necesaria para que un grafo sea circular Helly y conjeturamos que también es suficiente. De ser correcta esta conjetura tendríamos una caracterización y también un reconocimiento polinomial para esta subclase. Se muestra como a partir de la mencionada caracterización de Tucker para grafos arco-circular propios y de un teorema de caracterización de Bouchet para los circulares surgen estructuras prohibidas minimales para esta clase. Analizamos también todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan. Estudiamos una superclase de los grafos circulares: los grafos overlap de arcos circulares. Se muestran nuevas propiedades sobre esta clase, poniendo énfasis en su relación con los grafos arco-circulares y los circulares. Damos una condición necesaria para que un grafo sea overlap de arcos circulares. Probarnos la polinomialidad de encontrar una partición en cliques mínima para la clase de grafos que no contienen como subgrafo inducido ciclos inducidos impares de longitud mayor ó igual a 5 ni una rueda de 5 vétices ni un abanico de 5 vértices. Usamos para ello resultados de teoría poliedral para programación lineal entera. Extendemos este mismo resultado para cubrimiento mínimo de cliques por vértices. Aplicamos estos resultados a grafos circular HelIy sin agujeros impares, lo que es interesante pues estos problemas son NP-Hard para la clase general de los grafos y de complejidad desconocida para la clase de los grafos circulares. También demostramos que el problema de cubrimiento mínimo de cliques por vértices es polinomial para grafos arco-circular Helly. Por último, presentamos algunas conclusiones que surgen de este trabajo y las líneas futuras de investigación en estos tópicos, destacando algunos problemas interesantes que permanecen abiertos. Fil: Durán, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2000 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral 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/tesis_n3260_Duran
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
description Los grafos arco-circulares son los grafos intersección de arcos alrededor de un círculo. Presentamos en esta tesis los principales resultados conocidos sobre esta clase y definimos las principales subclases. Mostramos como a partir de la caracterización formulada por Tucker para grafos arco-circular propios surgen nuevas caracterizaciones para esta subclase y deducimos características de las estructuras prohibidas minimales para arco-circulares. Se estudian todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan, excepto en una de ellas que se demuestra que es vacía. Este resultado asegura que dado un grafo arco-circular propio no unitario, si es clique-Helly debe ser arco-circular Helly. Los grafos circulares son los grafos intersección de cuerdas dentro de un círculo. También aquí presentamos una reseña de los resultados más importantes y definimos las principales subclases, demostrando algunas relaciones de inclusión entre ellas. Damos una condición necesaria para que un grafo sea circular Helly y conjeturamos que también es suficiente. De ser correcta esta conjetura tendríamos una caracterización y también un reconocimiento polinomial para esta subclase. Se muestra como a partir de la mencionada caracterización de Tucker para grafos arco-circular propios y de un teorema de caracterización de Bouchet para los circulares surgen estructuras prohibidas minimales para esta clase. Analizamos también todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan. Estudiamos una superclase de los grafos circulares: los grafos overlap de arcos circulares. Se muestran nuevas propiedades sobre esta clase, poniendo énfasis en su relación con los grafos arco-circulares y los circulares. Damos una condición necesaria para que un grafo sea overlap de arcos circulares. Probarnos la polinomialidad de encontrar una partición en cliques mínima para la clase de grafos que no contienen como subgrafo inducido ciclos inducidos impares de longitud mayor ó igual a 5 ni una rueda de 5 vétices ni un abanico de 5 vértices. Usamos para ello resultados de teoría poliedral para programación lineal entera. Extendemos este mismo resultado para cubrimiento mínimo de cliques por vértices. Aplicamos estos resultados a grafos circular HelIy sin agujeros impares, lo que es interesante pues estos problemas son NP-Hard para la clase general de los grafos y de complejidad desconocida para la clase de los grafos circulares. También demostramos que el problema de cubrimiento mínimo de cliques por vértices es polinomial para grafos arco-circular Helly. Por último, presentamos algunas conclusiones que surgen de este trabajo y las líneas futuras de investigación en estos tópicos, destacando algunos problemas interesantes que permanecen abiertos.
author2 Szwarcfiter, Jayme L.
author_facet Szwarcfiter, Jayme L.
Durán, Guillermo Alfredo
format Tesis doctoral
Tesis doctoral
publishedVersion
author Durán, Guillermo Alfredo
spellingShingle Durán, Guillermo Alfredo
Sobre grafos intersección de arcos y cuerdas en un círculo
author_sort Durán, Guillermo Alfredo
title Sobre grafos intersección de arcos y cuerdas en un círculo
title_short Sobre grafos intersección de arcos y cuerdas en un círculo
title_full Sobre grafos intersección de arcos y cuerdas en un círculo
title_fullStr Sobre grafos intersección de arcos y cuerdas en un círculo
title_full_unstemmed Sobre grafos intersección de arcos y cuerdas en un círculo
title_sort sobre grafos intersección de arcos y cuerdas en un círculo
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2000
url https://hdl.handle.net/20.500.12110/tesis_n3260_Duran
work_keys_str_mv AT duranguillermoalfredo sobregrafosintersecciondearcosycuerdasenuncirculo
_version_ 1831982282722770944

Ejemplares similares