Advanced search
Start date

Transversals of longest paths in graphs

Grant number: 23/14346-8
Support Opportunities:Scholarships in Brazil - Master
Effective date (Start): February 01, 2024
Effective date (End): 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


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.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list using this form.