Curved manifolds with conserved Runge-Lenz vectors

van Holten’s algorithm is used to construct Runge-Lenz-type conserved quantities, induced by Killing tensors, on curved manifolds. For the generalized Taub-NUT metric, the most general external potential such that the combined system admits a conserved Runge-Lenz-type vector is found. In the multi-center case, the subclass of two-center metric exhibits a conserved Runge-Lenz-type scalar.