Hitting all longest cycles in a graph
Resumo
Let lct(G) be the minimum size of a set of vertices that contains at least one vertex in every longest cycle of a graph G. We show that lct(G) = 1 if G is a 3-tree, and that lct(G) 2 if G is a 2-connected partial 3-tree. It is known that, in every 2-connected graph, every pair of longest cycles intersect each other in at least two vertices. A natural question asks whether all longest cycles have a vertex in common in 2-connected graphs. (If the graph is not 2-connected, two longest cycles can be disjoint.) This has in general a negative answer, as the Petersen's graph shows. However, there are some graph classes for which this question has a positive answer, such as classes containing only Hamiltonian graphs [Thomas and Yu 1994, Tutte 1956], and dually chordal graphs [Jobson et al. 2016]. In this paper we show that the class of 3-trees also has a positive answer to this question. Observe that 3-trees are not dually chordal graphs, as they are not clique-Helly graphs, so they are not included in the class addressed by Jobson et al. [Jobson et al. 2016].
