Contribution to the study of alliances in graphs
Ismael G. Yero · TDX (Tesis Doctorals en Xarxa) · 2010
En este trabajo se estudian propiedades matematicas de las alianzas (defensivas, ofensivas y duales) en grafos. Entre los temas tratados se destacan los siguientes: ? Se estudian las alianzas en grafos producto. Especificamente, se obtienen relaciones entre las alianzas en grafos producto Cartesiano y las alianzas en los factores. ? Se estudia las particiones de un grafo en alianzas. En particular, se hacen estimaciones del numero maximo de conjuntos pertenecientes a una particion del grafo en k-alianzas. Ademas, se estudian las relaciones existentes entre dicho numero y otros invariantes del grafo, tales como el orden, la medida, el numero cromatico, el numero isoperimetrico y la medida de biparticion. ? Se estudian las propiedades matematicas de los conjuntos libres de alianzas y los cubrimientos de alianzas. En particular, se obtienen cotas tensas para la cardinalidad maxima de un conjunto libre de alianzas y la cardinalidad minima de un cubrimiento de alianzas. Ademas, se caracterizan grafos que son libres de k-alianzas defensivas. ? Se introduce el concepto de alianza frontera y se estudian algunas de sus propiedades. Entre los resultados obtenidos se destaca una condicion necesaria para la existencia de una particion de un grafo regular en dos alianzas fronteras. ? Se estudian las alianzas ofensivas globales y sus relaciones con algunos conjuntos caracteristicos en grafos, tales como conjuntos dominantes, t-dominantes y r-dependientes. ? Se estudian las alianzas de cardinal minimo. En particular, se hacen estimaciones de dicho cardinal en funcion de diversos invariantes del grafo.