Let $G=(V,E)$ be a graph modeling a network in which each edge is owned
by a selfish agent, which establishes the cost for traversing its
edge (i.e., assigns a weight to its edge) by pursuing only its
personal utility. In such a setting, we aim at designing approximate
truthful mechanisms for several NP-hard traversal problems
on $G$, such as the graphical traveling salesman problem, the
rural postman problem, and the mixed Chinese postman
problem, each of which in general requires an edge of $G$ to be used several
times. Thus, in game-theoretic terms, these are
one-parameter problems, but with a peculiarity: the workload of
each agent is a natural number. In this paper we refine the classical
notion of monotonicity of an algorithm so as to capture exactly this
property, and we then provide a general mechanism-design technique
that guarantees this monotonicity and that allows one to compute
efficiently the corresponding payments. In this way, we show that
the former two problems and the latter one admit a $3/2$- and a
$2$-approximate truthful mechanism, respectively. Thus, for the first
two problems we match the best known approximation ratios holding
for their corresponding centralized versions, while for the third
one we are only a $4/3$-factor away from it.