Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-08-12T15:13:32Z
No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) / Made available in DSpace on 2014-08-12T15:13:32Z (GMT). No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5)
Previous issue date: 2009-03-12 / Given a graph G = (V;E) and a set of vertices D V, a vertice v 2 V is dominated by D if jN[v] \ Dj 1. When jN(v) \ Dj = 1 for all v 2 V, G is efficiently dominable. A generalization of this concept is called efficient multiple domination, which requires all vertices must be dominated by a set D V exactly k times. The aim of this dissertation is to study these topics, describing the theoretical knowledge needed for advanced
researches. For this reason, many of the theorems and its proofs are detailed. Furthermore, some results on the efficient multiple domination are presented, including bounds for
the size of efficient k-dominating sets, the complement and iterated line graphs of efficiently (r + 1)-dominable r-regular graphs and a N P-completeness proof for the efficient multiple domination problem in arbitrary graphs. It is expected that this work contribute to the development of future researches on the efficient domination and in the resolution of some open problems. / Dado um grafo G = (V;E) e um subconjunto de vértices D V, define-se D como um conjunto dominante de G se todo vértice v 2 V que não estiver incluído no conjunto D for adjacente a pelo menos um vértice de D. Na situação em que, para todo v 2 V, jN[v]\Dj = 1, diz-se que o grafo G é eficientemente dominado. Uma generalização desse
conceito consiste na múltipla dominação eficiente, em que é requerido que todo vértice do grafo seja dominado exatamente k vezes. O objetivo deste trabalho é realizar um
estudo exploratório sobre esses temas, de modo a reunir o conhecimento teórico requerido para pesquisas avançadas. Para isso, buscou-se a apresentação e o detalhamento das
demonstrações dos teoremas estudados. Além disso, foram fornecidos alguns resultados sobre a múltipla dominação eficiente no que se refere aos limites para o tamanho de
um conjunto k-dominante eficiente, à relação da k-dominação eficiente entre grafos regulares, seu complemento e seus grafos linha iterados, bem como à caracterização da
N P-completude para o problema da múltipla dominação eficiente em grafos arbitrários. Espera-se que esta dissertação forneça subsídios teóricos para estudos futuros voltados à dominação eficiente, bem como à resolução de algumas questões em aberto.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tde/2901 |
| Date | 12 March 2009 |
| Creators | Oliveira, Rommel Teodoro de |
| Contributors | Barbosa, Rommel Melgaço |
| 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, -7712266734633644768, 3671711205811204509 |
Page generated in 0.1639 seconds