Nonempty intersection of longest paths in series-parallel graphs

Autor(es)

Chen, Guantao ; Ehrenmuller, Julia ; Fernandes, Cristina G. ; Heise, Carl Georg ; Shan, Songling ; Yang, Ping ; Yates, Amy N.

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 340, n. 3, p. 287-304, MAR 2017.
• Citações Web of Science: 6

Resumo

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. (C) 2016 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático