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

2019/12/27 by Gutiérrez, Juan
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1912.12230

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)≤ 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.

Related

• Transversals of Longest Paths
• Transversals of Longest Paths and Cycles
• Intersecting longest paths in chordal graphs
• All longest cycles intersect in partial 3-trees
• Longest Path and Cycle Transversals in Chordal Graphs