Full text
| |
| Author(s): |
Juan Gabriel Gutierrez Alva
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | São Paulo. |
| Institution: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Defense date: | 2018-12-20 |
| Examining board members: |
Cristina Gomes Fernandes;
Fábio Happ Botler;
Christiane Neme Campos;
Daniel Morgato Martin;
Yoshiko Wakabayashi
|
| Advisor: | Cristina Gomes Fernandes |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 15/08538-5 - Graph transversals |
| Grantee: | Juan Gabriel Gutierrez Alva |
| Support Opportunities: | Scholarships in Brazil - Doctorate |