| Texto completo | |
| Autor(es): |
de Rezende, Susanna F.
[1]
;
Fernandes, Cristina G.
[1]
;
Martin, Daniel M.
[2]
;
Wakabayashi, Yoshiko
[1]
Número total de Autores: 4
|
| Afiliação do(s) autor(es): | [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
Número total de Afiliações: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE MATHEMATICS; v. 313, n. 12, p. 1401-1408, JUN 28 2013. |
| Citações Web of Science: | 7 |
| Resumo | |
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) | |
| Processo FAPESP: | 11/16348-0 - Caminhos mais longos em grafos |
| Beneficiário: | Susanna Figueiredo de Rezende |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |