Tesis > Documento


Ver el documento (formato PDF)   Lin, Min Chih.  "Grafos self-clique y otras clases de grafos clique"  (2001)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
Dada una familia de conjuntos, el grafo intersección de esta familia es generado colocando un vértice por cada conjunto de la familia y dos vértices son adyacentes si y sólo sí los conjuntos correspondientes se intersecan. El grafo clique de un grafo G (se denota como K (G)) es el grafo intersección de los cliques (cada uno de ellos es un subconjunto de vértices de G que induce un subgrafo completo maximal de G) de G. Por lo tanto, K es un operador que transforma un grafo en otro grafo. Si aplicamos t veces este operador K a un grafo G, el grafo resultante (denotamos como Kt(G)) es isomorfo a G, G se llama grafo t-self-clique (si t = 1, se abrevia como self-Clique). Una familia de subconjuntos S satisface la propiedad de Helly cuando toda subfamilia de S consistente en subconjuntos que se intersecan de a pares tiene intersección no vacía. Un grafo es llamado Clique-Helly si la familia de los cliques del grafo verifica la propiedad de Helly. Presentamos aquí una condición suficiente relacionada con el grado mínimo δ(G) y el girth g(G) de un grafo G para que algunas potencias pares de este grafo sean grafos self-Clique. A través de esta condición conseguimos una nueva familia de grafos self-Clique.También presentamos otra familia de grafos self-Clique generados a partir de los grafos bipartitos que poseen una matriz de adyacencia reducida, simétrica. Además presentarnos una caracterización de los grafos self-Clique para los grafos Clique-Helly. Esta caracterización indica que un grafo G posee una matriz clique AG quasi-simétrica si y sólo sí G es un grafo self-Clique y Clique-Helly. A su vez conjeturamos que en lugar de “una matriz clique quasi-simétrica”, puede ser reemplazada por “una matriz clique simétrica” en la caracterización anterior. A continuación presentarnos dos condiciones suficientes para encontrar grafos 2-self-clique. Las familias de grafos 2-self-clique que surgen de estas condiciones están contenidas en la clase de los grafos Clique-Helly y una de ellas es una extensión de la familia descripta por Escalante en . Los grafos arco-circular son los grafos intersección de arcos alrededor de un círculo. Un grafo arco-circular que tiene una representación de arcos alrededor de un círculo y a su vez estos arcos verifican la propiedad de Helly, se denomina arco-circular Helly. Presentamos también en esta tesis, una caraterización de los grafos clique de los grafos arco-circular Helly. También probamos que los grafos clique de los grafos arco-circular Helly son una subclase de los grafos arco-circular y analizamos la relación entre esta subclase con las otras ya conocidas. Además analizamos algunas propiedades sobre la segunda iteración de grafos clique de los grafos arco-circular Helly. Los grafos circular son los grafos intersección de cuerdas dentro de un círculo. Una subclase de los grafos circular es la de los grafos circular Helly, aquellos que tienen un modelo de cuerdas que verifican la propiedad de Helly. Presentamos una clase de grafos llamada dualmente circular Helly y probamos que los grafos clique de los grafos circular Helly son exactamente los grafos dualmente circular Helly y viceversa. Probamos además que estas dos clases de grafos son distintas. A continuación, introducimos otros conceptos relacionados con los cliques de un grafo, revisamos la definición de los grafos Clique-perfectos y presentamos una familia de grafos altamente clique-imperfectos. 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.

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

Registro:
Título : Grafos self-clique y otras clases de grafos clique    
Autor : Lin, Min Chih
Director : Szwarcfiter, Jayme L.
Año : 2001
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Universidad Federal de Río de Janeiro
Grado obtenido : Doctor en Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_3337_Lin
Idioma : Español
Area Temática : 
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