How many vertices must we delete from a graph so that it no longer contains a path Pk on k vertices? We explore this question for various special graphs (hypercubes, square lattice graphs) as well as for some general families.
