An $r$-labeling of graph $G$ is a function $\Phi: V(G) \mapsto \{1,2,\hdots, r\}$. In 1996, Albertson and Collins introduced the following class of labelings. Suppose $G$ is labeled by $\Phi$. Let $(G,\Phi)$ denote the labeled version of $G$. The labeling $\Phi$ is said to be {\em distinguishing} if the only label-preserving automorphism of $(G,\Phi)$ is the identity map. The distinguishing number of $G$, $D(G)$, is the minimum number of colors needed so that $G$ has a distinguishing labeling. The complexity of the problem ``Is $D(G) \leq k$?'' is as difficult as the Graph Automorphism Problem when $k = 1$ and may or may not be in NP nor co-NP when $k \ge 2$.

In this talk, we will present a polynomial-time algorithm that solves for the distinguishing numbers of trees and forests exactly. We will discuss a generalization of distinguishing labelings and numbers called {\em $i$-local distinguishing labelings and numbers} of a graph. If $v$ is a vertex in $G$, let $N_v^i$ denote the induced subgraph of $G$ that contains all the vertices that are at most distance $i$ away from $v$ and has $v$ as its root. A labeling, $\Phi$, is {\em $i$-local distinguishing} if for every pair of vertices $(u,v)$ in $G$, the labeled versions of $N_u^i$ and $N_v^i$ are non-isomorphic. We note that $i$-local distinguishing labelings are distinguishing labelings too for all $i \ge 1$. We provide good upper bounds for the $i$-local distinguishing numbers of cycles and trees when $i \ge 1$ and $n$ is sufficiently large. We also give an upper bound for the $1$-local distinguishing numbers of almost all graphs.
(This is joint work with Prof. Lenore Cowen, Johns Hopkins University.)