Caracterización estructural de algunos problemas en grafos circle y de intervalos

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2020-03-30

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Temas:

GRAFOS - CIRCULO - SUBGRAFOS PROHIBIDOS - COMPLETACION - MINIMAL - GRAPHS - CIRCLE - FORBIDDEN INDUCED SUBGRAPHS - COMPLETION - MINIMAL

Descripción:

Dada una familia de conjuntos no vacíos S= {Si}, se define el grafo de intersección de la familia S como el grafo obtenido al representar con un vértice a cada conjunto Si de forma tal que dos vértices son adyacentes sí y sólo si los conjuntos correspondientes tienen intersección no vacía. Un grafo se dice círculo si existe una familia de cuerdas L= {Cv} veG [fórmula aproximada, revisar la misma en el original] en un círculo de modo que dos vértices son adyacentes si las cuerdas correspondientes se intersecan. Es decir, es el grafo de intersección de la familia de cuerdas L. Existen diversas caracterizaciones de los mismos mediante operaciones como complementación local o descomposición split. Sin embargo, no se conocen aún caracterizaciones estructurales de los grafos círculo por subgrafos inducidos minimales prohibidos. En esta tesis, damos una caracterización de los grafos círculo por subgrafos inducidos prohibidos, restringido a que el grafo original sea split. Una matriz de0’s y1’s tiene la propiedad de los unos consecutivos (C1P) para sus filas si existe una permutación de sus columnas de forma tal que para cada fila, todos sus1’s se ubiquen de manera consecutiva. En esta tesis desarrollamos caracterizaciones por submatrices prohibidas de matrices de0’s y 1’s con la C1P para sus filas que además son2-coloreables bajo una cierta relación de adyacencia, y caracterizamos estructuralmente algunas subclases de grafos círculo auxiliares que se desprenden de estas matrices. Dada una clase de grafos [letra griega pi], una [letra griega pi] -completación de un grafo G= (V;E)es un grafo H= (V;E[F) [fórmula aproximada, revisar la misma en el original] tal que H pertenezca a [letra griega pi]. Una [letra griega pi] -completación H de G es minimal si H0=(V;E[F0) [fórmula aproximada, revisar la misma en el original] no pertenece a [letra griega pi] para todo F0 subconjunto propio de F. Una [letra griega pi] -completación H de G es mínima si para toda [letra griega pi] -completaciónH0= (V;E[F0) de G [fórmula aproximada, revisar la misma en el original], se tiene que el tamaño de F es inferior o igual al tamaño de F0. En esta tesis estudiamos el problema de completar de forma minimal a un grafo de intervalos propios, cuando el grafo de inputes de intervalos. Hallamos condiciones necesarias que caracterizan una completación minimal en este caso, y dejamos algunas conjeturas para considerar en el futuro.

Identificador:

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