Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2016.07.023 | Discrete Mathematics |
Field | DocType | Volume |
Discrete mathematics,Modular decomposition,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Cograph,Pathwidth,1-planar graph,Mathematics,Split graph | Journal | 340 |
Issue | ISSN | Citations |
3 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guantao Chen | 1 | 107 | 25.00 |
| Julia Ehrenmüller | 2 | 7 | 2.67 |
| Cristina G. Fernandes | 3 | 260 | 29.98 |
| Carl Georg Heise | 4 | 1 | 0.70 |
| Songling Shan | 5 | 20 | 9.16 |
| Ping Yang | 6 | 0 | 0.68 |
| Amy N. Yates | 7 | 0 | 0.34 |