TRANSVERSALS OF LONGEST PATHS AND CYCLES

Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G, and define lct(G) analogously for cycles instead of paths. We prove that lpt(G) <= inverted right perpendicularn/4 - n(2/3)/90inverted left perpendicular if G is connected, and lct(G) <= inverted right perpendicularn/3 - n(2/3)/36inverted left perpendicular if G is 2-connected. Our bound on lct(G) improves an earlier result of Thomassen. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.