Longest paths in graphs

Author(s)

Susanna Figueiredo De Rezende

• Document type: Master's Dissertation
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Defense date: 2014-05-30

Examining board members

Yoshiko Wakabayashi; Christiane Neme Campos; Daniel Morgato Martin

• Advisor: Yoshiko Wakabayashi

Abstract

The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature. (AU)

• FAPESP's process: 11/16348-0 - Longest paths in graphs
• Grantee: Susanna Figueiredo de Rezende
• Support Opportunities: Scholarships in Brazil - Master