Contribution to the study of alliances in graphs.ResumenEn este trabajo se estudian propiedades matemáticas de las alianzas (defensivas, ofensivas y duales) en grafos. Entre los temas tratados se destacan los siguientes:· Se estudian las alianzas en grafos producto. Específicamente, 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 número máximo de conjuntos pertenecientes a una partición del grafo en k-alianzas. Además, se estudian las relaciones existentes entre dicho número y otros invariantes del grafo, tales como el orden, la medida, el número cromático, el número isoperimétrico y la medida de bipartición. · Se estudian las propiedades matemáticas de los conjuntos libres de alianzas y los cubrimientos de alianzas. En particular, se obtienen cotas tensas para la cardinalidad máxima de un conjunto libre de alianzas y la cardinalidad mínima de un cubrimiento de alianzas. Además, 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 condición necesaria para la existencia de una partición de un grafo regular en dos alianzas fronteras. · Se estudian las alianzas ofensivas globales y sus relaciones con algunos conjuntos característicos en grafos, tales como conjuntos dominantes, t-dominantes y r-dependientes.· Se estudian las alianzas de cardinal mínimo. En particular, se hacen estimaciones de dicho cardinal en función de diversos invariantes del grafo.
| Identifer | oai:union.ndltd.org:TDX_URV/oai:www.tdx.cat:10803/8489 |
| Date | 13 December 2010 |
| Creators | González Yero, Ismael |
| Contributors | Rodríguez Velázquez, Juan Alberto, Universitat Rovira i Virgili. Departament d'Enginyeria Informàtica i Matemàtiques |
| Publisher | Universitat Rovira i Virgili |
| Source Sets | Universitat Rovira i Virgili |
| Language | English |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs., info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds