Grafos self-clique y otras clases de grafos clique

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Lin, Min Chih
Otros Autores:	Szwarcfiter, Jayme L.
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2001
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n3337_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	tesis:tesis_n3337_Lin
record_format	dspace
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language	Español
orig_language_str_mv	spa
description	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.
author2	Szwarcfiter, Jayme L.
author_facet	Szwarcfiter, Jayme L. Lin, Min Chih
format	Tesis doctoral Tesis doctoral publishedVersion
author	Lin, Min Chih
spellingShingle	Lin, Min Chih Grafos self-clique y otras clases de grafos clique
author_sort	Lin, Min Chih
title	Grafos self-clique y otras clases de grafos clique
title_short	Grafos self-clique y otras clases de grafos clique
title_full	Grafos self-clique y otras clases de grafos clique
title_fullStr	Grafos self-clique y otras clases de grafos clique
title_full_unstemmed	Grafos self-clique y otras clases de grafos clique
title_sort	grafos self-clique y otras clases de grafos clique
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2001
url	https://hdl.handle.net/20.500.12110/tesis_n3337_Lin
work_keys_str_mv	AT linminchih grafosselfcliqueyotrasclasesdegrafosclique
_version_	1782023062833594368
spelling	tesis:tesis_n3337_Lin2023-10-02T19:47:36Z Grafos self-clique y otras clases de grafos clique Lin, Min Chih Szwarcfiter, Jayme L. 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. Fil: Lin, Min Chih. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2001 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n3337_Lin

Grafos self-clique y otras clases de grafos clique

Ejemplares similares