\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.78}{22(1)}{2015}

\usepackage{amsmath,amssymb,amsfonts,amsmath,oldlfont,graphics,oldgerm,latexsym,dsfont}

\usepackage{graphicx}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
  \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}

\newcommand{\ce}{$\cal E$ }
\newcommand{\ci}{$\cal I$ }
\newcommand{\co}{$\cal O$ }
\newcommand{\cq}{$\cal Q$ }
\newcommand{\cw}{$\cal Q$ }
\newcommand{\N}{\mathbb{N}}

\newcommand{\cp}{\ensuremath{\mathbin{\Box}}}
\newcommand{\Aut}{\ensuremath{\operatorname{Aut}}}
\newcommand{\End}{\ensuremath{\operatorname{End}}}
\newcommand{\Prob}{\ensuremath{\operatorname{Pr}}}
\newcommand{\id}{\ensuremath{\text{\rm id}}}
\newcommand{\dist}{\ensuremath{\operatorname{dist}}}
\newcommand{\proof}{\noindent{\bf Proof.\ }}
\newcommand{\qed}{\hfill $\square$ \medskip}
\newcommand{\cg}{\overline{G}}
\newcommand{\strong}{\boxtimes}
\newcommand{\rdi}{\mu}

\def\ld{\mbox{ld}\,}
\sloppy

%\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}
\newtheorem{claim}[theorem]{Claim}

%\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

%\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%*****************Title*********************************
\title{\bf The Distinguishing Index of Infinite Graphs}

\author{Izak Broere\\
\small Department of Mathematics and Applied Mathematics,\\[-0.8ex]
\small University of Pretoria, South Africa\\
\small\tt izak.broere@up.ac.za\\
\and
Monika Pil\'sniak\thanks{The research was partially supported by the Polish Ministry of Science and Higher
  Education.}\\
\small AGH University of Science and Technology,\\[-0.8ex]
\small al. Mickiewicza 30, 30-059 Krakow, Poland \\
\small\tt pilsniak@agh.edu.pl }

\date{\dateline{Dec 3, 2013}{Mar 12, 2015}{Mar 30, 2015}\\
\small Mathematics Subject Classifications: 05C25, 05C80, 03E10}

\begin{document}
\maketitle

\begin{abstract}
\noindent
The  distinguishing index $D^\prime(G)$ of a graph $G$ is the least
cardinal $d$ such that $G$ has an edge colouring with $d$ colours
that is only preserved by the trivial automorphism. This is similar
to the notion of the distinguishing number $D(G)$ of a graph $G$,
which is defined with respect to vertex colourings.

We derive several bounds for infinite graphs, in particular, we prove the general bound
$D^\prime(G)\leq\Delta(G)$ for an arbitrary infinite graph.
Nonetheless,  the distinguishing index is at most two for many
countable graphs, also for the infinite random graph and for uncountable tree-like graphs.

We also investigate the concept of the motion of edges and its relationship
with the Infinite Motion Lemma.


 \bigskip\noindent \textbf{Keywords:}  distinguishing index, automorphism,
infinite graph, countable graph, edge colouring, Infinite Motion Lemma

\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}


Albertson and Collins~\cite{alco-96} introduced the {\it (vertex-)distinguishing number}
$D(G)$ of a graph $G$  as the least cardinal
$d$ such that $G$ has a labeling with $d$ labels that is only
preserved by the trivial automorphism.
This  concept has spawned
numerous papers, mostly on finite graphs. But countable  infinite
graphs  have also been investigated with respect to the
distinguishing number; see \cite{smtuwa-xx},
\cite{tu-06}, and \cite{wazh-07}.
For graphs of higher cardinality, see \cite{imkltr-07}.
The corresponding notion for endomorphisms instead of automorphisms is
investigated in \cite{IKLP}.

In this paper, we consider edge colourings of a graph $G$
instead of vertex colourings.
An \textit{edge colouring} of $G$ is a function
$f: E(G) \rightarrow C$ which labels each edge of $G$ with a \textit{colour}
from some set $C$.
Given a graph $G$ with an edge colouring $f$, we say that a graph
automorphism $\varphi : V(G) \rightarrow V(G)$ of $G$ \textit{preserves
the edge colouring} $f$ if $f(xy) = f(\varphi(x)\varphi(y))$ for every edge
$xy \in E(G)$.
The \textit{distinguishing index} $D^\prime(G)$ of a graph $G$ is the
least cardinal $d$ such that $G$ has an edge colouring with
$d$ colours that is only preserved by the trivial automorphism.
Obviously for $K_2$ the distinguishing index is not defined
and it is the only such connected graph.


In our first two results we give sufficient conditions for a graph $G$
to have $D^\prime(G) \leq 2$.
Clearly, $D^\prime(G) = 1$ if and only if $G$ is an \textit{asymmetric} graph,
that is, a graph of which the automorphism group $Aut(G)$ is the trivial group.
The following observation shows why $D^\prime(G) = 2$ should be
expected in most circumstances.

\begin{proposition}\label{2}
If the graph $G$ has an asymmetric spanning subgraph,
then $D^\prime(G) \leq 2$.
\end{proposition}

\proof
We merely need to remark that the
colouring, in which the edges of the asymmetric spanning subgraph of
$G$ are coloured with 0 and every other edge (if any) with 1, is an
edge colouring of $G$ which is only preserved by the identity so
that $D^\prime(G) \leq 2$.
\qed


\begin{proposition}\label{1}
If the connected graph $G$ has a vertex colouring using only two colours
such that there is no automorphism interchanging these colours
and only the identity preserves colours, then $D^\prime(G) \leq 2$.
\end{proposition}

\proof
Given such a vertex colouring, using, say, $a$ and $b$ as colours,
colour all edges between vertices with
like colours 1 and all edges between vertices with different colours 2.
Consider any vertex $v$ and assume it is coloured $a$.
Then all neighbours of $v$ incident with edges coloured 1 have colour $a$
and all others have colour $b$.
Hence, since $G$ is connected, one can recover the original vertex colouring
of the graph up to a permutation of the colours
simply by knowing the colour of $v$.
It follows that any automorphism preserving edge colours either
interchanges colours, and no such automorphism exists, or
preserves the colours of the vertices, and hence is the identity.

Therefore $D^\prime(G) \leq 2$.
\qed

For examples in which $D^\prime(G) < D(G)$, one can observe that
$D^\prime(K_n)=D^\prime(K_{p,p})=2$, for any $n\geq 6$ and for any $p\geq 4$
while $D(K_{n+1})=D(K_{n,n})=n+1$.

For finite graphs this concept is investigated by Kalinowski and Pil\'sniak in
\cite{KP} and \cite{KP-motion}.


In \cite{KP}, the following general upper bound was proved.

\begin{theorem}\label{KP1}
If $G$ is a finite connected graph of order $n\geq 3$, then
$D^\prime(G)\leq D(G)+1$. Moreover, if $\Delta$ is the maximum degree of
$G$, then $D^\prime(G)\leq \Delta$, unless $G$ is a $C_3$, $C_4$ or~$C_5$.
\end{theorem}
\smallskip

The aim of this paper is to present some fundamental results for
the distinguishing index of infinite graphs.
We obtain general theorems for countable  and uncountable graphs, and a relationship with
the Infinite Motion Lemma.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A general bound for infinite graphs}\label{infinite}

In this section we consider infinite graphs and
prove an analogue of Theorem \ref{KP1} for them.
In the case of vertex colourings, Imrich, Klav{\v{z}}ar and Trofimov
showed in \cite{imkltr-07} that for a connected, infinite graph $G$ the
distinguishing number is at most the maximum  degree  $G$.
We will prove the same for the distinguishing index in a similar way.
In the sequel, we denote \textit{the sphere at $x$ with radius $k$},
which is the set of all vertices of $G$ at distance $k$ from $x$,
by $S_x(k)$.

\begin{theorem}\label{delta} %%Thm 4
Let $G$ be a connected, infinite graph such that the
degree of every vertex of $G$ is not greater than $\Delta$. Then
$D^\prime(G)\leq \Delta$.
\end{theorem}

\proof Suppose first that $\Delta$ is a finite cardinal.
Then $G$ is an infinite graph of bounded finite degree. So $G$ contains
a one-way infinite ray $R$.
Let $x$ be the first vertex of $R$.
We colour all edges of $R$ with $\Delta$; no other edge will receive the colour $\Delta$.
Since an edge incident with $x$ is coloured $\Delta$ and $x$ is adjacent
to exactly one vertex with the edge between them coloured $\Delta$, while
any other vertex $y$ of $R$ is adjacent to two vertices with the edges
between $y$ and these vertices coloured $\Delta$,
$x$ is fixed by every automorphism of $G$ which preserves edge colours.
Consequently, $R$ is fixed point-wise by every such automorphism.

Let $T$ be a breadth-first spanning tree rooted
at $x = x_1$ with a given enumeration.
We now colour edges at vertices taken in that enumerative order.
First colour the edges at $x$ other than the one with
colour $\Delta$ by $\{1,\ldots,\Delta-1\}$.
Having coloured edges at $x_1,\ldots, x_n$, vertex $x_{n+1}$ has one
edge $e$ already coloured previously.
Colour the remaining edges with different
colours $\{1,\ldots,\Delta-1\}$ (one of these will have already been used on $e$).
Colour all edges not in $T$ by 1.
Any colour-preserving automorphism $\varphi$ fixes $x$ as it is
the only vertex incident to exactly one vertex labeled $\Delta$.
Thus it also fixes all edges incident to $x$, since they have different colours.
Thus all vertices at the next level of tree $T$ are fixed.
Continuing this way level by level in the
tree $T$, we conclude that $\varphi$ fixes all vertices and hence is the identity.


Assume next that the degree of $G$ is not finite. The vertex set of $G$ is the union over $k$ of the vertices in the spheres $S_x(k)$.
Since the number of vertices in every such sphere is at most $\Delta$
and the graph is connected, we
have that $|V(G)|\leq\Delta$, hence also
$|E(G)|\leq\Delta$.
Hence it is possible to colour the edges of $G$ using each
colour at most once.
\qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Trees and tree-like graphs}

Let us start with some simple examples.
An infinite ray (of any cardinality) is an asymmetric graph, so the
distinguishing index of each infinite ray is one.
Consider the following colouring of the edges of the two-way infinite
path $P_{\infty}$: colour any two incident edges
and a third edge, not incident with them, with 0 and colour all the
other edges with 1.
Since this colouring is only preserved by the identity automorphism,
it follows that $D^\prime(P_{\infty})=2$.

On the other hand there exists, for any $d\in\N$, a countable locally
finite tree, such that  the distinguishing index is equal to $d$.
An example of such a tree can be obtained as follows:
consider an infinite ray $x_0, x_1, x_2, \dots$ with
$d-1$ pendant vertices added to any one (fixed) $x_i$, for some $i\geq 1$.
With this type of example we can furthermore observe that the distinguishing
index can even be infinite: simply take $d$ to be infinite.
These examples serve as motivation to consider trees without leaves
(or, with at most one leaf) and, more general, tree-like graphs.

Let $x$ be a vertex of a graph $G$ and denote the set of vertices
adjacent to $x$ by $N(x)$. We denote \textit{the ball at $x$ with radius $k$},
which is the set of all vertices of $G$ at distance at most $k$ from $x$,
by $B_x(k)$.

By a \textit{tree-like graph} we mean a connected graph $G$ that contains
a vertex, say  $x$, with the following property: for any vertex $y \neq x$ there
exists a vertex $z$ such that $\{y\}= N(z)\cap B_x(d(x,z)-1)$.
Such a vertex $x$ will be called \textit{central} in the graph $G$.

Notice that in every vertex $y$ of a tree-like graph there starts
an infinite ray $(y_0, y_1, y_2,\dots)$ such that $d(x, y_i)=d(x,y)+i$,
$y_0 = y$ and $y_1=z$.
In particular, a tree $T$ is a tree-like graph if and only if $T$ has at most one leaf.

\begin{theorem}\label{tree-like}  %Thm 5
Let $G$ be a tree-like graph such that the
degree of every vertex of $G$ is not greater than $2^{\aleph_0}$. Then
$D^\prime(G)\leq 2$.
\end{theorem}

\proof Let $f_V$ be a colouring of vertices of $G$ preserved only by the
identity and defined as in the proof of Theorem 4.2 in \cite{imkltr-07}.
In particular, a central vertex $x$ is unique such that all its neighbours have colour 0.
Moreover,
consider a spanning subgraph $F$ of $G$ with the property that $x'x''\in E(F)$
if  and only if  $\{x'\}= N(x'')\cap B_x(d(x,x'')-1)$ or $\{x''\}= N(x')\cap B_x(d(x,x')-1)$.
So $F$ is a forest with no finite component, uniquely defined and with at most $2^{\aleph_0}$ connected components ${F_i}$.
The colouring $f_V$ is given in such way that:

1. in the connected component $F_0$ of $F$ containing $x$, and the set of neighbours  $v$
of $x$ in $F$ (coinciding with the set of neighbours of $x$ in $G$) we have:
$f_V(x) = 0$ and $f_V(v) = 0$;

2. in every remaining connected component $F_i$ a unique vertex $x_{F_i}$ is coloured with 1 and
$x_{F_i}$ is the only vertex of $F_i$ for which all neighbours in ${F_i}$ are coloured with 0;

3. for any distinct $i\neq i'$ the colouring  tree ${F_i}$ and  tree $x_{F_i'}$ are not isomorphic.

Define a colouring $f:\, E(G)\rightarrow\{0,1\}$ as follows.
If an edge joins two vertices from different spheres with center $x$,
then it obtains the colour of its end vertex which is closer to $x$.
If an edge joins two vertices of the same sphere,
then it is coloured with 0.
In other words,

- for every edge $ab$ such that $d(x,a)=d(x,b)-1$ we get $f(ab)=f_V(a)$ and

- for every edge $ab$ such that $d(x,a)=d(x,b)$ we get $f(ab)=0$.

Now let $\varphi$ be an automorphism of $G$ preserving $f$.
Note that $x$ is the
only vertex of $G$ for which all edges in the ball $B_x(2)$ are coloured with 0.
Therefore $x$ is fixed by $\varphi$.
Suppose now that there exist two distinct  edges
$ab$ and $cd$ with the same colour $\alpha$ such that
$\varphi(a)=c$ and $\varphi(b)=d$. Since $\varphi$ preserves distances, there
exist $k,\, k'\geq 2$  and the vertices $a$ and $c$ belong to the sphere $S_x(k)$, and the
vertices $b$ and $d$ belong to the sphere $S_x(k')$.
Assume that $k\leq k'$.
Then the infinite ray $R_b$ starting at vertex $b$
(there exists one by the definition of a tree-like
graph) is mapped into an infinity ray $R_d$ with starting vertex $d$.
Since the restrictions of $f_V$ to distinct connected components of $F$ give pairwise
non-isomorphic labeled components and by the definition of $f$,
we obtain a contradiction with the fact that $f_V$ is preserved by $\varphi$.
Hence the colouring $f$ is preserved only by the identity. \qed

\bigskip

We can observe that for tree-like graphs, the
central vertex $x$ is characterized as the only vertex having
all its neighbours of the same colour.
Thus there is no colour-reversing automorphism,
and by Proposition \ref{1} we have $D'(G) \leq 2$.
So we can obtain another proof the above theorem if $G$ is denumerable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The countable random graph}

It is useful to remark that, given a graph $G$ with an edge
colouring $f$ and an automorphism $\varphi$ which
preserves edge colours, then  for every vertex
$x$ of $G$ and every colour $c$,
the number of edges at $x$ with colour $c$ is equal to
the numbers of edges at $\varphi(x)$ with colour $c$.
Let us call a triple $G$, $f$ and $\varphi$ for which
this property holds for some colour $c$
an \textit{edge number preserving triple at $c$}.

We shall now show that many countable graphs,
including the Rado graph (see \cite{Ra64}, also known as the random graph),
have distinguishing index $D^\prime(G) \leq 2$.
In order to do so, we say that a countable graph $G$ has \textit{good degrees}
if it is possible to label the vertices with the natural
numbers $\N$ such that the degree constraint ${\mbox {deg}}_G(n) \geq 2n-1$
is satisfied by every vertex $n \in \N$.
Clearly, every countable graph $G$ of which every vertex has
denumerable degree, including therefore the Rado graph,
has good degrees.

\begin{theorem}\label{good degrees}
For every countable graph $G$ with good degrees there is an edge
colouring $f$ of $G$ with colours $0$ and $1$ such that the number
of edges of colour $0$ incident to a given vertex $x$ is different
from the number of edges of colour $0$ incident to a vertex $y$
whenever $x \neq y$.
\end{theorem}

\begin{proof}
Consider any countable graph $G$ with good degrees.
Then we may assume that the vertex set is $\N$ and that
${\mbox {deg}}_G(n) \geq 2n-1$ for each $n \in \N$.

Our strategy is to describe, in a recursive manner,
an edge colouring of $G$ with the property that,
for every $n \in \N$,
there are exactly $n$ edges incident to a vertex
$n$ with colour $0$.
Consider, for any $n \in \N$, the partition $N(n) = B(n) \cup A(n)$
of the neighbourhood of a vertex $n$ obtained
by letting $x \in B(n)$ if $x \in N(n)$
and $x <n$ (the vertices before $n$) while
$y \in A(n)$ if $y \in N(n)$ and $y > n$
(the vertices after $n$).
Note that, since $|N(n)| \geq 2n-1$ for each $n \in \N$
while $|B(n)| \leq n-1$ (since there are only $n-1$ vertices
$x$ satisfying $x < n$), it follows that $|A(n)| \geq n$
for each $n \in \N$.

We are now ready to describe the colouring of the
edges mentioned above, using only the two colours $0$ and $1$.
We describe our choices for edges incident with
vertices $1$ and $2$ first.
Identify at vertex $1$ the least vertex $m$ such that
$1m \in E(G)$ and colour this edge $0$; every other edge
incident with vertex $1$ (if any) is coloured with $1$.
Next we consider vertex $2$ and we distinguish two cases:  \\
If there is an edge $12 \in E(G)$, it will already have colour $0$
and we choose the smallest member from $A(2)$ to colour the edge between
it and 2 with $0$ too;
all other edges from 2 to vertices of $N(2)$ are now coloured with $1$.
If, on the other hand, $12 \not\in E(G)$, then the two smallest vertices
$m$ and $m^\prime$ in $A(2)$ are chosen and the edges $2m$ and $2m^\prime$
are coloured $0$; all other edges of $N(2)$ are then coloured $1$.
Note that in both cases the two edges incident to the vertex $2$
which received colour $0$ are indeed the two edges $2x$ and
$2y$ with $x$ and $y$ the smallest members of the set $N(2)$.

Now suppose that, for some $k \geq 2$, all the edges
incident to each of the vertices $1, 2, \ldots, k$
have been coloured in such a way that, for each $j \leq k$,
there are $j$ edges that received colour $0$ and they
are exactly the edges of the form $jx$ where $x$ ranges over the subset
of $N(j)$ containing its smallest $j$ members.
Furthermore, suppose that all edges of the form
$xj$, for each $j \leq k$ and $x \in B(j)$, have been
coloured with $0$ or $1$.
In order to proceed to edges incident to the vertex $k+1$, suppose there are
$m$ vertices $y$ with $y < k+1$ for which
the edges $y(k+1)$ have already received the colour $0$.
Then we colour the remaining, i.e., not yet coloured, edges
incident to the vertex $k+1$ as follows:  Choose the
$k+1-m$ smallest members from $A(k+1)$ and, for each such
vertex $z$, colour the edge $(k+1)z$ with colour $0$;
all other edges of $A(k+1)$ are now coloured $1$.
Then clearly, all the edges incident with vertex $k+1$
have been coloured; and exactly $k+1$ of them are coloured $0$.

Repeating this recursive process clearly delivers the required
edge colouring of $G$ with the property that,
for every $n \in \N$, there are exactly $n$ edges incident to vertex
$n$ with colour $0$.
Hence this colouring has the properties claimed by the Theorem.
\end{proof} \qed

\begin{corollary} %%Cor 7
For every countable graph $G$ with good degrees there is an edge
colouring of $G$ in the colours $0$ and $1$ such that,
with respect to any automorphism $\varphi$ of $G$, the triple $G$, $f$ and
$\varphi$ is edge number preserving at 0.
\end{corollary}

\begin{corollary} %%Cor 8
Every countable graph $G$ with good degrees
satisfies $D^\prime(G) \leq 2$.
\end{corollary}

\begin{proof}
Let $f$ be colouring of the edges which is described in Theorem \ref{good degrees}
and let $\varphi$ be any automorphism of $G$.
Then we have an edge number preserving triple $G$, $f$ and
$\varphi$ at 0.
Hence, for any $n, m \in \N$, if $\varphi(n) = m$, then $n = m$
since the number of edges of colour $0$ incident to $n$ is
$\varphi(n)$ and is $n$.
But this means that $\varphi$ is the identity automorphism $\id_{V(G)}$;
showing that $D^\prime(G) \leq 2$.
\end{proof} \qed


It is interesting to note that Theorem \ref{good degrees} implies that
a graph on the rationals has distinguishing index equal to two whereas
the distinguishing number is infinite.
So $D$ and $D'$ can have an arbitrary large difference for infinite graphs
as they can have for finite graphs.
\bigskip


We remark that the above theorem and corollaries merely
repeat the idea in the proof of Proposition \ref{2} since the
edges with colour 0 form an asymmetric spanning subgraph.

\begin{corollary} %%Cor 9
The random graph $R$ has edge distinguishing number $2$.
\end{corollary}

\begin{proof}
It has already been remarked that the graph
$R$, being an example of a countable graph in which
every vertex is of denumerable degree,
has good degrees so that $D^\prime(R) \leq 2$ by the
previous corollary.

To complete the proof we merely need to remark that
$D^\prime(R) \neq 1$ since $R$ has a non-trivial automorphism
(in fact, it has a very large automorphism group by \cite{Large-aut-group})
which necessarily preserves the colours if only one colour is used.
\end{proof}\qed

We complete this section by giving an example of a denumerable graph
$H$ with $V(H) = \N$ and with good degrees in which every
vertex has finite degree. Define the edges of $H$
through a recursive construction as follows:
Let $12 \in E(H)$.  For every $n \geq 2$ we now choose
edges of the form $kn$ with $n< k$ as follows:
If $m$  edges of the form $xn$ with $x < n$ have
already been chosen (while describing the edges incident
to vertices $j$ with $j < n$), then we complete the choice of edges
incident to $n$ by choosing $2n-1-m$ edges of the form
$nk$ with $k > n$.
This graph, which is not unique since different choices are possible,
clearly has ${\mbox {deg}}_H(n) = 2n-1$ for each $n \in \N$.

A direct approach to describe the edges for such a graph $H$
can be obtained by taking, for each $n \geq 2$, all edges of the form
$mn \in E(H)$ if $m \in \{n-1, n+1, n+2, \ldots, 3n-2 \}$.
It is easy to see that, indeed, each vertex $n$
has a finite degree and that ${\mbox {deg}}_H(n) \geq 2n-1$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Edge-Motion Lemma}

Russel and Sundaram  \cite{rusu-98} introduced the concept of motion and they proved that the distinguishing
number of a graph is small when every automorphism of $G$ moves many
elements.
Kalinowski and Pil\'sniak in \cite{KP-motion} considered the
concept of the edge-motion of a non-trivial automorphism of a graph.
The {\it motion $m(\varphi)$ of a non-trivial automorphism}
$\varphi: \,V\rightarrow V$ of a finite graph $G=(V,E)$
is the number of elements it moves:
$$m(\varphi)  =  |\{v \in V(G)\,|\, \varphi(v) \neq v\}|,$$
and the \textit{motion of a graph} $G$ is
$$m(G) = \min_{\varphi \in \Aut(G)\setminus\{\id\}} m(\varphi).$$

Let $\varphi^{*}: \,E\rightarrow E$ be the bijection induced by $\varphi:
\,V\rightarrow V$.
We denote by $m^{*}(\varphi)$ the {\it edge-motion}
of a nontrivial automorphism  $\varphi: \,V\rightarrow V$ of a graph
$G$; it is the number of edges it moves:
$$m^{*}(\varphi)  =  |\{uv \in E\,|\, \varphi(u)\varphi(v) \neq uv\}|,$$
and the \textit{edge-motion of a graph} $G$ is
$$m^{*}(G) = \min_{\varphi \in \Aut(G)\setminus\{\id\}} m^{*}(\varphi).$$

For example, $m(K_n)=2$ and $m^{*}(K_{n}) = 2n-4$,
$m(C_{2n}) =m^{*}(C_{2n})=2n-2$, $m(P_{2n+1}) =2n=m^{*}(P_{2n+1})$,
but $m(P_{2n}) =2n=m^{*}(P_{2n})+2$.

A comparison between the graph-parameters $m$ and $m^{*}$ can be found
in \cite{KP-motion}; the main observation is

\begin{theorem}\cite{KP-motion} Let $G$ be a connected graph of order $n\geq 3$ with  minimal degree $\delta$. Then
$$m^{*}(G)\geq \left\{\begin {array}{ll} \frac 12(\delta-1)m(G),& {\rm if}\; \delta\geq 3, \\m(G)-2, &{\rm if} \;\delta\leq 2. \end{array} \right.$$
\end{theorem}

There is also a upper bound for the edge motion, $m^*(G)\leq \Delta(G)m(G).$
This, together with the Motion Lemma, gives a
further explanation for why $D'$ is generally much less than $D$.

These definitions can clearly be used verbatim to define $m(G)$
and $m^{*}(G)$ for an infinite graph $G$.
The following general result for finite graphs can also be found in \cite{KP-motion}.

\begin{lemma}[Edge-Motion Lemma]
\label{EML} For any finite graph $G$ we have:  if
$$d^{\frac{m^{*}(G)}{2}} \geq  |\Aut(G)|,$$
then $D^\prime(G)\leq d$.
\end{lemma}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip

Let $G$ be an infinite graph with infinite edge-motion
$m^{*}(G)$.
Note that
$$d^{m^{*}(G)/2} = d^{m^{*}(G)} = 2^{m^{*}(G)} \mbox{ if } d \geq 2$$
in this situation. Thus we obtain the natural generalization of
Theorem \ref{EML}, which we formulate as a conjecture.
\bigskip


{\bf Edge-Motion Conjecture.} \emph{Let $G$ be a connected, infinite
graph with edge-motion $m^{*}(G)$.
If the automorphism group $\Aut(G)$ of $G$ is non-trivial and $$2^{m^{*}(G)} \geq
|\!\Aut(G)|,$$ then $D^\prime(G) \leq 2$.} \medskip

Let us first consider the case where $G$ is countable. If $m^{*}(G)$
is infinite, then $m^{*}(G) = \aleph_0$ and $2^{m^{*}(G)} =
2^{\aleph_0} = \textswab{c}$, where $\textswab{c}$ denotes he
cardinality of the continuum.

Furthermore, for countable graphs we have $|\Aut(G)| \leq
\aleph_0^{\aleph_0} = 2^{\aleph_0} = \textswab{c}$. This means that the inequality $2^{m^{*}(G)} \geq |\!\Aut(G)|$ is always satisfied for
countably infinite graphs with infinite edge-motion. This motivates
the following conjecture.
\bigskip

{\bf Infinite Edge-Motion Conjecture.} \emph{Let $G$ be a countable
connected graph with infinite edge-motion. Then the distinguishing
index of $G$ is at most two.}
\medskip

We  now show that graphs which have countable automorphism groups
and infinite edge-motion have distinguishing index at most two.
We start with a slightly more general result.
Its proof is almost verbatim the same as the analogous to proof of Theorem 6
in \cite{IKLP}, but we include this short proof for the sake of completeness.

\begin{theorem}\label{TTconj_w}
Let $G$ be a graph with infinite edge-motion whose automorphism
group is countable. Let $f$ be a random $2$-colouring of edges where
all edges have been coloured independently and assume that there is
an $\varepsilon
> 0$ such that for every edge $e$ the probability that it is
assigned the colour $c \in \{\text{black}, \text{white}\}$ satisfies
\[
    \varepsilon \leq {\operatorname{Prob}}\left [f(e) = c \right ] \leq 1-\varepsilon.
\]
Then $f$ is almost surely distinguishing.
\end{theorem}

\begin{proof}
First, let $\varphi \in \Aut (G)$ be a fixed automorphism of $G$.
Since
the edge-motion of $\varphi$ is infinite we can find infinitely many
pairs $\{e_i, \varphi^{*} (e_i) \}$ of distinct edges.
Clearly the colourings of
these pairs are independent and the probability that $\varphi^{*}$
preserves the colouring in  any of the pairs is bounded from above by
some constant $\varepsilon' < 1$. Now
\[
{\operatorname{Prob}}\left [\varphi^{*} \text{ preserves }f \right ]
\leq {\operatorname{Prob}} \left [ \forall i \colon f(e_i) =
f(\varphi^{*} (e_i)) \right ] = 0.
\]

Since there are only countably many automorphisms we can use
$\sigma$-subadditivity of the probability measure to conclude that
\[
{\operatorname{Prob}} \left[ \exists \varphi \in \Aut (G) \colon
\varphi^{*} \text{ preserves f} \right] \leq \sum_{\varphi \in \Aut (G)}
{\operatorname{Prob}}\left [\varphi^{*} \text{ preserves }f \right ] =
0
\]
which completes the proof. \qed
\end{proof}

We will usually only use the following Corollary of Theorem
\ref{TTconj_w}.

\begin{corollary} \label{countmon}
Let $G$ be a graph with the infinite edge-motion whose automorphism
group is countable. Then $$D^\prime(G) \leq 2.$$
\end{corollary}


Additionally we can remark:

\begin{corollary} Let $G$ be a infinite, locally finite, 3-connected planar graph
with infinite edge-motion.
Then $D^\prime(G) \leq 2$.
\end{corollary}


\begin{corollary}
Let $G$ be an finite, locally finite, connected graph of linear
growth with infinite edge-motion.
Then $D^\prime(G) \leq 2$.
\end{corollary}

{\proof} In both cases the graphs have a countable group of automorphisms. \qed


\bigskip


The next theorem shows that the edge-motion conjecture is true if
$m^{*}(G) =|\!\Aut(G)|$, even if $m^{*}(G)$ is not countable.
The proof of this theorem is identical to the proof of
Theorem 4.4 in \cite{CIL}, so we omit it.

\begin{theorem}
\label{thm:special} Let $G$ be a connected graph with uncountable
edge-motion.
Then $$|\!\Aut(G)| \leq m^{*}(G)$$ implies $D^\prime(G)=2$.\qed
\end{theorem}

\begin{corollary}
\label{cor:special} Let $G$ be a connected graph with uncountable
edge-motion. If the general continuum hypothesis holds, and if $
|\!\Aut(G)| < 2^{m^{*}(G)}\!,$\, then $D^\prime(G) =2$.
\end {corollary}


\proof By the generalized continuum hypothesis $2^{m^{*}(G)}$ is the
successor of $m^{*}(G)$. Hence, the inequality $2^{m^{*}(G)}
>|\!\Aut(G)|$ is equivalent to ${m^{*}(G)} \geq |\!\Aut(G)|$. \qed

%\bigskip

\subsection*{Acknowledgement}

%\noindent
The authors are very grateful to an anonymous referee whose
very useful comments and suggestions greatly improved the paper.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}


\bibitem{alco-96}
  M.\,O.~Albertson, K.\,L.~Collins.
  \newblock Symmetry breaking in graphs. \newblock{\em
  Electron.\ J. Combin.} 3:\#R18, 1996.

\bibitem{Large-aut-group}
P.\,J.~Cameron. \newblock The Rado graph and the Urysohn space. \newblock
 {\url{http://www.maths.qmul.ac.uk/~pjc/preprints/stpbg.pdf}}


\bibitem{CIL}J.~Cuno, W.~Imrich, F.~Lehner. \newblock Distinguishing graphs with infinite  motion and nonlinear growth. \newblock{\em Ars Math. Contemp.} 7:201--213, 2014.

\bibitem{IKLP}W.~Imrich, R.~Kalinowski, F.~Lehner, M.~Pil\'sniak. \newblock Endomorphism Breaking in Graphs. \newblock{\em Electron. J. Combin.} 21(1):\#P1.16, 2014.

\bibitem{imkltr-07}
    W.~Imrich, S.~Klav{\v{z}}ar, V.~Trofimov. \newblock
    Distinguishing infinite graphs. \newblock{\em Electron. J. Combin.}
    14:\#R36, 2007.

\bibitem{imsm-xx}
    W.~Imrich, S.\,M.~Smith, T.~Tucker, M.\,E.~Watkins. \newblock
    Infinite Motion and 2-Distinguishability of Graphs and
Groups. \newblock {\em J. Algebr. Comb.} 2015. \doi{10.1007/s10801-014-0529-2}


\bibitem{KP} R.~Kalinowski, M.~Pil\'sniak. \newblock Distinguishing graphs by edge-colourings. \newblock
{\em Europ. J. Combin.} 45:124--131, 2015.

\bibitem{KP-motion} M.~Pil\'sniak. \newblock Edge Motion and the Distinguishing Index. \newblock {\em Preprint MD 076}. \newblock{\url{http://www.ii.uj.edu.pl/preMD}}


\bibitem{Ra64}
R. Rado. \newblock
Universal graphs and universal functions. \newblock{\em
Acta Arith.} 9:331--340, 1964.

\bibitem{rusu-98}
    A.~Russell, R.~Sundaram. \newblock A note on the asymptotics and computational complexity of graph distinguishability. \newblock{\em Electron. J. Combin.} 5:\#R23, 1998.

\bibitem{smtuwa-xx}
    S.\,M.~Smith, T.~Tucker, M.\,E.~Watkins. \newblock
    Distinguishability of Infinite Groups and
    Graphs. \newblock{\em Electron. J. Combin.} 19:\#P27, 2012.


\bibitem{tu-06}
  T.~Tucker. \newblock Distinguishing Maps \newblock{\em Electron. J. Combin.} 18:\#R50, 2011.

\bibitem{wazh-07} M.\,E.~Watkins, X.~Zhou. \newblock Distinguishability of Locally Finite Trees. \newblock{\em Electron. J. Combin.} 14:\#R29, 2007.


\end{thebibliography}


\end{document}
