Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647678 | Discrete Mathematics | 2013 | 8 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Susanna F. de Rezende, Cristina G. Fernandes, Daniel M. Martin, Yoshiko Wakabayashi,