How many vertices must we delete from a graph so that it no longer contains a path \(P_k\) on \(k\) vertices? We explore this question for various special graphs (hypercubes, square lattice graphs) as well as for some general families.
Citation
Paul Erdés, Ralph Faudree, Edward T.Ordman, Cecil Rousseau, Richard Schelp. Blocking Sets for Paths of a Given Length[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 040. 65-78. .
