Caracterizaciones estructurales de grafos de intersección

Structural characterizations of intersection graphs

dc.contributorDurán, Guillermo Alfredo
dc.creatorGrippo, Luciano Norberto
dc.date2011
dc.date.accessioned2017-01-24T19:44:32Z
dc.date.available2017-01-24T19:44:32Z
dc.identifierhttp://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_4904_Grippo
dc.identifierhttp://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=HASH598a7a4a2441cf6af98e22
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/74494
dc.descriptionEn 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.
dc.formattext; pdf
dc.languageInglés
dc.publisherFacultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
dc.subjectMatemática / Teoría de Grafos
dc.subjectGRAFOS ARCO CIRCULARES
dc.subjectGRAFOS CIRCULO
dc.subjectSUBGRAFOS INDUCIDOS PROHIBIDOS
dc.subjectGRAFOS PROBE DE BLOQUES
dc.subjectGRAFOS PROBE CO-BIPARTITOS
dc.subjectGRAFOS PROBE DE INTERVALOS
dc.subjectGRAFOS PROBE DE INTERVALOS UNITARIOS
dc.titleCaracterizaciones estructurales de grafos de intersección
dc.titleStructural characterizations of intersection graphs
dc.typeTesis


Este ítem pertenece a la siguiente institución