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

Producción científica: Contribución a una revistaArtículorevisión exhaustiva


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 (Formula presented.) -free chordal graphs.

Idioma originalInglés
Páginas (desde-hasta)690-712
Número de páginas23
PublicaciónJournal of Graph Theory
EstadoPublicada - ago. 2023


Profundice en los temas de investigación de 'All longest cycles in a 2-connected partial 3-tree share a common vertex'. En conjunto forman una huella única.

Citar esto