  In 1993 van den Berg and Kesten proved a strict monotonicity theorem for
first passage percolation on $\mathbb{Z}^d$, $d \ge 2$: given two probability
measures $\nu$ and $\tilde{\nu}$ with finite mean, if $\tilde{\nu}$ is strictly
more variable than $\nu$ and $\nu$ is subcritical in an appropriate sense, the
time constant associated to $\tilde{\nu}$ is strictly smaller than the time
constant associated to $\nu$. In this paper, an analogous result is proven for
(not necessarily almost-transitive) graphs of strict polynomial growth and for
bounded degree graphs quasi-isometric to trees which satisfy a certain
geometric condition we call "admitting detours." It is also proven that if a
bounded degree graph does not admit detours, then such a strict monotonicity
theorem with respect to variability cannot hold. Large classes of graphs are
shown to admit detours, and we conclude that for example any Cayley graph of a
virtually nilpotent group which is not isomorphic to the standard Cayley graph
of $\mathbb{Z}$ satisfies strict monotonicity with respect to variability, as
does any Cayley graph of $F \rtimes F_k$, $F$ a nontrivial finite group and
$F_k$ a free group.
  Moreover, it is proven that for graphs of strict polynomial growth and
bounded degree graphs quasi-isometric to trees, if the weight measure is
subcritical in an appropriate sense, then it is "absolutely continuous with
respect to the expected empirical measure of the geodesic." This implies a
strict monotonicity theorem with respect to stochastic domination of measures,
whether or not the graph admits detours.
