Busca avançada
Ano de início
Entree


All longest cycles in a 2-connected partial 3-tree share a common vertex

Texto completo
Autor(es):
Gutierrez, Juan
Número total de Autores: 1
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; v. 103, n. 4, p. 23-pg., 2023-03-01.
Resumo

In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. In this paper, we study the related question on longest cycles instead of longest paths (to make the question valid, we require 2-connectivity). The answer for cycles is also negative and not so much attention has been given to it. Classes for which the answer is known to be positive are dually chordal graphs and 3-trees. Perhaps the main open class for the question of both paths and cycles is the class of chordal graphs. In this paper, we show that all longest cycles intersect in graphs with treewidth at most three. This class of graphs includes several important subclasses of graphs, such as series-parallel graphs and K5 ${K}_{5}$-free chordal graphs. (AU)

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