Submitted by Jaqueline Silva (jtas29@gmail.com) on 2014-09-04T17:02:47Z
No. of bitstreams: 2
Dissertacao Elisangela Silva Dias.pdf: 846122 bytes, checksum: 357f425f14050b1601ed04cbcd4d9165 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-09-04T17:02:47Z (GMT). No. of bitstreams: 2
Dissertacao Elisangela Silva Dias.pdf: 846122 bytes, checksum: 357f425f14050b1601ed04cbcd4d9165 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2010-03-26 / 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”. / 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”.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tde/3008 |
| Date | 26 March 2010 |
| Creators | Dias, Elisângela Silva |
| Contributors | Barbosa, Rommel Melgaço, Martins, Wellington Santos, Tronto, Íris Fabiana de Barcelos |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 8930092515683771531, -862078257083325301 |
Page generated in 0.0027 seconds