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.)

Transversals of longest paths

Texto completo
Autor(es):
Cerioli, Marcia R. [1, 2] ; Fernandes, Cristina G. [3] ; Gomez, Renzo [3] ; Gutierrez, Juan [3] ; Lima, Paloma T. [4]
Número total de Autores: 5
Afiliação do(s) autor(es):
[1] Univ Fed Rio de Janeiro, Inst Matemat, Rio De Janeiro - Brazil
[2] Univ Fed Rio de Janeiro, COPPE Sistemas, Rio De Janeiro - Brazil
[3] Univ Sao Paulo, Dept Ciencia Comp, Sao Paulo - Brazil
[4] Univ Bergen, Dept Informat, Bergen - Norway
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: DISCRETE MATHEMATICS; v. 343, n. 3 MAR 2020.
Citações Web of Science: 0
Resumo

Let lpt(G) be the minimum cardinality of a transversal of longest paths in G, that is, a set of vertices that intersects all longest paths in a graph G. There are several results in the literature bounding the value of lpt(G) in general or in specific classes of graphs. For instance, lpt(G) = 1 if G is a connected partial 2-tree, and a connected partial 3-tree G is known with lpt(G) = 2. We prove that lpt(G) <= 3 for every connected partial 3-tree G; that lpt(G) <= 2 for every planar 3-tree G; and that lpt(G) = 1 if G is a connected bipartite permutation graph or a connected full substar graph. Our first two results can be adapted for broader classes, improving slightly some known general results: we prove that lpt(G) <= k for every connected partial k-tree G and that lpt(G) <= max[1, omega(G) - 2] for every connected chordal graph G, where omega(G) is the cardinality of a maximum clique in G. (C) 2019 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
Processo FAPESP: 15/08538-5 - Transversais em grafos
Beneficiário:Juan Gabriel Gutierrez Alva
Linha de fomento: Bolsas no Brasil - Doutorado