Publisher DOI: 10.1016/j.disc.2016.07.023
Title: Nonempty intersection of longest paths in series–parallel graphs
Language: English
Authors: Chen, Guantao 
Ehrenmüller, Julia 
Fernandes, Cristina G. 
Heise, Carl Georg 
Shan, Songling 
Yang, Ping 
Yates, Amy N. 
Issue Date: 2017
Publisher: Elsevier
Source: Discrete Mathematics 3 (340): 287-304 (2017)
Abstract (english): 
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 K4 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.
ISSN: 1872-681X
Journal: Discrete mathematics 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 5, 2022


Last Week
Last month
checked on Jun 30, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.