Catálogo de publicaciones - tesis
Título de Acceso Abierto
Grafos self-clique y otras clases de grafos clique
Min Chih Lin Jayme L. Szwarcfiter
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
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 [33]. 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.Palabras clave – provistas por el repositorio digital
No disponibles.
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2001 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2001
Información sobre licencias CC