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

ransversals of longest cycles in partial k-trees and chordal graph

Texto completo
Autor(es):
Gutierrez, Juan [1]
Número total de Autores: 1
Afiliação do(s) autor(es):
[1] Univ Ingn & Tecnol UTEC, Dept Ciencia Computac, Jr Medrano Silva 165, Lima 15063 - Peru
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; v. 98, n. 4 JUL 2021.
Citações Web of Science: 0
Resumo

Let lct ( G ) be the minimum cardinality of a set of vertices that intersects every longest cycle of a 2-connected graph G. We show that lct ( G ) <= k - 1 if G is a partial k-tree and that lct ( G ) <= max [ 1 , omega ( G ) - 3 ] if G is chordal, where omega ( G ) is the cardinality of a maximum clique in G. Those results imply that all longest cycles intersect in 2-connected series-parallel graphs and in 3-trees. (AU)

Processo FAPESP: 15/08538-5 - Transversais em grafos
Beneficiário:Juan Gabriel Gutierrez Alva
Linha de fomento: Bolsas no Brasil - Doutorado