The problem of intersection of longest paths in graph classes
Platform for bioprospecting the mechanism of action of antimicrobial molecules: pr...
Macrophages and T lymphocytes immunometabolism in metabolic and inflammatory diseases
| Full text | |
| Author(s): |
de Rezende, Susanna F.
[1]
;
Fernandes, Cristina G.
[1]
;
Martin, Daniel M.
[2]
;
Wakabayashi, Yoshiko
[1]
Total Authors: 4
|
| Affiliation: | [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 |
| Abstract | |
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 |