Tesis > Documento


Ver el documento (formato PDF)   Grippo, Luciano Norberto.  "Caracterizaciones estructurales de grafos de intersección"  (2011)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
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.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Caracterizaciones estructurales de grafos de intersección     =    Structural characterizations of intersection graphs
Autor : Grippo, Luciano Norberto
Director : Durán, Guillermo Alfredo
Director Asistente : Bonomo, Flavia
Consejero : Lederman, Claudia
Jurados : Hell, Pavol  ; Protti, Fábio  ; Gutiérrez, Marisa
Año : 2011
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias Matemáticas
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_4904_Grippo
Idioma : Inglés
Area Temática : Matemática / Teoría de Grafos
Palabras claves : GRAFOS ARCO CIRCULARES; GRAFOS CIRCULO; SUBGRAFOS INDUCIDOS PROHIBIDOS; GRAFOS PROBE DE BLOQUES; GRAFOS PROBE CO-BIPARTITOS; GRAFOS PROBE DE INTERVALOS; GRAFOS PROBE DE INTERVALOS UNITARIOS; CIRCULAR-ARC GRAPHS; CIRCLE GRAPHS; FORBIDDEN INDUCED SUBGRAPH; PROBE BLOCK GRAPHS; PROBE CO-BIPARTITE GRAPHS; PROBE INTERVAL GRAPHS; PROBE UNIT INTERVAL GRAPHS
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34