\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm,amssymb,amsfonts,amsmath}

\usepackage{graphicx}

\usepackage{xspace,algorithmic,algorithm,verbatim}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\newcommand{\proc}[1]{\mbox{\sc #1}}
\newcommand{\NP}{{\rm NP}\xspace}
\newcommand{\AM}{{\rm AM}\xspace}
\newcommand{\Aut}{{\rm Aut}}

\title{\bf Distinguishing trees in linear time}

\author{Antoni Lozano\thanks{Antoni Lozano is supported by
projects MTM2011-28800-C02-01 and BASMATI, Biological and Social
Mining: Algorithms, Theory, and Implementation
TIN2011-27479-C04-03.}\\
\small Dpt. Llenguatges i Sistemes Inform\`atics\\[-0.8ex]
\small Universitat Polit\`ecnica de Catalunya\\[-0.8ex]
\small Barcelona, Spain\\
\small\tt antoni@lsi.upc.edu\\
\and Merc\`e Mora\thanks{Merc\`e Mora and Carlos Seara are
partially supported by projects MTM2009-07242, Gen Cat
DGR2009GR1040, and the ESF EUROCORES programme EuroGIGA-ComPoSe
IP04-MICINN Project
EUI-EURC-2011-4306.} \qquad Carlos Seara\\
\small Dpt. Matem\`atica Aplicada II\\[-0.8ex]
\small Universitat Polit\`ecnica de Catalunya\\[-0.8ex]
\small Barcelona, Spain\\
\small\tt \{merce.mora, carlos.seara\}@upc.edu}

\date{\dateline{April 15, 2011}{April 12, 2012}\\
\small Mathematics Subject Classifications: 05C85, 68R05, 05C15,
05C78}

\begin{document}

\maketitle

\begin{abstract}
A graph is said to be $d$-\emph{distinguishable} if there exists a
$d$-labeling of its vertices which is only preserved by the
identity map. The \emph{distinguishing number} of a graph $G$ is
the smallest number $d$ for which $G$ is $d$-distinguishable. We
show that the distinguishing number of trees and forests can be
computed in linear time, improving the previously known ${\cal
O}(n\log n)$ time algorithm.
\end{abstract}

\section{Introduction}\label{sec:int}

Let $G$ be a connected graph with $n$ vertices\footnote{Graphs in
this paper are finite, undirected and simple. The vertex-set and
the edge-set of a graph $G$ are denoted by $V(G)$ and $E(G)$,
respectively. The order of $G$ is the number of its vertices,
denoted by $|V(G)|$. For more terminology we follow~\cite{W}.}. A
$d$-labeling of $G$ is a total function $\phi: V(G)
\longrightarrow \{1,2,\dots,d\}$. We say that $\phi$
\emph{distinguishes} $G$ if $G$ has no label-preserving
automorphism different from the identity map. In this case, we say
that $\phi$ is a \emph{distinguishing $d$-labeling} of $G$. Such a
labeling is said to break or destroy the symmetries of $G$. The
\emph{distinguishing number} of $G$, $D(G)$, is the minimum number
$d$ of labels needed so that $G$ has a distinguishing
$d$-labeling. A graph $G$ having a distinguishing $d$-labeling is
said to be \emph{$d$-distinguishable}.

Distinguishing numbers were first introduced by Albertson and
Collins~\cite{AC}. The parameter can be thought of as a measure of
the symmetry of a graph, i.e., if $G$ and $G'$ have the same
number of vertices but $D(G)>D(G')$, then $G$ is more symmetric
than $G'$ because more colors are needed to destroy its
automorphisms than those of $G'$.

It is not known if the problem of computing $D(G)$ is
polynomially-time solvable or \NP-hard. Russell and
Sundaram~\cite{RS} showed that determining if $D(G)>d$ belongs to
the class \AM, i.e., the set of languages for which there are
Arthur-Merlin games. However, when $G$ is restricted to certain
graph families such as cycles, hypercubes, acyclic graphs, and
planar graphs, the problem can be solved
efficiently~\cite{AC,AD,ACD,BC,Cha,Che}.
See~\cite{A,ACD,Cha1,Cha2,Che1,IK,IJK,KZ,T} for other works on
distinguishing number problems.

For the computation of the distinguishing number of trees and
forests with $n$ vertices, Cheng~\cite{Che} and Arvind and
Devanur~\cite{AD} presented an ${\cal O}(n\log n)$ time algorithm
which uses a binary search to compute the distinguishing number of
a tree. Improving this time complexity was our main motivation for
the design of an optimal linear-time algorithm for computing the
distinguishing number of trees and forests, and this is the main
result of our paper.

In Section~\ref{sec:rooted} we will focus on the design of a
linear time algorithm for rooted trees which is based on
properties proved by Cheng~\cite{Che} and follow her notation
whenever possible. As a consequence of our result, we show in
Section~\ref{sec:forest} that there are linear-time algorithms for
computing the distinguishing numbers of trees and forests.
Finally, in Section~\ref{sec:applications} we conjecture
logarithmic factor improvements for other graph classes.

\section{Distinguishing Rooted Trees}\label{sec:rooted}

\subsection{Preliminaries}\label{subsec:pre}

We start with some notation. By $\Aut(G)$ we denote the
automorphism group of a graph $G$. As usual, two graphs $G$ and
$H$ are \emph{isomorphic}, denoted by $G \cong H$, if there is a
permutation $\pi:V(G) \rightarrow V(H)$ which preserves
adjacencies, that is, $\{u,v\}\in E(G)$ if and only if
$\{\pi(u),\pi(v)\} \in E(H)$ for any $u,v \in V(G)$.

Given a graph $G$ and a labeling $\phi$ of $G$, we represent the
corresponding labeled graph by $(G,\phi)$. In this case,
$\Aut(G,\phi)$ consists of all the automorphisms of $\Aut(G)$
which preserve the labeling $\phi$, that is, $\pi\in \Aut(G,\phi)$
if and only if $\phi\in \Aut(G)$ and $\phi(v) = \phi(\pi(v))$. We
also consider the extension of isomorphism to labeled graphs.
Given two labeled graphs $(G,\phi)$ and $(H,\varphi)$, we say that
they are isomorphic if there is a permutation $\pi:V(G)
\rightarrow V(H)$ which preserves adjacencies as defined above,
but also preserves labels, that is, $\phi(v) = \varphi(\pi(v))$
for each $v\in V(G)$. In this case, we write $(G,\phi) \cong
(H,\varphi)$. Two distinguishing $d$-labelings $\phi$ and
$\varphi$ of a graph $G$ are said to be {\em equivalent} if
$(G,\phi) \cong (G,\varphi)$.

Given a rooted tree $T$, we denote its root by $r(T)$. We also
denote by $T_u$ the subtree of $T$ rooted at vertex $u$ of $T$,
and we call \emph{components} of $T$ to all the subtrees $T_u$ of
$T$ where $u$ is a child of $r(T)$. Any isomorphism between two
rooted trees $T_1$ and $T_2$ must map $r(T_1)$ into $r(T_2)$. In
the same way, any automorphism of a rooted tree must map the root
into itself.

As we will see, the distinguishing number of a rooted tree can be
computed using a recursive formula. Call $D(T,d)$ to the number of
inequivalent distinguishing $d$-labelings of a rooted tree $T$.
For instance, if $T$ is a rooted tree consisting of a single path
of $k$ vertices, then $D(T,d)=d^k$, but if $T$ is a full binary
tree of (any) depth $k$, then $D(T,2)$ is just $2$ since we can
assign two possible labels to the root while the rest of the tree
has a unique distinguishing $2$-labeling up to isomorphism.
Clearly, for any graph $G$,
\[D(G) = \min\{d \mid D(G,d) > 0\},\]
and, therefore, computing $D(T,d)$ for any $d$ is all that is
needed to compute $D(T)$ for a rooted tree $T$. We also observe
the following relation between $D(T)$ and $D(T,d)$.

\begin{proposition}\label{prop:labels}
For any rooted tree $T$ and for any $d \ge D(T)$, it holds $D(T,d)
\ge d$.
\end{proposition}

\begin{proof}
For any $d\ge D(T)$, the rooted tree $T$ is clearly
$d$-distinguishable, so suppose $\phi$ is some $d$-distinguishing
labeling of $T$. Changing the label assigned by $\phi$ to the root
gives $d$ inequivalent labelings of $T$, that is,
\[ \phi_i(u) = \left\{ \begin{array}{ll}
                        i, & \mbox{if $u = r(T)$} \\
                        \phi(u), & \mbox{if $u \ne r(T)$.}
                       \end{array}
                \right.
\]
for every $i \in \{1,\dots,d\}$. To see that the labelings are
inequivalent, suppose on the contrary that two such labelings, say
$\phi_i$ and $\phi_j$ (where $1 \le i < j \le d$), are equivalent.
Then, there would be a mapping $\pi$ between the labeled copies
$(T,\phi_i)$ and $(T,\phi_j)$ such that $\phi_i(r(T)) =
\phi_j(\pi(r(T))) = \phi_j(r(T))$, where the last equality holds
because any isomorphism between labeled copies of a rooted tree
must map the root to itself. But then, by definition of $\phi_i$
and $\phi_j$, we get $i=j$, contradicting our assumption that
$i<j$.

The existence of the inequivalent $d$-labelings
$\phi_1,\dots,\phi_d$ for $T$ implies that $D(T,d)\ge~d$.
\end{proof}

Now, we consider the recursive formula developed in~\cite{AD}
and~\cite{Che} which counts the number of inequivalent
distinguishing $d$-labelings of a rooted tree, and how to derive
the distinguishing number from it in two ways.

\begin{proposition}\label{prop:Dd}
\emph{({\cite{Che}, Th.~3.2, Cor.~3.3, Th.~4.2})} Let $T$ be a
rooted tree and $\cal T$ be the set of the components of $T$.
Suppose that $\cal T$ has exactly $g$ distinct isomorphism classes
of trees where the $i$th isomorphism class consists of $m_i$
copies of the rooted tree $T_{u_i}$; i.e., ${\cal T} = m_1 T_{u_1}
\cup m_2 T_{u_2} \cup \dots \cup m_g T_{u_g}$. Then,
\begin{enumerate}
\item $D(T,d)=d\prod_{i=1}^{g} \binom{D(T_{u_i},d)}{m_i}$.
\item $D(T) = \min\{ d \mid \forall i \in \{1,\dots,g\} \;\; D(T_{u_i},d) \ge m_i\}$.
\item $D(T) = \max\{ \min\{ d \mid D(T_{u_i},d) \ge m_i\} \mid 1 \le i \le g\}$.
\end{enumerate}
\end{proposition}

By Proposition~\ref{prop:Dd}(1), in order to compute $D(T)$ for a
rooted tree $T$, it is enough to know a list of values
$\{(m_1,u_1),\dots,(m_g,u_g)\}$, where the degree of $r(T)$ equals
$\sum_{i=1}^g m_i$ and for each pair $(m_i,u_i)$, $u_i$ is a child
of $r(T)$ and $m_i$ is the multiplicity of the isomorphic copies
of $T_{u_i}$ which appear as components of $T$. We take advantage
of the fact that Cheng~\cite{Che} shows a method to compute
exactly this information. We will assume that a new procedure
called \proc{Compute-list}, given a rooted tree $T$, returns the
list $\{(m_1,u_1),\dots,(m_g,u_g)\}$ defined above (in~\cite{Che},
this can be accomplished by calling procedure
\proc{FIND-ISOMORPH}, then \proc{ESSENTIAL} and, finally, taking
the first output). Cheng~\cite{Che} shows that this can be done in
linear time.

\subsection{Linear Time Algorithm}

We will describe the procedures used in our main algorithm. In the
first place, procedure \proc{Colorings}$(T,d)$, given a rooted
tree $T$ and a constant $d$, computes $D(T,d)$ in linear time. We
will not detail the algorithm here since it is already described
by Cheng~\cite{Che} and by Arvind and Devanur~\cite{AD}. This
procedure is called \proc{EVALUATE} in~\cite{Che} and
\emph{Inequiv} in~\cite{AD}.

Note that, according to Proposition~\ref{prop:Dd}(2), given a
rooted tree $T$ of order $n$, $D(T)$ can already be computed by
making calls to \proc{Colorings}$(T,d)$ for different values of
$d$, $1\le d\le n-1$. Since each call takes linear time, using
binary search in $d$, it is possible to find $D(T)$ in time ${\cal
O}(n\log n)$, as it is argued in~\cite{AD} and~\cite{Che}. This is
precisely the common method in~\cite{AD,Che} which works in time
${\cal O}(n\log n)$. In order to lower it to an overall linear
time, we need to carefully call this procedure for the subtrees of
$T$ only when it is needed. To do so, we need the information
contained in the list $\{(m_1,u_1),\dots,(m_g,u_g)\}$, which will
be obtained in linear time by calling to a procedure
\proc{Compute-list}, as stated at the end of
Subsection~\ref{subsec:pre}. Our algorithm is the following (see
Figure~\ref{arbre} for an example).

\bigskip

\noindent \proc{Distinguishing}($T$)

\algorithmicrequire{ A rooted tree $T$ with $n$ vertices}

\algorithmicensure{ $D(T)$}
\begin{algorithmic}[1]

\IF {$|V(T)| = 1$}
    \STATE {\bf return} $1$
\ELSE
    \STATE $col \gets 0$
    \STATE $\{(u_1,m_1),\dots,(u_g,m_g)\} \gets \proc{Compute-list}(T)$
    \FOR {$i=1$ {\bf to} $g$}
        \STATE $d \gets \proc{Distinguishing}(T_{u_i})$
        \IF {$d<m_i$}
            \WHILE {$\proc{Colorings}(T_{u_i},d) < m_i$}
                \STATE $d \gets d+1$
            \ENDWHILE
        \ENDIF
        \STATE $col \gets \mbox{max}\{col,d\}$
    \ENDFOR
    \STATE {\bf return} $col$
\ENDIF
\end{algorithmic}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.5\textwidth]{arbre.eps}
\end{center}
\caption{Each vertex is labeled with the distinguishing number of
the rooted subtree it defines.}\label{arbre}
\end{figure}

\begin{theorem}\label{teo:2} \emph{(Correctness)}
Given a rooted tree $T$ as input, procedure \proc{Distinguishing}
returns $D(T)$.
\end{theorem}

\begin{proof}
We show it by induction on the order of $T$. If the rooted tree
$T$ has only one vertex, \proc{Distinguishing} returns $1$ at line
2, which is correct. Suppose now that the order of $T$ is $n > 1$.
For each $i$, procedure \proc{Distinguishing} makes a recursive
call on the subtree $T_{u_i}$ in line 7. By induction hypothesis,
we can assume that the result is $d=D(T_{u_i})$. Now we can
distinguish two cases:
\begin{enumerate}
\item If $d \ge m_i$, then by Proposition~\ref{prop:labels},
$D(T_{u_i},d)\ge d \ge m_i$.
\item If $d < m_i$, then after the {\bf while} loop in lines 9--11,
$d$ is the smallest value satisfying $D(T_{u_i},d) \ge m_i$.
\end{enumerate}
In any case, the value of $d$ at line 13 for a given $i$ is the
smallest value such that $D(T_{u_i},d)\ge m_i$. Since the value
$col$ returned by \proc{Distinguishing} is the maximum of such
values for $1 \le i \le g$, it must equal $D(T)$ by
Proposition~\ref{prop:Dd}(3).
\end{proof}

\begin{theorem}\label{teo:1} \emph{(Complexity)}
Procedure \proc{Distinguishing} works in ${\cal O}(n)$ time.
\end{theorem}

\begin{proof}
Let $T$ be the rooted tree of order $n$ given as input and let
$T_{u_1},\dots,T_{u_g}$ be its different components up to
isomorphism, with orders $n_1,\dots,n_g$, respectively
(In~\cite{AHU} the authors provided a linear time isomorphism test
for trees). Note that since $m_i$ is the number of isomorphic
copies for $T_{u_i}$, it holds that

\begin{equation}
n = 1 + \sum_{i=1}^{g} m_i \cdot n_i.\label{eq1}
\end{equation}

Since line 5 takes linear time, let $a$ stand for a constant such
that $a n$ bounds the time required by procedure
\proc{Distinguishing} to execute lines 1--5 and return $col$ at
line 15. Additionally, the {\bf for} loop between lines 6--14 does
some work in constant time, say $b$, plus a maximum of $m_i$ calls
to \proc{Colorings}$(T_{u_i},d)$. The reason why \proc{Colorings}
is called at most $m_i$ times for a given $i$ is that the {\bf
while} loop in lines 9--11 is never executed for $d=m_i$ since, by
Proposition~\ref{prop:labels}, $D(T_{u_i},m_i)\ge m_i$ and the
condition of the loop would not hold. Now, since \proc{Colorings}
works in linear time, we can bound the overall work done between
lines 9 and 11 by $c n_i$ for a constant $c$. Now, if we denote
the running time of \proc{Distinguishing} by $R(n)$, we have

\begin{equation}
R(n) \le an + \sum_{i=1}^{g} (b + c (m_i-1) n_i + R(n_i)).
\label{eq2}
\end{equation}

Let $e$ be a constant such that $e\ge a+b+c$. We will show by
induction that the running time of \proc{Distinguishing}$(T)$ is
bounded by $an+e(n-1)$. For $n=1$, we have $R(n)\le a=an+e(n-1)$.
In the general case $n>1$, we unfold the summation in
Equation~(\ref{eq2}) and get:
\[ R(n) \le an + b g + c \sum_{i=1}^{g} ((m_i - 1) n_i) + \sum_{i=1}^{g} (a n_i + e (n_i - 1)),\]
where the last term comes from the induction hypothesis. Now,
\[ R(n) \le an + b g + (e-a) \sum_{i=1}^{g} ((m_i - 1) n_i) + a \sum_{i=1}^g n_i - e g+ e \sum_{i=1}^{g} n_i \]
\[ \le an + b g + -a \sum_{i=1}^{g} ((m_i - 1) n_i) + a \sum_{i=1}^g n_i - e g+ e (n-1) \]
\[ \le an - a \sum_{i=1}^g (m_i-1)n_i + a \sum_{i=1}^g n_i + e(n-1) \]
\[ \le an - a(n-1) + a \sum_{i=1}^g n_i + e(n-1) \]
\[ = a (1 + \sum_{i=1}^g n_i) + e(n-1) \le an + e(n-1),\]
where both Equation~(\ref{eq1}) and the fact that $e\ge a+b+c$
have been used. Therefore, we conclude that $R(n)$ is ${\cal
O}(n)$.
\end{proof}

\section{Distinguishing Trees and Forests}\label{sec:forest}

There is an easy way to transform the problem of computing $D(T)$
for a general tree $T$ into the one of computing $D(T')$ for a
rooted tree $T'$. This can be done using the concept of tree
center, as is done in~\cite{AD} and~\cite{Che}. A \emph{center} of
a tree $T$ is a vertex $v$ such that the maximal distance of $v$
to the other vertices is minimized. It is well known that every
tree has either one center or two adjacent centers. In the first
case, the tree can already be considered a rooted tree with root
at its center, while in the second case, a new vertex can be
inserted between the centers and then used as its root. As
mentioned in~\cite{AD} and~\cite{Che}, this transformation can be
done in linear time.

\begin{proposition}\label{prop:rooted}
Given a tree $T$, it is possible to compute a rooted tree $T'$ in
linear time such that $D(T)=D(T')$.
\end{proposition}

As a direct consequence of Proposition~\ref{prop:rooted} and
Theorems~\ref{teo:2} and~\ref{teo:1}, we conclude the following.

\begin{corollary}
The distinguishing number of a tree with $n$ vertices can be
computed in ${\cal O}(n)$ time.
\end{corollary}

In the case of forests, we use the transformation from Cheng's
paper~\cite{Che}, which is as follows. Suppose that $F$ is a
forest and define the following trees $T_1$ and $T_2$. In the
first place, create two vertices $v_1$, and $v_2$ which will act
as the respective roots of $T_1$ and $T_2$, respectively. In the
second place, transform each connected component of $F$ into a
rooted tree as indicated before Proposition~\ref{prop:rooted}.
Since this can be done in two ways, depending on whether the
original tree is unicentral or bicentral, call $F_1$ ($F_2$) to
the set of rooted trees obtained from the unicentral (bicentral)
trees in $F$ in the way indicated before
Proposition~\ref{prop:rooted}. Finally, join $v_j$ to the roots of
all trees in $F_j$, for $1\le j\le 2$. We can now state the
following regarding the above construction.

\begin{proposition}\label{prop:forest}
Given a forest $F$, it is possible to compute two rooted trees
$T_1$ and $T_2$ in linear time such that $D(F)=\max\{D(T_1),
D(T_2)\}$.
\end{proposition}

\begin{proof}
It is well known that the centers of a tree can be computed in
linear time. So, given a forest $F$ with $n$ vertices, the above
transformation into trees $T_1$ and $T_2$ can be done in time
${\cal O}(n)$. Moreover, since no automorphism of $F$ can map a
unicentral tree into a bicentral tree or viceversa, nontrivial
automorphisms of $F$ induce separate nontrivial automorphisms in
$T_1$ and $T_2$. Suppose that $d=\max\{D(T_1), D(T_2)\}$. Then,
$d$ labels are enough to break symmetries in both $T_1$ and $T_2$,
that is, there must be two $d$-labelings $\phi_1$, $\phi_2$ such
that both $\Aut(T_1,\phi_1)$ and $\Aut(T_2,\phi_2)$ are trivial.
Then, one can define a distinguishing $d$-labeling $\phi$ of $F$:
Given a vertex $u$ of $F$, if $u \in T_1$, set $\phi(u) =
\varphi_1(u)$ and, otherwise, set $\phi(u) = \varphi_2(u)$. In
case $\Aut(F,\phi)$ was nontrivial, then one of
$\Aut(T_1,\varphi_1)$ or $\Aut(T_2,\varphi_2)$ would be
nontrivial. Thus, $\Aut(F,\phi)$ must be trivial, and $D(F)\le d$.
But we can discard the case when $D(F)= d'< d$ since it would make
it possible to use the distinguishing $d'$-labeling of $F$ to
define a distinguishing $d'$-labeling of $T_1$ and $T_2$,
contradicting the definition of $d$ as the maximum between
$D(T_1)$ and $D(T_2)$. Therefore, $D(F)=\max\{D(T_1),D(T_2)\}$.
\end{proof}

Now, it is clear that our algorithm \proc{Distinguishing} from
Section~\ref{sec:rooted} can be used twice in combination with
Proposition~\ref{prop:forest} to yield the following result.

\begin{corollary}
The distinguishing number of a forest with $n$ vertices can be
computed in ${\cal O}(n)$ time.
\end{corollary}

\section{Conclusions and applications}\label{sec:applications}

We have shown that the distinguishing number of trees and forests
can be computed in linear time, improving the previously known
${\cal O}(n\log n)$ time algorithm. We \emph{believe} that our
algorithmic technique in Section~\ref{sec:rooted} can be applied
to improve by a logarithmic factor (caused by a binary search in
the last step of the algorithms) the complexities of computing
distinguishing numbers and distinguishing chromatic numbers of the
following graph classes: (1) \emph{the distinguishing number} of
(i) planar graphs computed by Arvind et al.~\cite{AD,ACD} and (ii)
interval graphs computed by Cheng~\cite{Che1}; (2) \emph{the
distinguishing chromatic number} (due to Collins and
Trenk~\cite{CT}, see also~\cite{EHSS}) of: (i) trees computed by
Cheng~\cite{Che1} and (ii) interval graphs computed by
Cheng~\cite{Che1}.

\begin{thebibliography}{XX}

\bibitem{A} M. O. Albertson. \newblock Distinguishing cartesian powers of
graphs. \newblock \emph{Electron. J. Combin.}, Vol. 12, N17, 2005.

\bibitem{AC} M. O. Albertson and K. Collins. \newblock Symmetry breaking in graphs.
\newblock \emph{Electron. J. Combin.}, Vol. 3, R18, 1996.

\bibitem{AHU} A. V. Aho, J. E. Hopcroft, and J. D. Ullman. \newblock \emph{The design
and analysis of computer algorithms}. \newblock Addison-Wesley
Pub. Co. 1974.

\bibitem{AD} V. Arvind and N. R. Devanur. \newblock Symmetry breaking in trees
and planar graphs by vertex coloring. \newblock \emph{Proceedings
of the Nordic Combinatorial Conference}, 2004.

\bibitem{ACD} V. Arvind, C. T. Cheng, and N. R. Devanur. \newblock On computing the
distinguishing numbers of planar graphs and beyond: a counting
approach. \newblock \emph{SIAM Journal on Discrete Mathematics},
22:4, pp. 1297--1324, 2008.

\bibitem{BC} B. Bogstad and L. J. Cowen. \newblock The distinguishing number of the
hypercube. \newblock \emph{Discrete Math.}, Vol. 283, No. 1-3, pp.
29--35, 2004.

\bibitem{Cha} M. Chan. \newblock The distinguishing number of the augmented cube
and hypercube powers. \newblock \emph{Discrete Math.}, Vol. 308,
pp. 2330--2336, 2008.

\bibitem{Cha1}M. Chan. \newblock The distinguishing number of the direct product and
wreath product action. \newblock \emph{Journal of Algebraic
Combinatorics}, Vol. 24, pp. 331--345, 2006.

\bibitem{Cha2} M. Chan. \newblock The maximum distinguishing number of a group.
\newblock \emph{Electron. J. Combin.}, Vol. 13, R70, 2006.

\bibitem{Che} C. Cheng. \newblock On computing the distinguishing numbers of
trees and forests. \newblock \emph{Electron. J. Combin.}, Vol. 13,
R11, 2006.

\bibitem{Che1} C. Cheng. \newblock On computing the distinguishing and distinguishing
chromatic numbers of interval graphs and other results.
\newblock \emph{Discrete Math.}, 309:16, pp. 5169--5182, 2009.

\bibitem{CT} K. L. Collins and A. N. Trenk. \newblock The distinguishing chromatic
number. \newblock \emph{Electron. J. Combin.}, Vol. 13, R16, 2006.

\bibitem{EHSS} E. M. Eschen, C. T. Ho\`ang, R. Sritharan, and L. Stewart.
\newblock On the complexity of deciding whether the distinguishing chromatic
number of a graph is at most two. \newblock \emph{Discrete Math.},
Vol. 311, Issue 6, pp. 431--434, 2011.

\bibitem{IK} W. Imrich and S. Klav\v{z}ar. \newblock Distinguishing
cartesian powers of graphs. \newblock \emph{Journal of Graph
Theory}, Vol. 53, Issue 3, pp. 250--260, 2006.

\bibitem{IJK} W. Imrich, J. Jerebicb, and S. Klav\v{z}ar.
\newblock The distinguishing number of cartesian products of complete
graphs. \newblock \emph{European J. Combin.}, Vol. 29, Issue 4,
pp. 922--929, 2008.

\bibitem{KZ} S. Klav\v{z}ar and X. Zhu. \newblock Cartesian powers of
graphs can be distinguished by two labels. \newblock
\emph{European J. Combin.}, Vol. 28, pp. 303--310, 2007.

\bibitem{RS} A. Russell and R. Sundaram. \newblock A note on the asymptotics and
computational complexity of graph distinguishability.
\newblock \emph{Electron. J. Combin.}, Vol. 5, R23, 1998.

\bibitem{T} J. Tymoczko. \newblock Distinguishing numbers for graphs and
groups. \newblock \emph{Electron. J. Combin.}, Vol. 11(1), R63,
2004.

\bibitem{W} D. B. West. \newblock \emph{Introduction to graph theory}. \newblock Prentice Hall, 1996.
\end{thebibliography}
\end{document}


\begin{abstract}
  The reconstruction conjecture states that the multiset of unlabeled
  vertex-deleted subgraphs of a graph determines the graph, provided
  it has at least 3 vertices.  This problem was independtly introduced
  by Stanis\l aw Ulam (1960) and and Paul Kelly (1957). In this paper,
  we prove the conjecture by elementary methods.  It is only necessary
  to integrate the Lenkle potential of the Broglington manifold over
  the quantum supervacillatory measure in order to reduce the set of
  possible counterexamples to a small number (less than a trillion).
  A simple computer program that implements Pipletti's classification
  theorem for torsion-free Aramaic groups with simplectic socles can
  then finish the remaining cases.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} graph reconstruction
  conjecture; Broglington manifold; Pipletti's classification
\end{abstract}

\section{Introduction}

The reconstruction conjecture states that the multiset of unlabeled
vertex-deleted subgraphs of a graph determines the graph, provided it
has at least three vertices.  This problem was independtly introduced
by Ulam~\cite{Ulam} and Kelly~\cite{Kelly}.  The reconstruction
conjecture is widely studied
\cite{Bollobas,FGH,HHRT,KSU,RM,RR,Stockmeyer} and is very interesting
because...... See \cite{WikipediaReconstruction} for more about the
reconstruction conjecture.

\begin{definition}
  A graph is \emph{fabulous} if....
\end{definition}

\begin{theorem}
  \label{Thm:FabGraphs}
  All planar graphs are fabulous.
\end{theorem}

\begin{proof}
  Suppose on the contrary that some planar graph is not fabulous....
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Broglington Manifolds}

This section describes background information about Broglington
Manifolds.

\begin{lemma}
  \label{lem:Technical}
  Broglington manifolds are abundant.
\end{lemma}

\begin{proof}

\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof of Theorem~\ref{Thm:FabGraphs}}

In this section we complete the proof of Theorem~\ref{Thm:FabGraphs}.

\begin{proof}[Proof of Theorem~\ref{Thm:FabGraphs}]
Let $G$ be a graph... Hence
 % use the amsmath align environment for multi-line equations
  \begin{align}
    |X| &= abcdefghijklmnopqrstuvwxyz \nonumber\\
    &= \alpha\beta\gamma
  \end{align}
  This completes the proof of Theorem~\ref{Thm:FabGraphs}.
\end{proof}

\begin{figure}[!h]
  \begin{center}
    % use \includegraphics to import figures
    % \includegraphics{filename}
  \end{center}
  \caption{\label{fig:InformativeFigure} Here is an informative
    figure.}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
Thanks to Professor Querty for suggesting the proof of
Lemma~\ref{lem:Technical}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% we recommend using BibTeX to create a bibliography
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% then copy and past the contents of your .bbl file into this .tex file

\begin{thebibliography}{10}

\bibitem{Bollobas} B{\'e}la Bollob{\'a}s.  \newblock Almost every
  graph has reconstruction number three.  \newblock {\em J. Graph
    Theory}, 14(1):1--4, 1990.

\bibitem{WikipediaReconstruction} Wikipedia contributors.  \newblock
  Reconstruction conjecture.  \newblock {\em Wikipedia, the free
    encyclopedia}, 2011.

\bibitem{FGH} J.~Fisher, R.~L. Graham, and F.~Harary.  \newblock A
  simpler counterexample to the reconstruction conjecture for
  denumerable graphs.  \newblock {\em J. Combinatorial Theory Ser. B},
  12:203--204, 1972.

\bibitem{HHRT} Edith Hemaspaandra, Lane~A. Hemaspaandra,
  Stanis{\l}aw~P. Radziszowski, and Rahul Tripathi.  \newblock
  Complexity results in graph reconstruction.  \newblock {\em Discrete
    Appl. Math.}, 155(2):103--118, 2007.

\bibitem{Kelly} Paul~J. Kelly.  \newblock A congruence theorem for
  trees.  \newblock {\em Pacific J. Math.}, 7:961--968, 1957.

\bibitem{KSU} Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara.
  \newblock Reconstruction of interval graphs.  \newblock In {\em
    Computing and combinatorics}, volume 5609 of {\em Lecture Notes in
    Comput. Sci.}, pages 106--115. Springer, 2009.

\bibitem{RM} S.~Ramachandran and S.~Monikandan.  \newblock Graph
  reconstruction conjecture: reductions using complement, connectivity
  and distance.  \newblock {\em Bull. Inst. Combin. Appl.},
  56:103--108, 2009.

\bibitem{RR} David Rivshin and Stanis{\l}aw~P. Radziszowski.
  \newblock The vertex and edge graph reconstruction numbers of small
  graphs.  \newblock {\em Australas. J. Combin.}, 45:175--188, 2009.

\bibitem{Stockmeyer} Paul~K. Stockmeyer.  \newblock The falsity of the
  reconstruction conjecture for tournaments.  \newblock {\em J. Graph
    Theory}, 1(1):19--25, 1977.

\bibitem{Ulam} S.~M. Ulam.  \newblock {\em A collection of
    mathematical problems}.  \newblock Interscience Tracts in Pure and
  Applied Mathematics, no. 8.  Interscience Publishers, New
  York-London, 1960.

\end{thebibliography}

\end{document}