DOI
https://doi.org/10.11606/T.45.2020.tde-10012020-200714
Documento
Autor
Nome completo
Juan Gabriel Gutierrez Alva
E-mail
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2020
Fernandes, Cristina Gomes (Presidente)
Botler, Fábio Happ
Campos, Christiane Neme
Martin, Daniel Morgato
Wakabayashi, Yoshiko
Título em inglês
Transversals of graphs
Palavras-chave em inglês
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Resumo em 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 em inglês
Não consta
Palavras-chave em inglês
Graph theory
Longest cycles
Longest paths
Packing
Transversal
Triangles
Resumo em inglês
Não consta

AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2020-02-07

AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI