The problem of intersection of longest paths in graph classes

• Grant number: 12/10252-4
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2012
• End date: July 31, 2013
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Christiane Neme Campos
• Grantee: Vitor Roberto de Almeida Castro
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

This undergraduate research project aims at introducing the student to Graph Theory research, through the study of the conjecture which states that any three longest paths in a connected graph have a vertex in common. This problem was motivated by a question of T. Gallai in 1968 and touches on important aspects of Graph Theory, such as connectivity and structures of paths. The focus of this project is to study some of the consequences of the conjecture and investigate its validity for some classes of graphs.(AU)