Verlagslink DOI: 10.1016/j.disc.2016.07.023
Titel: Nonempty intersection of longest paths in series–parallel graphs
Sprache: Englisch
Autor/Autorin: Chen, Guantao 
Ehrenmüller, Julia 
Fernandes, Cristina G. 
Heise, Carl Georg 
Shan, Songling 
Yang, Ping 
Yates, Amy N. 
Erscheinungs­datum: 2017
Verlag: Elsevier
Quellenangabe: Discrete Mathematics 3 (340): 287-304 (2017)
Zusammenfassung (englisch): 
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
Zeitschrift: Discrete mathematics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

107
Letzte Woche
1
Letzten Monat
3
checked on 06.10.2022

SCOPUSTM   
Zitate

12
Letzte Woche
0
Letzten Monat
0
checked on 30.06.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.