Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Nonempty intersection of longest paths in series-parallel graphs

Texto completo
Autor(es):
Chen, Guantao ; Ehrenmuller, Julia ; Fernandes, Cristina G. ; Heise, Carl Georg ; Shan, Songling ; Yang, Ping ; Yates, Amy N.
Número total de Autores: 7
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
Linha de fomento: Auxílio à Pesquisa - Temático