Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Intersecting longest paths

Full text
de Rezende, Susanna F. [1] ; Fernandes, Cristina G. [1] ; Martin, Daniel M. [2] ; Wakabayashi, Yoshiko [1]
Total Authors: 4
[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[2] Univ Fed ABC, Ctr Matemat Comp & Cognicao, BR-09210170 Santo Andre, SP - Brazil
Total Affiliations: 2
Document type: Journal article
Source: DISCRETE MATHEMATICS; v. 313, n. 12, p. 1401-1408, JUN 28 2013.
Web of Science Citations: 7

In 1966, Gallai asked whether every connected graph has a vertex that is common to all longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs and 2-trees. Another related question was raised by Zamfirescu in the 1980s: Do any three longest paths in a connected graph have a vertex in common? The answer to this question is unknown. We prove that for connected graphs in which all nontrivial blocks are Hamiltonian the answer is affirmative. Finally, we state a conjecture and explain how it relates to the three longest paths question. (C) 2013 Elsevier B.V. All rights reserved. (AU)

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