Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2020.tde-10012020-200714
Document
Auteur
Nom complet
Juan Gabriel Gutierrez Alva
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2020
Directeur
Jury
Fernandes, Cristina Gomes (Président)
Botler, Fábio Happ
Campos, Christiane Neme
Martin, Daniel Morgato
Wakabayashi, Yoshiko
Titre en anglais
Transversals of graphs
Mots-clés en anglais
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Resumé en anglais
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.
Titre en anglais
Não consta
Mots-clés en anglais
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Resumé en anglais
Não consta

AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2020-02-07

AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2023. Tous droits réservés.