Metal oxide clusters of sub-nm dimensions dispersed on a metal oxide support are an important class of catalytic materials for a number of key chemical reactions, showing enhanced reactivity over the corresponding bulk oxide. In this paper we present the results of a density functional theory study of small sub-nm TiO2 clusters, Ti2O4, Ti3O6 and Ti4O8 supported on the rutile (110) surface. We find that all three clusters adsorb strongly with adsorption energies ranging from -3 eV to -4.5 eV. The more stable adsorption structures show a larger number of new Ti-O bonds formed between the cluster and the surface. These new bonds increase the coordination of cluster Ti and O as well as surface oxygen, so that each has more neighbours. The electronic structure shows that the top of the valence band is made up of cluster derived states, while the conduction band is made up of Ti 3d states from the surface, resulting in a reduction of the effective band gap and spatial separation of electrons and holes after photon absorption, which shows their potential utility in photocatalysis. To examine reactivity, we study the formation of oxygen vacancies in the cluster-support system. The most stable oxygen vacancy sites on the cluster show formation energies that are significantly lower than in bulk TiO2, demonstrating the usefulness of this composite system for redox catalysis.