O trabalho a ser desenvolvido insere-se na área de teoria dos grafos, e tem como foco o estudo de caminhos mais longos em grafos, do ponto de vista estrutural. É bem conhecido o fato de que quaisquer dois caminhos mais longos em um grafo conexo têm um vértice em comum. Em 1966, Gallai questionou se esse fato continua verdadeiro quando se considera todos os caminhos mais longos em um grafo conexo. Em 1969, foi provada que a resposta a essa questão é negativa. Desde então, diversas classes de grafos têm sido estudadas a esse respeito, e para algumas delas sabe-se que a resposta é positiva. Com relação a outros problemas relacionados à essa questão, surge naturalmente o problema sobre quaisquer k caminhos mais longos, onde k é um inteiro maior que 2. Conjectura-se que a resposta para o caso k = 3 seja positiva, contudo, os resultados obtidos a este respeito são restritos a classes especiais de grafos, e ainda não são muitos. Pretendemos estudar o caso de três caminhos mais longos, cujos primeiros resultados apareceram na literatura há cerca de 15 anos.
ObjetivosEsperamos que o estudo do tema proposto permita-nos não apenas adquirir conhecimentos sobre o tema, mas principalmente aprender diversas técnicas de provas na área de grafos. A possibilidade de contribuir com resultados novos poderá ser explorada à medida que a maturidade e os conhecimentos adquiridos permitam isso. Será feita uma resenha sobre esse tema, abordando o caso de todos os caminhos mais longos, e o caso de quaisquer 3 caminhos mais longos. Essas questões serão investigadas mais em classes especiais de grafos, pois sabemos que a resposta para a primeira questão, no caso de grafos arbitrários, é negativa; e a segunda questão é um problema em aberto. Apresentaremos alguns resultados conhecidos e reproduziremos provas de alguns deles. Depois de adquirirmos mais conhecimento sobre esse assunto, pretendemos focar o problema em classes especiais de grafos.
Passos ImportantesNossos estudos serão baseados em leitura de teses e artigos sobre o tema. Inicialmente, estudaremos as seguintes teses/dissertações.
Adicionalmente, dentre outros, estudaremos os seguintes artigos.
Esses trabalhos apresentam o problema de maneira geral e resultados obtidos para determinadas classes especiais. Com isso, esperamos ter um repertório de diversos tipos de provas. Em conjunto com essas leituras, estudaremos propriedades específicas da classe dos grafos cúbicos.
[1] S. Mark, The Intersection of Longest Paths in a Graph, University of Canterbury , New Zealand,
2022.
[2] C. Strasser, Intersection of longest paths in connected graphs, Faculty of Technical Sciences, Áustria,
2021.
[3] S.F. de Rezende, Caminhos mais longos em grafos, Dissertação de Mestrado, Instituto de
Matemática e Estatística da Universidade de São Paulo, São Paulo, 2014.
[4] M.R. Cerioli, P.T. Lima, Intersection of longest paths in graph classes, Discrete Applied
Mathematics, Volume 281, 2020, Páginas 96-105, 2016.
[5] S.F. de Rezende, C.G. Fernandes, D.M. Martin, Y. Wakabayashi, Intersecting longest paths,
Discrete Mathematics, Volume 313, Issue 12, 1401-1408, 2013.
[6] M. Axenovich, When do three longest paths have a common vertex?, Discrete Mathematics,
Algorithms and Applications 1, 115-120, 2009