Intersection of Longest Paths in a Graph
De Rezende, Susanna F. LU
; Fernandes, Cristina G.
; Martin, Daniel M.
and Wakabayashi, Yoshiko
(2011)
Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011
In Electronic Notes in Discrete Mathematics
38.
p.743-748
- Abstract
In 1966, Gallai asked whether every connected graph has a vertex that is common to all its longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs. Another related question was raised in 1995 at the British Combinatorial Conference: Do any three longest paths in a connected graph have a vertex in common? We prove that, in a connected graph in which all non-trivial blocks are Hamiltonian, any three of its longest paths have a common vertex. Both of these results strengthen a recent result by Axenovich.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/d5b4d61a-a451-40a2-aa49-2d092ff290aa
- author
- De Rezende, Susanna F.
LU
; Fernandes, Cristina G.
; Martin, Daniel M.
and Wakabayashi, Yoshiko
- publishing date
- 2011-12-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Intersection of longest paths, Longest path, Outerplanar graph
- in
- Electronic Notes in Discrete Mathematics
- volume
- 38
- pages
- 6 pages
- publisher
- Elsevier
- conference name
- Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011
- conference location
- Budapest, Hungary
- conference dates
- 2011-08-29 - 2011-09-02
- external identifiers
-
- scopus:82955242515
- ISSN
- 1571-0653
- DOI
- 10.1016/j.endm.2011.10.024
- language
- English
- LU publication?
- no
- id
- d5b4d61a-a451-40a2-aa49-2d092ff290aa
- date added to LUP
- 2021-12-17 13:37:18
- date last changed
- 2022-02-02 02:13:59
@article{d5b4d61a-a451-40a2-aa49-2d092ff290aa,
abstract = {{<p>In 1966, Gallai asked whether every connected graph has a vertex that is common to all its longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs. Another related question was raised in 1995 at the British Combinatorial Conference: Do any three longest paths in a connected graph have a vertex in common? We prove that, in a connected graph in which all non-trivial blocks are Hamiltonian, any three of its longest paths have a common vertex. Both of these results strengthen a recent result by Axenovich.</p>}},
author = {{De Rezende, Susanna F. and Fernandes, Cristina G. and Martin, Daniel M. and Wakabayashi, Yoshiko}},
issn = {{1571-0653}},
keywords = {{Intersection of longest paths; Longest path; Outerplanar graph}},
language = {{eng}},
month = {{12}},
pages = {{743--748}},
publisher = {{Elsevier}},
series = {{Electronic Notes in Discrete Mathematics}},
title = {{Intersection of Longest Paths in a Graph}},
url = {{http://dx.doi.org/10.1016/j.endm.2011.10.024}},
doi = {{10.1016/j.endm.2011.10.024}},
volume = {{38}},
year = {{2011}},
}