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

Gutiérrez J. · Journal of Graph Theory (2023) · DOI: 10.1002/jgt.22942

Resumen

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.

Instituciones: Universidad de Ingeniería y Tecnología