Detalhes bibliográficos
| Ano de defesa: |
2010 |
| Autor(a) principal: |
Dias, Elisângela Silva
 |
| Orientador(a): |
Barbosa, Rommel Melgaço
|
| Banca de defesa: |
Martins, Wellington Santos
,
Tronto, Íris Fabiana de Barcelos
|
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Universidade Federal de Goiás
|
| Programa de Pós-Graduação: |
Programa de Pós-graduação em Ciência da Computação (INF)
|
| Departamento: |
Instituto de Informática - INF (RG)
|
| País: |
Brasil
|
| Palavras-chave em Português: |
|
| Palavras-chave em Inglês: |
|
| Área do conhecimento CNPq: |
|
| Link de acesso: |
http://repositorio.bc.ufg.br/tede/handle/tde/3008
|
Resumo: |
A defensive alliance in graph G = (V;E) is a set of vertices S V satisfying the condition that every vertex v 2 S has at most one more neighbor in V S than S. Due to this type of alliance, the vertices in S together defend themselves to the vertices in V S. This dissertation introduces the basic concepts for the understanding of alliances in graphs, along with a variety of alliances and their numbers and provides some mathematical properties for these alliances, focusing mainly on defensive alliances in graphs. It shows theorems, corollaries, lemmas, propositions and observations with appropriate proofs with respect to the minimum degree of a graph G d(G), the maximum degree D(G), the algebraic connectivity μ, the total dominanting set gt(G), the eccentricity, the edge connectivity l(G), the chromatic number c(G), the (vertex) independence number b0(G), the vertex connectivity k(G), the order of the largest clique w(G) and the domination number g(G). It also shows a generalization of defensive alliances, called defensive kalliance, and the definition and properties of a security set in G. A secure set S V of graph G = (V;E) is a set whose every nonempty subset can be successfully defended of an attack, under appropriate definitions of “attack” and “defence”. |
