Transversals of Longest Cycles in Partial k-Trees and Chordal Graphs

12/27/2019

∙

by   Juan Gutiérrez, et al.

∙

0

∙

share

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, ω(G)-3} if G is chordal, where ω(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.