Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | matematica |
| Título: | Caracterizaciones estructurales de grafos de intersección |
| Título alternativo: | Structural characterizations of intersection graphs |
| Autor: | Grippo, Luciano Norberto |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la Web: | 2011-11-17 |
| Fecha de defensa: | 2011 |
| Fecha en portada: | 2011 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias Matemáticas |
| Director: | Durán, Guillermo Alfredo |
| Director Asistente: | Bonomo, Flavia |
| Consejero: | Lederman, Claudia |
| Jurado: | Hell, Pavol; Protti, Fábio; Gutiérrez, Marisa |
| Idioma: | Inglés |
| Palabras clave: | GRAFOS ARCO CIRCULARES; GRAFOS CIRCULO; SUBGRAFOS INDUCIDOS PROHIBIDOS; GRAFOS PROBE DE BLOQUES; GRAFOS PROBE CO-BIPARTITOS; GRAFOS PROBE DE INTERVALOS; GRAFOS PROBE DE INTERVALOS UNITARIOSCIRCULAR-ARC GRAPHS; CIRCLE GRAPHS; FORBIDDEN INDUCED SUBGRAPH; PROBE BLOCK GRAPHS; PROBE CO-BIPARTITE GRAPHS; PROBE INTERVAL GRAPHS; PROBE UNIT INTERVAL GRAPHS |
| Tema: | matemática/teoría de grafos
|
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n4904_Grippo |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n4904_Grippo.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n4904_Grippo |
| Ubicación: | Dep.MAT 004904 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Grippo, Luciano Norberto. (2011). Caracterizaciones estructurales de grafos de intersección. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n4904_Grippo |
Resumen:
En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos.
Abstract:
In this Thesis we study structural characterizations for six classes of graphs, namely circular-arc graphs, circle graphs, probe interval graphs, probe unit interval graphs, probe co-bipartite graphs, and probe block graphs. A circular-arc graph (circle graph) is the intersection graph of a family of arcs (chords) on a circle. Let G be a hereditary class of graphs. A graph is probe G if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a graph belonging to the class G by adding edges with both endpoints in the set of nonprobe vertices. Probe G graphs form a superclass of the class G. Hence, probe interval graphs and probe unit interval graphs are extensions of the classes of interval graphs and unit interval graphs, respectively. We partially characterize circular-arc graphs, circle graphs, probe interval graphs and probe unit interval graphs by forbidden induced subgraphs within certain hereditary families of graphs. Finally, a structural characterization for probe co-bipartite graphs that leads to a polynomial-time recognition algorithm and a complete characterization of probe block graphs by a list of forbidden induced subgraphs are presented.
Citación:
---------- APA ----------
Grippo, Luciano Norberto. (2011). Caracterizaciones estructurales de grafos de intersección. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n4904_Grippo
---------- CHICAGO ----------
Grippo, Luciano Norberto. "Caracterizaciones estructurales de grafos de intersección". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2011.https://hdl.handle.net/20.500.12110/tesis_n4904_Grippo
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n4904_Grippo.pdf
