  The automorphism group of the composition of graphs $G \circ H$ contains the
wreath product $Aut(H) \wr Aut(G)$ of the automorphism groups of the
corresponding graphs. The classical problem considered by Sabidussi and
Hemminger was under what conditions $G \circ H$ has no other automorphisms. In
this paper we deal with the converse. If the automorphism group of a graph (or
a colored graph or digraph) is the wreath product $A \wr B$ of permutation
groups, then the graph must be the result of the corresponding construction.
The question we consider is whether $A$ and $B$ must be the automorphism groups
of graphs involved in the construction. We solve this problem, generally in
positive, for the wreath product in its natural imprimitive action (which
refers to the results by Sabidussi and Hemminger). Yet, we consider also the
same problems for the wreath product in its product action, which turns out to
be more complicated and leads to interesting open questions involving other
combinatorial structures.
