  The concentrations of dark matter haloes provide crucial information about
their internal structure and how it depends on mass and redshift -- the
so-called concentration-mass-redshift relation, denoted $c(M,z)$. We present
here an extensive study of the cosmology-dependence of $c(M,z)$ that is based
on a suite of 72 gravity-only, full N-body simulations in which the following
cosmological parameters were varied: $\sigma_{8}$, $\Omega_{\mathrm{M}}$,
$\Omega_{\mathrm{b}}$, $n_{\mathrm{s}}$, $h$, $M_{\nu}$, $w_{0}$ and
$w_{\mathrm{a}}$. We characterize the impact of these parameters on
concentrations for different halo masses and redshifts. In agreement with
previous works, and for all cosmologies studied, we find that there exists a
tight correlation between the characteristic densities of dark matter haloes
within their scale radii, $r_{-2}$, and the critical density of the Universe at
a suitably defined formation time. This finding, when combined with excursion
set modelling of halo formation histories, allows us to accurately predict the
concentrations of dark matter haloes as a function of mass, redshift, and
cosmology. We use our simulations to test the reliability of a number of
published models for predicting halo concentration and highlight when they
succeed or fail to reproduce the cosmological $c(M,z)$ relation.
