Doctoral Thesis
DOI
https://doi.org/10.11606/T.45.2020.tde-10012020-200714
Document
Author
Full name
Juan Gabriel Gutierrez Alva
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2020
Supervisor
Committee
Fernandes, Cristina Gomes (President)
Botler, Fábio Happ
Campos, Christiane Neme
Martin, Daniel Morgato
Wakabayashi, Yoshiko
Title in English
Transversals of graphs
Keywords in English
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Abstract in English
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.
Title in English
Não consta
Keywords in English
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Abstract in English
Não consta

WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2020-02-07

WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI