Defensive alliances in Graphs / Alianças defensivas em Grafos
AUTOR(ES)
Elisângela Silva Dias
DATA DE PUBLICAÇÃO
2010
RESUMO
Uma aliança defensiva no grafo G = (V;E) é um conjunto de vértices S V satisfazendo a condição de que todo vértice v 2 S tem no máximo um vizinho a mais em V ��S que em S. Devido a este tipo de aliança, os vértices em S juntam para se defenderem dos vértices em V ��S. Nesta dissertação, são introduzidos os conceitos básicos para o entendimentos das alianças em grafos, junto com uma variedade de tipos de alianças e seus respectivos números, bem como são fornecidas algumas propriedades matemáticas para estas alianças, focando principalmente nas alianças defensivas em grafos. Apresentamos teoremas, corolários, lemas, proposições e observações com as devidas provas com relação ao grau mínimo de um grafo G d(G), ao grau máximo D(G), à conectividade algébrica μ, ao conjunto dominante total gt(G), à excentricidade, à conectividade de arestas l(G), ao número cromático c(G), ao número de independência (de vértices) b0(G), à conectividade de vértices k(G), à ordem da maior clique w(G) e ao número de dominação g(G). Também é mostrada a generalização de alianças defensivas, chamada k-aliança defensiva, e a definição e propriedades de um conjunto seguro em G. Um conjunto seguro S V do grafo G = (V;E) é um conjunto no qual todo subconjunto não-vazio pode ser defendido com sucesso de um ataque, sob as definições apropriadas de ataque e defesa.
ASSUNTO(S)
3. conjuntos seguros 3. secure sets 2. alianças defensivas ciencia da computacao 1. alianças em grafos 1. alianças em grafos; 2. alianças defensivas; 3. conjuntos seguros 2. defensive alliances 1. alliances in graphs
