The relaxation of vibrational energy in the H and D stretch modes has been studied on the graphene surface using ab initio calculations. The dissipation of the vibrational energy stored in the stretching modes proceeds through vibration-phonon coupling, while the dissipation through electronic excitations makes only minor contributions. Recently, we reported the fast relaxation of the H stretch energy on graphene [S. Sakong and P. Kratzer, J. Chem. Phys. 133, 054505 (2010)]. Interestingly, we predict the lifetime of the D stretch to be markedly longer compared to the relaxation of the H stretch. This is unexpected since the vibrational amplitudes at carbon atoms in the joint C-D vibrational modes are larger than in the joint C-H modes, due to the mass ratio m(D)/m(C) > m(H)/m(C). However, the vibrational relaxation rate for the D stretch is smaller than for the H stretch, because the energy is dissipated to an acoustic phonon of graphene in the case of C-D rather than an optical phonon as is the case in C-H, and hence, the corresponding phonon density of states is lower in the C-D case. To rationalize our findings, we propose a general scheme for estimating vibrational lifetimes of adsorbates based on four factors: the density of states of the phonons that mediates the transitions, the vibration-phonon coupling strength, the anharmonic coupling between local modes, and the number of quanta involved in the transitions. Mainly the first two of these factors are responsible for the differences in the lifetimes of the C-H and C-D stretches. The possible role of the other factors is illustrated in the context of vibrational lifetimes in other recently studied systems.