Dominação e Dominação Total em Grafos Cúbicos de Cintura Grande
Autores
|
5577 |
Deiwison Sousa Machado
|
2566,200,427
|
|
5578 |
2566,200,427
|
|
|
5579 |
2566,200,427
|
Informações:
Publicações do PESC
Título
Dominação e Dominação Total em Grafos Cúbicos de Cintura Grande
Linha de pesquisa
Inteligência Artificial
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
20/3/2014
Resumo
Essa dissertação versa sobre conjuntos dominantes em grafos cúbicos de cintura grande. Nosso objetivo é comparar os números de dominação e dominação total de um grafo cúbico G de forma a contribuir para uma melhor compreensão da relação existente entre estes dois parâmetros e, como consequência da nossa pesquisa, melhoramos os limites existentes na literatura.
Para um grafo cúbico G de ordem n, cintura pelo menos g e número de dominação (1/4+ ε)n, para algum
ε > 0, mostramos que o número de dominação total de G é no máximo 13n/32+O(n/g)+O(εn), o que implica que γ_t(G)/ γ(G) <= 1.89714+O(1/g).
Abstract
This dissertation discuss the dominating sets in cubic graphs of large girth. Our goal is to compare the total dominaion number and the domination number of a cubic graph G in order to better understand the relationship between these two parameters. With our research, we have improved the bounds found in the literature.
For a cubic graph G of order n, girth at least g, and domination number (1/4+ ε)n, for some ε > 0, we proved that the total domination number of G is at most 13n/32+O(n/g) +O(εn), which implies γ_t(G)/γ(G) <= 1.89714+O(1/g).
Arquivo