We study the influence of network topology on retrieval properties of recurrent neural networks, using replica techniques for dilute systems. The theory is presented for a network with an arbitrary degree distribution p(k) and applied to power-law distributions p(k) ∼ k^−γ, i.e. to neural networks on scale-free graphs. A bifurcation analysis identifies phase boundaries between the paramagnetic phase and either a retrieval phase or a spin-glass phase. Using a population dynamics algorithm, the retrieval overlap and spin-glass order parameters may be calculated throughout the phase diagram. It is shown that there is an enhancement of the retrieval properties compared with a Poissonian random graph. We compare our findings with simulations.