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

Abstract

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)\le k-1$ if $G$ is a partial $k$-tree and that $lct(G)\le \max \{1,\omega (G)-3\}$ if $G$ is chordal, where $\omega (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.

References in corpus (1)

• Nonempty Intersection of Longest Paths in Series-Parallel Graphs