Nonempty intersection of longest paths in series-parallel graphs

Full text
Author(s):	Chen, Guantao ; Ehrenmuller, Julia ; Fernandes, Cristina G. ; Heise, Carl Georg ; Shan, Songling ; Yang, Ping ; Yates, Amy N. Total Authors: 7
Document type:	Journal article
Source:	DISCRETE MATHEMATICS; v. 340, n. 3, p. 287-304, MAR 2017.
Web of Science Citations:	6
Abstract
In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai's question is positive for several well-known classes of graphs, as for instance connected outerplanar graphs, connected split graphs, and 2-trees. A graph is series-parallel if it does not contain K-4 as a minor. Series-parallel graphs are also known as partial 2-trees, which are arbitrary subgraphs of 2-trees. We present two independent proofs that every connected series-parallel graph has a vertex that is common to all of its longest paths. Since 2-trees are maximal series-parallel graphs, and outerplanar graphs are also series-parallel, our result captures these two classes in one proof and strengthens them to a larger class of graphs. We also describe how one such vertex can be found in linear time. (C) 2016 Elsevier B.V. All rights reserved. (AU)

FAPESP's process:	13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
Grantee:	Carlos Eduardo Ferreira
Support Opportunities:	Research Projects - Thematic Grants