By virtue of periodic density functional theory, we investigate structure and thermodynamic stability of (VO)k and (VO2)k (k = 1, 2, 3) clusters deposited on the CeO2(111) surface, which serve as models for the very active sub-monolayer vanadia catalyst on a ceria support. We find V always completely oxidized (oxidation state +5) and coordinated to four O atoms. As a consequence, Ce4+ is (partially) reduced to Ce3+. Thus, localized Ce-4f states are populated, which requires an onsite U-term (PBE+U) to avoid over-delocalization off-electrons. Importantly, trimers of VO2 were found to be extraordinarily stable (agglomeration energy: -1.68 eV), whereas aggregation of VO species on CeO2(111) is thermodynamically clearly unfavourable (agglomeration energy: 3.45 eV). As a consequence a large area of the VnOm phase diagram (for relevant temperatures) is dominated by the VO2 trimer. The latter is less active towards reduction/oxidation than the active monomer and dimer of VO2, which are not present in the phase diagram at all, although directly observed by recent STM measurements. This suggests that kinetic effects hinder VO2 to grow into larger oligomers. The lowest migration energy barrier we found is as high as 1.95 eV, which indicates that adsorbed monomeric VO2 is "kinetically locked" at low temperatures and explains why monomers are stabilized on the ceria surface.