Alianças defensivas em grafos
Nenhuma Miniatura disponível
Data
2010-03-26
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
A defensive alliance in graph G = (V,E) is a set of vertices S ⊆V satisfying the condition
that every vertex v ∈ 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 δ(G), the maximum degree ∆(G),
the algebraic connectivity µ, the total dominanting set γt(G), the eccentricity, the edge
connectivity λ(G), the chromatic number χ(G), the (vertex) independence number β0(G),
the vertex connectivity κ(G), the order of the largest clique ω(G) and the domination
number γ(G). It also shows a generalization of defensive alliances, called defensive k alliance, 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”.
Descrição
Palavras-chave
Citação
DIAS, E. S. Alianças Defensivas em Grafos. 2010. 105 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2010.