|Publisher DOI:||10.1016/j.disc.2016.07.023||Title:||Nonempty intersection of longest paths in series–parallel graphs||Language:||English||Authors:||Chen, Guantao
Fernandes, Cristina G.
Heise, Carl Georg
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.
|URI:||http://hdl.handle.net/11420/4169||ISSN:||1872-681X||Journal:||Discrete mathematics||Institute:||Mathematik E-10||Document Type:||Article|
|Appears in Collections:||Publications without fulltext|
Show full item record
checked on Jul 5, 2022
checked on Jun 30, 2022
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.