Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Intersecting longest paths

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