The behavior of two interacting populations, ``hosts''and ``parasites'', is investigated on Cayley trees and scale-free networks. In the former case analytical and numerical arguments elucidate a phase diagram, whose most interesting feature is the absence of a tri-critical point as a function of the two independent spreading parameters. For scale-free graphs, the parasite population can be described effectively by Susceptible-Infected-Susceptible-type dynamics in a host background. This is shown both by considering the appropriate dynamical equations and by numerical simulations on Barab��si-Albert networks with the major implication that in the termodynamic limit the critical parasite spreading parameter vanishes.

10 pages, 6 figures, submitted to PRE; analytics redone, new calculations added, references added, appendix removed