\documentclass[12pt]{article} \usepackage{e-jc} \specs{}{}{} \usepackage{amsmath,amssymb,amsfonts,amsmath,oldlfont,graphics,oldgerm,latexsym,dsfont} \usepackage{graphicx,hyperref} \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\\ \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}{}\\ \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 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}