Transversals of longest paths in graphs

• Grant number: 23/14346-8
• Support Opportunities: Scholarships in Brazil - Master
• Start date: February 01, 2024
• End date: January 31, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiko Wakabayashi
• Grantee: Heloisa de Lazari Bento
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

This project falls within the area of graph theory. It concerns the investigation of problems on longest paths in graphs, with emphasis on the study of minimal transversals of these objects. In a connected graph, a set of vertices that intersects each longest path of this graph is called a transversal (of longest paths). It is known that not all graphs have transversals of cardinality 1. We are interested in studying certain classes of graphs and determine upper bounds for their minimum transversals. Other variants of this problem (restricted to a fixed number of longest paths) will also be investigated.