  Motivated by the experimentally observed high mobility of gold atoms on
graphene and their tendency to form nanometer-sized clusters, we present a
density functional theory study of the ground state structures of small gold
clusters on graphene, their mobility and clustering. Our detailed analysis of
the electronic structures identifies the opportunity to form strong gold-gold
bonds and the graphene mediated interaction of the pre-adsorbed fragments as
the driving forces behind gold's tendency to aggregate on graphene. While
clusters containing up to three gold atoms have one unambiguous ground state
structure, both gas phase isomers of a cluster with four gold atoms can be
found on graphene. In the gas phase the diamond shaped Au$_{4}^{D}$ cluster is
the ground state structure, whereas the Y shaped Au$_{4}^{Y}$ becomes the
actual ground state when adsorbed on graphene. As we show, both clusters can be
produced on graphene by two distinct clustering processes. We also studied in
detail the stepwise formation of a gold dimer out of two pre-adsorbed adatoms,
as well as the formation of Au$_{3}$. All reactions are exothermic and no
further activation barriers, apart from the diffusion barriers, were found. The
diffusion barriers of all studied clusters range from 4 to 36 meV, only, and
are substantially exceeded by the adsorption energies of -0.1 to -0.59 eV. This
explains the high mobility of Au$_{1-4}$ on graphene along the C-C bonds.
