Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Transversals of longest paths

Full text
Author(s):
Cerioli, Marcia R. [1, 2] ; Fernandes, Cristina G. [3] ; Gomez, Renzo [3] ; Gutierrez, Juan [3] ; Lima, Paloma T. [4]
Total Authors: 5
Affiliation:
[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
Total Affiliations: 4
Document type: Journal article
Source: DISCRETE MATHEMATICS; v. 343, n. 3 MAR 2020.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
Grantee:Carlos Eduardo Ferreira
Support type: Research Projects - Thematic Grants
FAPESP's process: 15/08538-5 - Graph transversals
Grantee:Juan Gabriel Gutierrez Alva
Support type: Scholarships in Brazil - Doctorate