Back to Search
Start Over
Nonempty intersection of longest paths in series–parallel graphs.
- Source :
-
Discrete Mathematics . Mar2017, Vol. 340 Issue 3, p287-304. 18p. - Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 340
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 120320667
- Full Text :
- https://doi.org/10.1016/j.disc.2016.07.023