Title: Transversals of longest paths in cubic graphs
Student: Heloisa de Lazari Bento
Advisor: Yoshiko Wakabayashi

Data: segunda-feira, 26 de maio de 2025
Time: 12h
Place: Auditório Jacy Monteiro - Bloco B e via meet (https://meet.google.com/her-ujff-tob)

Abstract: The central topic of this master’s thesis proposal is the study of transversals
of longest paths in graphs. A transversal of longest paths of a graph G is a set of vertices S ⊆ V (G) such that S intersects every longest path of G. Given a connected graph G, we are interested in the size of a smallest transversal of longest paths of G, a parameter denoted here lpt(G). Extensive research on the parameter lpt(G) has been conducted for special graph classes of graphs G, either proving that lpt(G) = 1 or proving bounds for lpt(G). It has been proved that lpt(G) = 1 for graphs G in a number of special graph classes, but it is not known whether cubic graphs have this property. This motivated our studies on the class of cubic graphs, with special emphasis on the class of polycyclic cubic Halin graphs. Besides studying this class, we are also interested in operations to generate cubic graphs from other cubic graphs (or on the same graph) that preserve the value of the parameter lpt. We also plan to present some known results in the literature on bounds for lpt(G) when G is an arbitrary graph.