\documentclass[12pt]{article}
\usepackage{amsfonts,amssymb,amscd,amsmath,enumerate,verbatim,calc,graphicx}
\usepackage[]{color}
%\usepackage[colorlinks,breaklinks,backref]{hyperref}

 \usepackage{e-jc}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{definitions}[theorem]{Definitions}
\newtheorem{remarks}[theorem]{Remarks}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{notations}[theorem]{Notations}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{acknowledgement}{Acknowledgement}
\renewcommand{\theacknowledgement}{}

\newcommand{\A}{\ensuremath{\operatorname{Aut}}}
\newcommand{\Sym}{\ensuremath{\operatorname{Sym}}}
\newcommand{\End}{\ensuremath{\operatorname{End}}}
\newcommand{\D}{\ensuremath{\operatorname{D}}}
\newcommand{\V}{\ensuremath{\operatorname{V}}}
\newcommand{\sk}{\ensuremath{\operatorname{S}}}
\newcommand{\m}{\ensuremath{\operatorname{m}}}
\newcommand{\Prob}{\ensuremath{\operatorname{Pr}}}
\newcommand{\id}{\ensuremath{\text{\rm id}}}
\newcommand{\dist}{\ensuremath{\operatorname{dist}}}
\newcommand{\supp}{\ensuremath{\operatorname{supp}}}
\newcommand{\cl}{\ensuremath{\operatorname{cl}}}
\newcommand{\cg}{\overline{G}}
\newcommand{\cp}{\,\square\,}
\newcommand{\strong}{\boxtimes}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\detnum}{{\rm Det}}

\newcommand{\proof}{\noindent{\bf Proof\,\ }}
\newcommand{\qed}{\hfill $\Box$}
\newcommand{\stab}{{\rm Stab}}
\newcommand{\setstab}{{\rm SetStab}}
\newcommand{\ptstab}{{\rm PtStab}}
\newcommand{\diam}{{\rm diam}}



\newcommand{\red}{\color{red}}
\newcommand{\bl}{ \color{black}}
\newcommand{\rout}{\red\sout}
\usepackage[normalem]{ulem}

\begin{document}
\title
{Infinite Graphs with Finite 2-Distinguishing Cost}
\author{Debra Boutin \\
Hamilton College, Clinton, NY 13323, USA \\
dboutin@hamilton.edu
\and
Wilfried Imrich\\
Montanuniversit\"{a}t Leoben, 8700 Leoben, Austria \\
imrich@unileoben.ac.at}
%\date{April 1, 2014}
\maketitle


\begin{abstract}
A graph $G$ is said to be 2-distinguishable if there is a labeling of the vertices with two
labels such that only the trivial automorphism preserves the labels. Call the minimum size of
a label class in such a labeling of $G$ the cost of 2-distinguishing $G$.

Within the class of connected, locally finite, infinite graphs, we show that those with finite 2-distinguishing cost are precisely the graphs with countable automorphism group.  Further we show that, for such graphs, the cost is less than three times the size of a smallest determining set (a set which only the trivial automorphism fixes pointwise).  {Finally we show that graphs with}  linear growth {rate $c$ have} the even smaller upper bound of {$c+1$ on their cost of 2-distinguishing}.
\end{abstract}

\vspace{0.5cm}
\noindent {\bf Key words}: Distinguishing number, Distinguishability, Automorphism, Determining set, Determining number,
Infinite graph

\bigskip\noindent
{\bf AMS subject classification (2000)}: 05C15, 05C25,

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

A labeling of the vertices of a graph $G$ with the integers $1, \ldots , d$ is called  $d$-{\it distinguishing} if no nontrivial automorphism of $G$ preserves the labels. A graph is called $d$-{\it distinguishable} if it has a $d$-distinguishing labeling. This concept was introduced by Albertson and Collins in \cite{alco-96} and has spawned a  wealth of results, in particular for finite graphs, but also for infinite ones.\medskip

For finite graphs it was shown that many infinite families of graphs have the property that all but finitely many members  are 2-distinguishable{;} see \cite{4way-2014}. Interestingly, in such cases the size of the smaller color class can be extremely small. For example the hypercube $Q_{2^k}$ of dimension $2^k$ can be 2-distinguished by coloring $k+2$ vertices black and the others white{;}\bl see \cite{bo-2013}.\medskip

There are {also} large classes {of} 2-distinguishable infinite graphs. In this paper, we consider the question {of} whether one of the two color classes can be finite, and how to obtain good bounds for the size of such a class.\medskip

To aid in addressing this question, we will call a label class in a 2-distinguish\-ing labeling a \emph{distinguishing class}. Following \cite{bo-2008} we call the minimum size of a distinguishing class for a 2-distinguishable graph G the {\it cost of 2-distinguishing} $G$ and denote it by $\rho(G)$.\medskip

In the finite case it is natural to restrict the investigation to connected graphs. {Thus the} first natural extension to the infinite {is to}\bl connected, locally finite, infinite graphs. That is, connected graphs that are infinite, and whose vertices have finite, but possibly arbitrarily large degrees. We show that such  graphs $G$ have finite $\rho(G)$  if and only if $\A(G)$ is countable. Further we provide two general bounds for $\rho(G)$ and a sharper one for graphs of linear growth.\medskip

\section{Preliminaries}
\label{sec:prelim}


Recall that the {\it set stabilizer} of $S\subseteq V(G)$, denoted $\setstab(S)$, is the set of all  $\varphi\in{\rm Aut}(G)$ for which $\varphi(x) \in S$ for all $x\in S$.  In this case we say that $S$ is invariant under $\varphi$, or $\varphi$ preserves $S$, and we write $\varphi(S)=S$.  The {\it point stabilizer} of $S$, denoted $\ptstab(S)$ is the set of all $\varphi\in {\rm Aut}(G)$ for which $\varphi(x)=x$ for all $x\in S$.\medskip

A labeling of the vertices of a graph $G$ with the integers $1,\ldots, d$ is called a {\it $d$-distinguishing labeling} if no non-trivial automorphism of $G$ preserves the labels. A graph is called {\it $d$-distinguishable} if it has a $d$-distinguishing labeling.  If a graph is 2-distinguishable, call a color class in a 2-distinguishing labeling a {\it distinguishing class} for $G$.  The minimum size of a distinguishing class for a 2-distinguishable graph $G$ is called the {\it cost of $2$-distinguishing $G$} and {is}\bl denote{d} by $\rho(G)$.\medskip

A significant tool used in this work is a {\it determining set} \cite{B1} (or equivalently, a {\it base} of the automorphism group action).  A determining set {$S$} has the property that whenever $\varphi, \psi \in {\rm Aut}(G)$ so that $\varphi(x)=\psi(x)$ for all $x\in {S}$, then $\varphi=\psi$. Thus every automorphism of $G$ is uniquely determined by its action on the vertices of a determining set. Equivalently, a determining set is a set of vertices $S$ with $\ptstab(S)=\{\id\}$. The {\it determining number} of the graph $G$, denoted  by ${\rm Det}(G)$, is the minimum size of a determining set of $G$.\medskip

Note that for $F\subseteq V(G)$, an automorphisms $\varphi\in \setstab(F)$ can be thought of as a permutation in $\Sym(F)$ by restricting the action of $\varphi$ to $F$, denoted $\varphi|F$.  Thus we have a natural map $\Psi:\setstab(F) \to \A(G)|F \leq \Sym(F)$.  Note that this map is injective if and only if $F$ is a determining set for $G$.  In such a case, we get that $\setstab(F) \cong \A(G)|F$.\medskip

Albertson and Boutin showed in \cite{AB2} that a graph is $d$-distinguishable if and only if it has a determining set that is $(d-1)$-distinguishable.  In particular, such a determining set is a distinguishing class for a 2-distinguishable graph $G$.  Thus, a graph is $2$-distinguishable if and only if it has a determining set $S$ for which $\setstab(S) = \ptstab(S) = \{\id\}$. In such a case, the determining set and its complement provide the two necessary label classes for a 2-distinguishing labeling.  Thus in particular, the cost of $2$-distinguishing a graph $G$ is bounded below by the size of a smallest determining set.\medskip

The {\it motion} of an automorphism $\varphi\in \A(G)$, denoted $\m(\varphi)$,  is the number of vertices moved by $\varphi$.  The {\it motion} of the automorphism group, denoted {$\m(G)$}, is the minimum motion of the non-trivial elements of $\A(G)$.\medskip

Throughout this paper let $\Gamma$ denote the class of infinite, connected, locally finite graphs. For such graphs Halin proved the following result, which is foundational for the work that follows.

\begin{theorem}\label{thm:halin} {\rm \cite{ha-73} (Halin, 1973)} A connected, locally finite infinite graph $G$ has uncountable $\A(G)$ if and only if for every finite $F \subset V(G)$ there exists a non-trivial automorphism $\varphi$ of $G$ such that $\varphi(v) = v$ for each $v \in F$.\end{theorem}

In other words, $G \in \Gamma$ has uncountable {automorphism} group if and only if it does not have a finite determining set. Therefore, a  2-distinguishable graph $G$ with uncountable {automorphism} group has infinite $\rho(G)$. We are thus interested in graphs $G$ of $\Gamma$ whose {automorphism} group is not uncountable. We first consider those that have infinite automorphism group. For them we have the following extension of Theorem \ref{thm:halin}.

\begin{theorem}\label{thm:istw}  {\rm \cite{4way-2014} (Imrich, Smith, Tucker, Watkins, 2014)} If $G\in \Gamma$  so that $\aleph_0 \leq  |\A(G)|$ $<$ $2^{\aleph_0}$, then $\detnum(G) < \aleph_0$, $|\A(G)| = \aleph_0$, $m(G) = \aleph_0$, and $G$ is 2-distinguishable. This holds independently of the Continuum Hypothesis. \end{theorem}

There is yet another consequence of Theorem \ref{thm:halin} that is folklore. It says that the vertex stabilizers of graphs $G \in \Gamma$ are finite if $\A(G)$ is countably infinite. This follows, for  example, from the slightly more general Corollary 3.10 from \cite{4way-2014}. Below we state and prove a related result that invokes neither Theorem \ref{thm:halin} nor Theorem \ref{thm:istw}, but needs the following definition: The set of vertices $u\in V(G)$ for which $d(u,v)\leq n$ is called \emph{ball of radius $n$ centered at $v$,} and denoted $B_v(n)$. For later reference we also define the \emph{sphere $S_v(n)$of radius $n$ centered at $v$} as the set of vertices $u\in V(G)$ for which $d(u,v)= n$.

\begin{lemma}\label{le:finite_vertex-stab}  {If $G\in \Gamma$ has finite determining set, then the vertex stabilizers of $G$ are finite.}
\end{lemma}

\proof Suppose  $B$ is a {finite} determining set for $G$ and $\ptstab(v)$ is infinite. {Since $B$ is finite, we may choose $k$ so that} $B \subseteq B_v(k)$. Hence, the orbit $C = \ptstab(v)(B)$ of $B$ {under} $\ptstab(v)$ is {a subset of} $B_v(k)$ and thus is finite. Because the infinite group  $\ptstab(v)$ stabilizes the finite set $C$ {setwise}, there must be at least two different elements of $\ptstab(v)$ whose actions are identical on $C$, and thus also on $B$.  {This contradicts the choice of $B$ as a determining set.}
\qed
\medskip




\section{Countable Automorphism Group}

By Theorem \ref{thm:istw} the automorphism groups of graphs $G$ in $\Gamma$ that satisfy
$\aleph_0 \leq  |\A(G)| < 2^{\aleph_0}$ are countable.  Moreover, such graphs have infinite motion, are 2-distinguishable, and have finite determining sets. Below we show that such graphs $G$ have finite 2-distinguishing cost and give two bounds for  $\rho(G)$.



\begin{lemma}\label{le:finite_base_and_cost}
If $G\in \Gamma$ with infinite automorphism group and $\detnum(G)=n<\aleph_0$, then $\rho(G)$ is finite and satisfies the inequality $$\rho(G) \leq n + n! -1\,.$$
\end{lemma}


\proof  Let $F$ be a minimum determining set for $G$.  Since $F$ is a determining set, as discussed in Section \ref{sec:prelim}, $\setstab(F) \cong \A(G)|F \leq \Sym(F)$.  Since $F$ is finite, so is $\Sym(F)$, and hence so is $\setstab(F)$.  Let $\setstab(F) = \{\id = \alpha_0, \alpha_1, \alpha_2, \ldots, \alpha_k\}$. If $|F| = 1$, then $k = 0$. We can thus assume that $|F| > 1$.\medskip

Color all elements of $F$ black and consider $\alpha_1$. By Theorem \ref{thm:istw}, $G$ has infinite motion.  In other words, every nontrivial automorphism moves infinitely many vertices.   Since $\alpha_1$  moves infinitely many vertices,  there is a vertex $v_1$, moved by $\alpha_1$, whose distance $d(v_1, F)$ from $F$ is larger than the diameter of $F$.   Color it black.  Similarly there is a vertex $v_2$, moved by $\alpha_2$, with $d(v_2, F) > d(v_1, F) + \diam(F)$. Color it black as well.
Similarly construct the vertices $v_3$ to $v_k$ and color them black.\medskip

Suppose that $\varphi$ preserves the set of black vertices.  Since each of $v_1,\ldots, v_k$ is farther from $F$ than any pair of vertices in $F$ is, $\varphi$ must preserve $F$.  Thus $\varphi \in \setstab(F)$.  Thus either $\varphi = id$ or $\varphi = \alpha_i$ for some $i\in[k]$.  Recall that, for each $i\in [k]$, since $v_i$ is the only black vertex of distance $d(v_i,F)$ from $F$, we have that $\varphi(v_i)=v_i$.  Since $v_i$ is moved by $\alpha_i$, we infer $\varphi\ne \alpha_i$.  Thus $\varphi = id$ and the set of black vertices is a distinguishing class. Clearly its size is $|\setstab(F)| -1 + |F|\leq  n! + n -1$.  Hence, $\rho(G) < \aleph_0$.\qed\medskip

Interestingly this crude bound is sharp for the 2-sided infinite path $P_{\aleph_0}$. To see this, observe that no single vertex of $P_{\aleph_0}$ can be a determining set, but that the set of end-points of any edge is a determining set.  By the lemma, $\rho(P_{\aleph_0})\leq 3$.  It is easy to see that  $\rho(P_{\aleph_0})$ cannot be 1 or 2. Hence $\rho(P_{\aleph_0})$ = 3 and the bound is sharp.\medskip

A better bound is the following, which we formulate as theorem. It uses a strong result of Cameron, Solomon and Turull \cite{casot-89}, which asserts that the largest length of a chain of subgroups of the symmetric group on $n$ elements is $\left\lceil\frac{3n}{2}\right\rceil - b(n) - 1$, where $b(n)$ denotes the number of 1s in the base-2 representation of $n$.\medskip

\begin{theorem}\label{le:cameron}  If $G\in \Gamma$ with infinite automorphism group and $\detnum(G)=n<\aleph_0$, then $\rho(G) \leq \left\lceil\frac{5n}{2}\right\rceil - b(n) - 1$, where $b(n)$ denotes the number of 1s in the base-2 representation of $n$.
\end{theorem}

\proof Let $F$ be a minimum determining set for $G$. Then $n=|F|=\detnum(G)$.  Let $k, \alpha_i, v_i$ for $i\in [k]$ be as in the proof of Lemma \ref{le:finite_base_and_cost}. As shown above, coloring all elements of $F$ black breaks all automorphisms of $G$ that do not preserve $F$. The automorphisms that preserve $F$ form a (not necessarily proper) subgroup $A_0$ of $\Sym(F)$. Coloring $v_1$ black leaves a subgroup $A_1 < A_0$ of still unbroken elements of $\A(G)$. Using the notation $A_i$ for the group that preserves the set $F\cup\{v_1, \ldots, v_i\}$ we thus arrive at a chain of subgroups $$\{\id\} = A_k < A_{k-1} < \cdots < A_0$$ of length $k$. By \cite{casot-89},  $k\leq\left\lceil\frac{3n}{2}\right\rceil - b(n) - 1$.
Because  we colored $k + n$ vertices black the result follows.\qed\medskip

Again, this bound is sharp for $P_{\aleph_0}$.   From $\detnum(P_{\aleph_0})=2$ we infer  $\rho(P_{\aleph_0}) \leq$ $ \lceil5\cdot|F|/2\rceil - b(|F|) - 1 = 5 - 1  -1 = 3$,  which we know is the cost of 2-distinguishing $P_{\aleph_0}$.
\medskip

{We now combine some of  the above results for our main theorem.}\smallskip

\begin{theorem}\label{thm:finiterho}   Let $G\in \Gamma$ with infinite automorphism group.  Then
$\rho(G)$ is finite if and only if $\A(G)$ is countable. \end{theorem}


\proof Let $G$ be a graph in $\Gamma$ with finite $\rho(G)$. Since a distinguishing class is necessarily a determining set, we can conclude that $G$ has a finite determining set.  Then, by Theorem \ref{thm:halin}, $\A(G)$ cannot be uncountable. Thus it is countable. \medskip

Suppose  $G \in \Gamma$ has countable automorphism group.  By Theorem \ref{thm:istw}, $G$ is both 2-distinguishable and has a finite determining set. By using either Lemma \ref{le:finite_base_and_cost} or Theorem \ref{le:cameron} we conclude that $\rho(G)$ is finite.\qed

\section{Linear Growth}

For graphs of linear growth we can obtain an even better bound for the cost of 2-distinguishing. We begin with a few remarks about graphs of linear growth.\medskip

A connected, locally finite, infinite graph $G$ is said to have \emph{linear growth} if there exists a vertex $v$ and a constant $c$, such that $|B_v(n)| \leq cn$, {for all $n\in \N$}. The definition is independent of the choice of $v$, but $c$ may have to be replaced by a different constant if $v$ is changed.\medskip

Notice that $B_v(n) = \cup_{i=0}^n S_v(i)$ and that the growth is {obviously} linear if $|S_v(n)| \leq c$ for all $n$. Nonetheless, it is possible that infinitely many spheres have more than  $c$ elements. Moreover, the size of the spheres need not even be bounded. We leave it to the reader to construct examples. \medskip

More important for us is the fact that there must be infinitely many spheres of size at most $c$. {To see this, {suppose} only $m< \aleph_0$  of {the spheres around $v$} contain at most $c$ vertices.  Consider $B_{v}(cm+1) = \cup_{i=0}^{cm+1} S_v(i)$.  The $m$ spheres of size at most $c$ contain at least one vertex each, and thus in total {contain} at least $m$ vertices.  The $(c-1)m+1$ spheres with more than $c$ vertices contain at least $c+1$ vertices each, and thus {contain} at least $(c+1)(cm+1-m)$ in total.  Thus $|B_{v}(cm+1) | = \cup_{i=0}^{cm+1} |S_v(i)| \geq  m + ((c-1)m+1)(c+1)= c(cm+1)+1$ which contradicts the assumption on the  growth of $G$.}  Thus there are an infinite number of spheres  of size at most $c$. Because $c$ is finite, infinitely many of these spheres must have the same size.\medskip

Interestingly, for graphs $G\in \Gamma$ with linear growth and infinite automorphism group, $\m(G) = \aleph_0$ if and only if $|\A(G)| = \aleph_0$. That $|\A(G)| = \aleph_0$ implies infinite motion follows from Theorem \ref{thm:istw}.  The reverse implication is not hard to show. In \cite{cuimle-xx} it is attributed to \cite{4way-2014}, but only the consequence that {$G$ is 2-distinguishable} is mentioned there. As that paper contains no proof of it, we include one here for the sake of completeness. {The proof}  uses the following lemma, which is similar to Lemma 2.4 in \cite{cuimle-xx}.\medskip

\begin{lemma}\label{sphere}  Suppose that $G$ is a connected, locally finite graph and $\A(G)$ has infinite motion.  If $\alpha,\beta \in \ptstab(v)$ and $\alpha|S_v(n)=\beta|S_v(n)$ for some $n>0$, then $\alpha|B_v(n)=\beta|B_v(n)$. Furthermore, if $\alpha, \beta \in \ptstab(v)$ {have distinct actions} on $S_v(n)$, then {they have distinct actions} on all $S_v(m)$ where $m>n$.
\end{lemma}

\proof  {Define the mapping $\gamma$ on $V(G)$ by $\gamma(u)=u$ for all $u$ with $d(v,u)\geq n$ and $\gamma(u)=\alpha\beta^{-1}(u)$ for all $u$ with $d(v,u)<n$. Clearly, $\gamma$ is one-to-one and onto and preserves adjacency, so $\gamma$ is an automorphism. Since $\A(G)$ has infinite motion, but $\gamma$ moves at most finitely many vertices (those inside $B_{v}(n-1)$), $\gamma=id$.} This proves the first assertion. The second assertion easily follows  from the first.
\qed

\begin{lemma} Let $G \in \Gamma$ be a graph of linear growth with infinite automorphism group. Then $\A(G)$ is countable if and only if $G$ has infinite motion.
\end{lemma}

\proof By Theorem \ref{thm:istw} we only have to show that infinite motion implies that $\A(G)$ is countable. For {distinct}   $\alpha, \beta \in \ptstab(v)$ there is some $k$ so that $\alpha,\beta$ differ in their action on $S_v(k)$.  If $\ptstab(v)$ is finite then there exists some $k$ so that all pairs of automorphisms in $\ptstab(v)$ differ in their actions on the finite set $B_v(k)$.  In such a case $\detnum(G)$ is finite and thus by Theorem \ref{thm:halin},   $\A(G)$ is countable.   {Thus it is sufficient to prove that point stabilizers in $G$ are finite.} Suppose $\ptstab(v)$ is infinite. Since $G$ has linear growth, {by our previous argument} we know that there are infinitely many spheres with center $v$ that have  size at most $c$.  {Since $\ptstab(v)$ is infinite, we may} consider $c! + 1$ distinct elements of $\ptstab(v)$. Any {pair} of these must act distinctly on some sphere $S_v(n)$, and thus  by Lemma \ref{sphere}, on all spheres $S_v(m)$ for $m > n$. Hence, there must be a sphere of size $c$ on which all $c! + 1$ automorphisms have distinct action. But this is impossible since there are at most $c!$ distinct actions on a set of size $c$.  Thus $|\ptstab(v)| <\aleph_0$.  In particular, if $G\in \Gamma$ has  infinite motion and linear growth {rate $c$ from vertex $v$, then} then $|\ptstab(v)| \leq b!$ where $b \leq c$ is the minimum sphere size that occurs infinitely often.\qed
\medskip

{The part of the lemma which asserts that linear growth and infinite motion imply countability of the automorphisms group  is based on an observation by T.~Tucker\footnote{Private communication.}.}\medskip

\begin{theorem}\label{le:linear}  Let $G$ be a graph with countably infinite automorphism group and  linear growth. If $|B_v(n)| \leq cn$ for a fixed $v \in V(G)$ and $c\in \R$, then $\rho(G) \leq c + 1$.
\end{theorem}

\proof Notice first that since $G$ has a countable automorphism group, by Theorem \ref{thm:istw}, it has infinite motion.  By our previous argument, there are infinitely many spheres of size at most $c$ {centered at $v$}.  Denote these by {$S_i = S_v(n_i)$}, for $n_1 < n_2 < \cdots $. Since $c$ is finite, infinitely many of these spheres must have the same size. Without loss of generality we can assume that the $S_i$ already have the same size, say $d$.\medskip

Note that for $j<i$, the minimal distance between an arbitrary vertex in $S_i$ and one in $S_j$ is $n_i - n_{j}$ and the maximal distance is $n_i + n_{j}$. Hence, if we choose the $n_i$ such that $$n_i > 2 \sum_{j < i }n_j\,,$$ then for $j<i$ the distance between an arbitrary vertex in $S_i$ and one in $S_j$ is larger than the maximal distance of any two vertices in $\cup_{j < i }S_{j}$. \medskip



By Lemma \ref{sphere}, since $G$ has infinite motion, every non-identity element of $\ptstab(v)$ acts non-trivially on all but finitely many spheres.  As $\ptstab(v)$ is finite by Lemma \ref{le:finite_vertex-stab},  without loss of generality, we can assume that $\ptstab(v)\setminus \{\id\}$ acts non-trivially on all spheres $S_i$.\medskip

For the sequel we wish to remind the reader that we have chosen the notation such that mappings act on the left.
\smallskip

For each $i$ greater than 1, fix an arbitrary bijection $\phi_i$ from $S_1$ to $S_i$.  Let $\phi_1 =  id$ on $S_1$.  For each $i$, denote by $A_i$ the group $\phi_i^{-1}(\ptstab(v)|{S_i})\phi_i$. By definition, each of the $A_i$ is a subgroup of ${\rm Sym(}S_1)$.  Further, consider an arbitrarily chosen $\alpha \in \ptstab(v)$ and the infinite set of  permutations $\{\beta_i = \phi_i^{-1}(\alpha|{S_i}) \phi_i\}\subseteq \Sym(S_1)$.  As $\Sym(S_1)$ has only finitely many elements, infinitely many of the $\beta_i$ must identical. Let $J$ be the set of indices for which this is the case. Notice, that this set need not include 1. Let $j_0$ be the smallest of these indices. Clearly, for $j \in J$  all

 $$\gamma_j = \phi_{j_0}\phi_j^{-1}(\alpha|{S_j})\phi_j\phi_{j_0}^{-1}$$are identical on $S_{j_0}$, and

$$\gamma_{j_0} = \phi_{j_0}\phi_{j_0}^{-1}(\alpha|{S_{j_0}})\phi_{j_0}\phi_{j_0}^{-1} =\alpha|{S_{j_0}}\,. $$

  Notice that the {$\phi_j\phi_{j_0}^{-1}$ are bijections from $S_{j_0}$ to {$S_j$}. Hence, we can assume without loss of generality that $J$ is $\N$, in other words that all $\beta_i$ are identical and that $\beta_1 = \alpha|S_1$.\medskip

  Because $\ptstab(v)$ is finite, we can, proceeding successively, suppose that for any element $\psi \in \ptstab(v)$ the equalities
  $$\psi|S_1 = \phi_i^{-1}(\psi|{S_i}) \phi_i\,$$
  hold.\medskip

Again we can assume without loss of generality that this is already the case for the chosen $S_i$.\medskip

Suppose $\alpha \in \ptstab(v)$ fixes a vertex $\phi_i(u)$ in $S_i$. Then $\alpha(u) = \phi_1^{-1}\alpha\phi_1(u) = $ $  \phi_i^{-1}\alpha\phi_i(u) = \phi_i^{-1}(\alpha(\phi_i(u))) = \phi_i^{-1}\phi_i(u) = u$.  That is, if $\alpha\in \ptstab(v)$ fixes $\phi_i(u)$ in $S_i$ then $\alpha$ fixes $u$ in $S_1$.\medskip

Finally, let $v_1, v_2,\ldots v_{d}$ be the vertices of $S_1$.  Color the vertices of $X=\{v, \phi_1(v_1), \phi_2(v_2)$, $\ldots$, $\phi_d(v_d)\}$ black.  Color all other vertices in the graph white.  Suppose ${\alpha}\in \A(G)$ preserves color classes.  By our choice of distances between the spheres $S_1,\ldots, S_d$, within the set $X$ $v$ is uniquely identified by its distances to the other vertices.\medskip

Thus ${\alpha}\in \ptstab(v)$.  Since ${\alpha}$ must preserve distance to $v$, again by the way distances were chosen, {$\alpha$} cannot interchange vertices of {$\{\phi_1(v_1), \ldots, \phi_d(v_d)\}$}.   Thus $\ptstab(v)$ fixes all $\phi_i(v_i)$, and hence all $v_i$. {Recall that the spheres $S_i$ were chosen so that every non-trivial automorphism in $\ptstab(v)$ acts non-trivially on each  sphere.} Thus if ${\alpha}$ is non-trivial, its action on $S_1$ must be nontrivial, but this is not possible, since it  fixes all elements of $S_1$. So ${\alpha}$ is the identity.
\qed
\medskip

To see that the bound is sharp, consider $P_{\aleph_0}$. It has linear growth with $c = 2$. We know that it can be distinguished by just three black vertices, but not by two. Hence $\rho(P_{\aleph_0}) = 3$, which is the bound given by the {theorem}.\medskip




\section{Finite Automorphism Group}

Suppose the automorphism group of $G \in \Gamma$ is finite. There are two types of automorphisms, those with finite motion and those with infinite motion. Clearly the ones with finite motion form a  subgroup of (the finite group) $\A(G)$, say $B$. Define $W\subseteq V(G)$ to be the orbits under $B$ of all vertices moved by  $B$.  Since $B$ is finite, and all motion in $B$ is finite, $W$ is also finite.  Further $W$ is stabilized setwise by $B$ while elements of $V(G) \setminus W$ are fixed by $B$.\medskip

Consider a distinguishing 2-coloring of $V(G)$ with the color classes $X_1$ and $X_2$ (white and black). We set $Y_1 = X_1 \cap W$ and $Y_2 = X_2 \cap W$. Since $X_1, X_2$ distinguished {the action of $\A(G)$}, $Y_1, Y_2$ distinguish {the action of} $B$, independent of the colors of the elements of $V(G) \setminus W$.\medskip

Let $\{\alpha_1, \alpha_2, \ldots, \alpha_k\}$ be the elements of infinite motion in $\A(G)$. To break {the symmetries of each of these}, we first color all elements of $V(G) \setminus W$ white and {then use the methods of Lemma \ref{le:finite_base_and_cost} to choose vertices $v_1, v_2, \ldots, v_k$ to  color black.} \medskip

Clearly $X_2 \cup \{v_1, v_2, \ldots, v_k\}$ is finite, and hence also
$\rho(G)$. We have thus proved the following lemma.\medskip

\begin{theorem} Let $G$ be a 2-distinguishable graph in $\Gamma$. If $\A(G)$ is finite, then $\rho(G)$ is also finite.
\end{theorem}

\section{Acknowledgements}

Wilfried Imrich was partially supported by
ARRS Slovenia within the EUROCORES Programme EUROGIGA/GReGAS of the European Science
Foundation.\medskip

The authors also wish to thank Simon Mark Smith and Thomas W. Tucker for their careful attention which helped improve the clarity of the paper.


%
% --- Bibliography
%
\begin{thebibliography}{99}
\setlength{\itemsep}{0pt}


\bibitem{AB2} M.\,O.~Albertson, D.~L.~Boutin, Using determining sets to distinguish {K}neser graphs, Electron. J. Combin., 14 (2007), no. 1, Research Paper 20, 9 pp. (electronic).

\bibitem{alco-96}
  M.\,O.~Albertson and K.\,L.~Collins,
  Symmetry breaking in graphs,
  Electron.\ J. Combin., 3 (1996), no. 1, Research Paper 18, approx. 17 pp. (electronic).

\bibitem{B1}  D.~L.~Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin., 13 (2006), no. 1, Research Paper 78, 12 pp. (electronic).

\bibitem{bo-2008} D.~L.~Boutin, Small label classes in 2-distinguishing labelings. Ars Math. Contemp., 1 (2008), no. 2, 154--164.

\bibitem{bo-2013} D.~L.~Boutin, The Cost of 2-Distinguishing Selected Kneser Graphs and Hypercubes, J. Combin. Math. Combin. Comput., 85 (2013), 161--171.


\bibitem{casot-89}    P.~J.~Cameron, R.~Solomon and A.~Turull, Chains of subgroups in the symmetric group, J. Algebra, 127 (1989), no. 2, 340--352.

\bibitem{cuimle-xx}
J.~Cuno, W.~Imrich and F.~Lehner, Distinguishing graphs with infinite motion and nonlinear growth,  Ars Math. Contemp., 7 (2014), no. 1, 201--213.


\bibitem{ha-73}
	R.~Halin, Automorphisms and endomorphisms of infinite locally
finite graphs, Abh. Math. Sem. Univ. Hamburg, 39 (1973), 251--283.


\bibitem{4way-2014} W.~Imrich, S.~M.~Smith, T.~W.~Tucker, and M.~E.~Watkins, Infinite motion and the distinguishing number of graphs and groups, J. Algebraic Comb.,  DOI 10.1007/s10801-014-0529-2.


\end{thebibliography}

\end{document}

{We end this section with a comparison of Theorem \ref{thm:istw}  with a related result. Theorem \ref{thm:istw} is actually rather deep. It asserts that graphs in $\Gamma$ have countable group, infinite motion, and are 2-distinguishable if their automorphisms group is not uncountable.}

{If one knows that $\A(G)$ is countably infinite and that
$\m(G)$ is infinite, then it is no more than a simple exercise to prove that $\D(G) = 2$. No further restrictions or assumptions are needed. For a proof see \cite[Lemma 3.3]{4way-2014}, where this observation is presented in the language of permutation groups. For later reference we state the result in the language of graphs.}

{\begin{lemma}\label{le:trivial}  Let $G$ be a countable graph with infinite motion. If $A(G)$ is countably infinite, then $D(G) = 2$.
\end{lemma}}

{Despite its simplicity, \cite[Lemma 3.3]{4way-2014} has numerous, surprising consequences. They comprise a large part of \cite{4way-2014}.
}


