\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac2{{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Michael O. Albertson}
%
%
\medskip
\noindent
%
%
{\bf Distinguishing Cartesian Powers of Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
Given a graph $G$, a labeling $c:V(G) \rightarrow \{1, 2, \ldots, d\}$
is said to be {\it $d$-distinguishing} if the only element in ${\rm
Aut}(G)$ that preserves the labels is the identity.  The {\it
distinguishing number} of $G$, denoted by $D(G)$, is the minimum $d$
such that $G$ has a $d$-distinguishing labeling. If $G \square H$ denotes
the Cartesian product of $G$ and $H$, let $G^{^2} = G \square G$ and
$G^{^r} = G \square G^{^{r-1}}$. A graph $G$ is said to be {\it prime}
with respect to the Cartesian product if whenever $G \cong G_1 \square
G_2$, then either $G_1$ or $G_2$ is a singleton vertex.  This paper
proves that if $G$ is a connected, prime graph, then $D(G^{^r}) = 2$
whenever $r \geq 4$.

\bye

.
