  Graph-walking automata (GWA) traverse graphs by moving between the nodes
following the edges, using a finite-state control to decide where to go next.
It is known that every GWA can be transformed to a GWA that halts on every
input, to a GWA returning to the initial node in order to accept, and to a
reversible GWA. This paper establishes lower bounds on the state blow-up of
these transformations, as well as closely matching upper bounds. It is shown
that making an $n$-state GWA traversing $k$-ary graphs halt on every input
requires at most $2nk+1$ states and at least $2(n-1)(k-3)$ states in the worst
case; making a GWA return to the initial node before acceptance takes at most
$2nk+n$ and at least $2(n-1)(k-3)$ states in the worst case; Automata
satisfying both properties at once have at most $4nk+1$ and at least
$4(n-1)(k-3)$ states in the worst case. Reversible automata have at most
$4nk+1$ and at least $4(n-1)(k-3)-1$ states in the worst case.
