Grafos self-clique y otras clases de grafos clique

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2001

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Descripción:

Dada una familia de conjuntos, el grafo intersección de esta familia esgenerado colocando un vértice por cada conjunto de la familia y dos vérticesson 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ónde los cliques (cada uno de ellos es un subconjunto de vértices de Gque induce un subgrafo completo maximal de G) de G. Por lo tanto, K esun 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 (sit = 1, se abrevia como self-Clique). Una familia de subconjuntos S satisface la propiedad de Helly cuandotoda subfamilia de S consistente en subconjuntos que se intersecan de apares tiene intersección no vacía. Un grafo es llamado Clique-Helly si la familia de los cliques del grafoverifica 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 paresde este grafo sean grafos self-Clique. A través de esta condición conseguimosuna nueva familia de grafos self-Clique.También presentamos otra familia degrafos self-Clique generados a partir de los grafos bipartitos que poseen unamatriz de adyacencia reducida, simétrica. Además presentarnos una caracterizaciónde los grafos self-Clique para los grafos Clique-Helly. Esta caracterizaciónindica que un grafo G posee una matriz clique AG quasi-simétrica siy sólo sí G es un grafo self-Clique y Clique-Helly. A su vez conjeturamos queen lugar de “una matriz clique quasi-simétrica”, puede ser reemplazada por “una matriz clique simétrica” en la caracterización anterior. A continuaciónpresentarnos dos condiciones suficientes para encontrar grafos 2-self-clique. Las familias de grafos 2-self-clique que surgen de estas condiciones están contenidasen la clase de los grafos Clique-Helly y una de ellas es una extensiónde la familia descripta por Escalante en [33]. Los grafos arco-circular son los grafos intersección de arcos alrededor deun círculo. Un grafo arco-circular que tiene una representación de arcosalrededor 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 cliquede los grafos arco-circular Helly. También probamos que los grafos clique delos grafos arco-circular Helly son una subclase de los grafos arco-circular yanalizamos la relación entre esta subclase con las otras ya conocidas. Ademásanalizamos algunas propiedades sobre la segunda iteración de grafos cliquede los grafos arco-circular Helly. Los grafos circular son los grafos intersección de cuerdas dentro de uncí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 yprobamos que los grafos clique de los grafos circular Helly son exactamentelos grafos dualmente circular Helly y viceversa. Probamos además que estasdos clases de grafos son distintas. A continuación, introducimos otros conceptos relacionados con los cliquesde un grafo, revisamos la definición de los grafos Clique-perfectos y presentamosuna familia de grafos altamente clique-imperfectos. Por último, presentamos algunas conclusiones que surgen de este trabajoy las líneas futuras de investigación en estos tópicos, destacando algunosproblemas interesantes que permanecen abiertos.

Identificador:

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