Intersecting longest paths
De Rezende, Susanna F. LU
; Fernandes, Cristina G.
; Martin, Daniel M.
and Wakabayashi, Yoshiko
(2013)
In Discrete Mathematics
313(12).
p.1401-1408
- 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/f870c7c5-5274-4bd7-8a9e-918a5deda77c
- author
- De Rezende, Susanna F.
LU
; Fernandes, Cristina G.
; Martin, Daniel M.
and Wakabayashi, Yoshiko
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Intersection of longest paths, Longest path, Outerplanar graph 2-tree
- in
- Discrete Mathematics
- volume
- 313
- issue
- 12
- pages
- 8 pages
- publisher
- Elsevier
- external identifiers
-
- scopus:84875699858
- ISSN
- 0012-365X
- DOI
- 10.1016/j.disc.2013.02.016
- language
- English
- LU publication?
- no
- additional info
- Funding Information: This research was partially supported by CNPq ( Proc. 123740/2010-0 , 308523/2012-1 , 303987/2010-3 and 477203/2012-4 ), FAPESP ( Proc. 2011/16348-0 ) and Project MaCLinC of NUMEC/USP.
- id
- f870c7c5-5274-4bd7-8a9e-918a5deda77c
- date added to LUP
- 2021-12-17 13:32:14
- date last changed
- 2022-04-11 22:21:58
@article{f870c7c5-5274-4bd7-8a9e-918a5deda77c,
abstract = {{<p>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.</p>}},
author = {{De Rezende, Susanna F. and Fernandes, Cristina G. and Martin, Daniel M. and Wakabayashi, Yoshiko}},
issn = {{0012-365X}},
keywords = {{Intersection of longest paths; Longest path; Outerplanar graph 2-tree}},
language = {{eng}},
number = {{12}},
pages = {{1401--1408}},
publisher = {{Elsevier}},
series = {{Discrete Mathematics}},
title = {{Intersecting longest paths}},
url = {{http://dx.doi.org/10.1016/j.disc.2013.02.016}},
doi = {{10.1016/j.disc.2013.02.016}},
volume = {{313}},
year = {{2013}},
}