| 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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 15/08538-5 - Transversais em grafos |
| Beneficiário: | Juan Gabriel Gutierrez Alva |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |