Número de envoltória em classes de grafos orientados
Resumo
Neste trabalho estudamos o número de envoltória para algumas classes de grafos orientados. Primeiramente apresentamos um limitante superior para o número de envoltória restrito a torneios, além de um torneio para o qual atingimos esse limite. Em seguida provamos que esse problema é NP-completo para grafos bipartidos orientados. Para tanto utilizamos o resultado de [Araujo et al. 2013], o qual afirma que tal problema é NP-completo para grafos bipartidos não-orientados. Depois mostramos uma caraterização para o menor conjunto de envoltória de umaárvore orientada. Além disso, generalizamos esse resultado ao mostrar um algoritmo de tempo polinomial para calcular o número de envoltória de qualquer grafo cacto orientado.
Referências
Albenque, M. and Knauer, K. (2016). Convexity in partial cubes: The hull number. Discrete Mathematics, 339(2):866 – 876.
Araujo, J., Campos, V., Giroire, F., Nisse, N., Sampaio, L., and Soares, R. (2013). On the hull number of some graph classes. Theoretical Computer Science, 475(Supplement C):1 – 12.
Chartrand, G., Fink, J. F., and Zhang, P. (2003). The hull number of an oriented graph. International Journal of Mathematics and Mathematical Science, 2003(36):2265–2275.
Chartrand, G., Wall, C., and Zhang, P. (2002). The convexity number of a graph. Graphs and Combinatorics, 18(2):209–217.
Duchet, P. (1988). Convex sets in graphs, ii. minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307–316.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
West, D. B. (2000). Introduction to Graph Theory. Prentice Hall, 2 edition.
Araujo, J., Campos, V., Giroire, F., Nisse, N., Sampaio, L., and Soares, R. (2013). On the hull number of some graph classes. Theoretical Computer Science, 475(Supplement C):1 – 12.
Chartrand, G., Fink, J. F., and Zhang, P. (2003). The hull number of an oriented graph. International Journal of Mathematics and Mathematical Science, 2003(36):2265–2275.
Chartrand, G., Wall, C., and Zhang, P. (2002). The convexity number of a graph. Graphs and Combinatorics, 18(2):209–217.
Duchet, P. (1988). Convex sets in graphs, ii. minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307–316.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
West, D. B. (2000). Introduction to Graph Theory. Prentice Hall, 2 edition.
Publicado
26/07/2018
Como Citar
ARAÚJO, J.; ARRAES, P..
Número de envoltória em classes de grafos orientados. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 53-56.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3150.
