Abstract
En la práctica, una alianza puede ser un vínculo o una conexión entre individuos,
familias, estados, entidades, etc. Formalmente, un conjunto no vacío S de vértices
de un grafo G es una alianza defensiva si cada vértice de S tiene al menos uno o más
vecinos en S que fuera de él.
Durante la pasada década hubo un desarrollo notable de tres tipos de alianzas,
alianzas defensivas, alianzas ofensivas y alianzas duales. Debido a la variedad de
aplicaciones, las alianzas han recibido una especial atención por muchos científicos e
investigadores. Hay aplicaciones de alianzas en varias áreas como la bioinformática,
la computación distribuida, las comunidades web, las redes sociales, la clasificación
de los datos, empresas, etc.
Distintos parámetros de alianza han sido de nidos y un gran número de resultados teóricos (algorítmicos y computacionales) se han obtenido para varios tipos
de grafos. En este documento se presenta un
survey
de los resultados obtenidos
hasta ahora sobre las alianzas, centrándonos principalmente en las alianzas defensivas. Además, se dan algunos resultados y algoritmos sobre parámetros de alianzas
defensivas para dos tipos de grafos, grafos soles y grafos orugas.---ABSTRACT---In practice, an alliance can be a bond or connection between individuals, families,
states, or entities, etc. Formally, a non-empty set S of vertices of a graph G is a
defensive alliance if every vertex of S has at least one more neighbour inside of S
than it has outside of S.
During the last decade there has been a remarkable development on three kinds
of alliances, defensive alliance, o ensive alliance and powerful alliance. Due to their
variety of applications, the alliances have received a special attention from many
scientists and researchers. There are applications of alliances in several areas such
as bioinformatics, distributed computing, web communities, social networks, data
clustering, business, etc.
Several alliance numbers have been de ned and a huge number of theoretical
(algorithmic and computational) results are obtained for various graph classes. In
this paper, we present a survey with the results obtein about alliances, mainly in
the defensive alliances. Also, we give some results and algorithms about alliance
numbers for two graph classes, sun graphs and caterpillar graph