Characterization of randomly k-dimensional graphs