Intersecção de Caminhos mais Longos em Produtos de Grafos

• Gabriel Matheus Faria de Almeida UFG
• Elisângela Silva Dias UFG

Resumo

O problema de caminhos mais longos começou a ser discutido por volta de 1966 a partir de uma questão levantada por Gallai, que questiona se todo grafo conexo tem pelo menos um vértice que aparece em todos os caminhos mais longos. Neste trabalho, foram estudados os caminhos mais longos em produtos de grafos, grafos cordais, grafos ponderados, árvores e grafos prismas complementares e foram obtidos resultados teóricos e alguns algoritmos de tempo fatorial buscando entender o problema e o comportamento dos caminhos mais longos nos diferentes tipos de grafos.

Palavras-chave: Grafos Conexos, Grafos Cordais, Grafos Ponderados, Grafos Prismas Complementares.

Referências

Cormen, T. H., Leiserson, C. E., Rivest R. L., and Stein, C. (2009). Introduction to algorithms. MIT press, 3th edition.

Bondy, J. A. and Murty U. R. (2008). Graph Theory, Graduate Texts in Mathematics. Springer.

Dirac, G. A. (1952). “Some theorems on abstract graphs.” Proceedings of the London Mathematical Society 3.1, pages 69–81.

Erdos, P. and Katona G. (1966). Theory of Graphs. Proceedings of the Colloquium held at Tihany, Hungrary. Academic Press, New York. Problem 4 (Gallai T.), page 362.

Rezende, S. F. (2014). “Caminhos mais longos em grafos”. Dissertação de mestrado, USP.

Walther, H. and Voss H. J. (1974). Uber¨ Kreise in Graphen. VEB Deutscher Verlag der Wissenschaften, Berlin.

Zamfirescu, T. (1976). On longest paths and circuits in graphs. Mathematica Scandina-vica, Vol. 38, pages 211–239.