Nonempty Intersection of Longest Paths in Series-Parallel Graphs
| Autor: | Ehrenmüller, Julia, Fernandes, Cristina G., Heise, Carl Georg |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Discrete Mathematics 340/3 (2017) 287-304 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.disc.2016.07.023 |
| Popis: | 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 a proof 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 this vertex can be found in linear time. Comment: 17 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|