This work reports results on the recombination of hydrogen atoms on a graphite surface at 10 K obtained using a detailed semi-classical molecular dynamics method in connection with the use of recently proposed ab initio potential energy surfaces. The calculated recombination probabilities together with the vibrational distributions of the formed H-2 molecules obtained assuming that the surface reaction proceeds via the Eley-Rideal mechanism can have an impact on the chemistry of H-2 formation in interstellar space.