Interseção de Caminhos Mais Longos em Grafos

Em 1966, T. Gallai propôs o problema de determinar se a interseção de todos os caminhos mais longos de um grafo é não vazia. Uma forma mais geral de abordar o problema é determinar o tamanho do menor subconjunto de vértices cuja interseção com qualquer caminho mais longo do grafo é não vazia. Para um grafo G, o tamanho deste subconjunto é denotado por lpt(G). Se C é uma classe de grafos e lpt(G) = 1 para todo G ? C, dizemos que a classe responde positivamente à pergunta de Gallai. Uma variação deste problema consiste em considerar um número ?xo de caminhos mais longos. Esta dissertação apresenta uma coletânea de resultados importantes sobre o assunto, principalmente sobre a interseção de todos os caminhos mais longos ou de um número ?xo deles em algumas classes especí?cas de grafos. Nossa principal contribuição foi a de determinar novas classes de grafos que respondem positivamente à pergunta de Gallai, como os grafos cadeia, P4-esparsos, estrelados, (2K2,C4)-free, ptolemaicos e (P5,K1,3)-free, assim como grafos que são obtidos através da operação de join de dois outros grafos e grafos cujos componentes biconvexos são split, de intervalo ou possuem um vértice universal. Também fornecemos limites superiores para lpt(G) nas classes 2K2-free, (P5,criquet)-free e para grafos de interseção de subárvores de uma estrela estendida.