| Texto completo | |
| Autor(es): |
Gutierrez, Juan
;
Bender, MA
;
FarachColton, M
;
Mosteiro, MA
Número total de Autores: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | LATIN 2018: THEORETICAL INFORMATICS; v. 10807, p. 14-pg., 2018-01-01. |
| Resumo | |
Let lct(G) be the minimum size of a set of vertices that intersects every longest cycle of a 2-connected graph G. Let tw(G) be the tree-width of G and omega (G) be the size of a maximum clique in G. We show that lct(G) <= tw(G)-1 for every G, and that lct(G) <= max{1, omega(G)-3} if G is chordal. Those results imply as corollaries that all longest cycles intersect in 2-connected series-parallel graphs and in 3-trees. We also strengthen the latter result and show that all longest cycles intersect in 2-connected graphs of tree-width at most 3, also known as partial 3-trees. (AU) | |
| Processo FAPESP: | 15/08538-5 - Transversais em grafos |
| Beneficiário: | Juan Gabriel Gutierrez Alva |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |