Tesis Doctoral
DOI
https://doi.org/10.11606/T.45.2020.tde-10012020-200714
Documento
Autor
Nombre completo
Juan Gabriel Gutierrez Alva
Dirección Electrónica
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2020
Director
Tribunal
Fernandes, Cristina Gomes (Presidente)
Botler, Fábio Happ
Campos, Christiane Neme
Martin, Daniel Morgato
Wakabayashi, Yoshiko
Título en inglés
Transversals of graphs
Palabras clave en inglés
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Resumen en inglés
The intention of this work is to study problems about transversals of graphs. A transversal of a graph is a set of vertices or edges that intersects every object of some type. We study three types of transversals: of longest paths, of longest cycles, and of triangles. For each such type of transversal, we show upper bounds on the minimum cardinality of a transversal in a given graph class. The problems we study here have a strong connection with two well-known questions in graph theory: Gallais question and Tuzas Conjecture. Gallai asked whether all longest paths in a connected graph intersect. In terms of transversals, Gallai was asking whether there is a transversal of longest paths of cardinality one. Although the answer to this question is negative, it is still open for several classes of graphs. One part of this work is as an attempt to solve Gallais question, and its corresponding analogous question for cycles, on important classes of graphs. In some of these classes we are able to solve the question and in others we present significant advances. Tuza conjectured whether the minimum cardinality of a transversal of triangles is at most twice the cardinality of a maximum packing of triangles, where a packing of triangles is a set of edge-disjoint triangles in a graph. This conjecture is still open and several related advances have been made in the literature. One part of this work is an attempt to solve Tuzas Conjecture for several classes of graphs. For some of these classes we prove the conjecture. For some other classes, the conjecture was already proved, so we show stronger results.
Título en inglés
Não consta
Palabras clave en inglés
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Resumen en inglés
Não consta

ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2020-02-07