Advanced search
Start date
Betweenand

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.

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