Caracterizaciones estructurales de grafos de intersección

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2011

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

eng

Temas:

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

Descripción:

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.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n4904_Grippo