  Graph-walking automata (GWA) are a model for graph traversal using
finite-state control: these automata move between the nodes of an input graph,
following its edges. This paper investigates the effect of node-replacement
graph homomorphisms on recognizability by these automata. It is not difficult
to see that the family of graph languages recognized by GWA is closed under
inverse homomorphisms. The main result of this paper is that, for $n$-state
automata operating on graphs with $k$ labels of edge end-points, the inverse
homomorphic images require GWA with $kn+O(1)$ states in the worst case. The
second result is that already for tree-walking automata, the family they
recognize is not closed under injective homomorphisms. Here the proof is based
on an easy homomorphic characterization of regular tree languages.
