ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 201-213
Distinguishing graphs with infinite motion and nonlinear growth
Johannes Cuno *
Institut fur Mathematische Strukturtheorie, Technische Universität Graz Steyrergasse 30/III, 8010 Graz, Austria
Wilfried Imrich
Department Mathematik und Informationstechnologie Montanuniversitat Leoben, 8700 Leoben, Austria
The distinguishing number D(G) of a graph G is the least cardinal d such that G has a labeling with d labels which is only preserved by the trivial automorphism. We show that the distinguishing number of infinite, locally finite, connected graphs G with infinite motion and growth o(n2/ log2 n) is either 1 or 2, which proves the Infinite Motion Conjecture of Tom Tucker for this type of graphs. The same holds true for graphs with countably many ends that do not grow too fast. We also show that graphs G of arbitrary cardinality are 2-distinguishable if every nontrivial automorphism moves at least uncountably many vertices m(G), where m(G) > |Aut(G)|. This extends a result of Imrich et al. to graphs with automorphism groups of arbitrary cardinality.
Keywords: Distinguishing number, automorphisms, infinite graphs. Math. Subj. Class.: 05C25, 05C63, 05C15, 03E10.
*All three authors, namely Johannes Cuno, Wilfried Imrich, and Florian Lehner, acknowledge the support of the Austrian Science Fund (FWF), project W1230-N13.
E-mail ¡addresses: cuno@math.tugraz.at (Johannes Cuno), imrich@unileoben.ac.at (Wilfried Imrich), f.lehner@tugraz.at (Florian Lehner)
Florian Lehner
Institut für Geometrie, Technische Universität Graz Kopernikusgasse 24/IV, 8010 Graz, Austria
Received 11 May 2012, accepted 19 March 2013, published online 22 April 2013
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
202
Ars Math. Contemp. 7 (2014) 201-213
1	Introduction
Albertson and Collins [1] introduced the distinguishing number D(G) of a graph G as the least cardinal d such that G has a labeling with d labels which is only preserved by the trivial automorphism.
This seminal concept spawned many papers on finite and infinite graphs. We are mainly interested in infinite, locally finite, connected graphs of polynomial growth, see [8], [15], [13], and in graphs of higher cardinality, see [9], [11]. In particular, there is one conjecture on which we focus our attention, the Infinite Motion Conjecture of Tom Tucker.
Before stating it, we introduce the notation m(fy) for the number of elements moved by an automorphism fy, and call m(fy) the motion of fy. In other words, m(fy) is the size of the set of vertices which are not fixed by fy, that is, the size of its support, supp(fy).
The Infinite Motion Conjecture of Tom Tucker. Let G be an infinite, locally finite, connected graph. If every nontrivial automorphism of G has infinite motion, then the distinguishing number D(G) of G is either 1 or 2.
For the origin of the conjecture and partial results compare [13]. The conjecture is true if Aut(G) is countable, hence we concentrate on graphs with uncountable group.
The validity of the conjecture for graphs with countable group follows from either one of two different results in [10]. One of them replaces the requirement of infinite motion by a lower and upper bound on the size of the automorphism group. It asserts that every infinite, locally finite, connected graph G whose automorphism group is infinite, but strictly smaller than 2N°, has countable group, infinite motion, and distinguishing number 2. For a precise formulation see Theorem 4.1. The proof is not easy and follows from results of either Halin [6], Trofimov [14], or Evans [3].
The other one relaxes the condition of local finiteness and requires that the group is at most countable. It asserts that countably infinite, connected graphs with finite or countably infinite group and infinite motion are 2-distinguishable, no matter whether they are locally finite or not, see Theorem 4.2. The proof is short and elementary.
For uncountable connected graphs with countable motion the Infinite Motion Conjecture need not be true. We turn to this case in Section 4, suggest a version of the conjecture for uncountable connected graphs, and prove its validity under a bound on the size of the automorphism group.
2	Preliminaries
Throughout this paper the symbol N denotes the set {1, 2,3,...} of positive integers, whereas the symbol N0 refers to the set {0,1,2, 3,...} of non-negative integers.
Let G be a graph with vertex set V(G). Let X be a set. An X-labeling l of G is a mapping l : V(G) ^ X. For us X will mostly be the set {black, white}. In this case, we speak of a 2-coloring of G.
Let l be an X-labeling of G. Consider an automorphism fy G Aut(G). If, for every v G V(G), l(fy(v)) = l(v), we say that l is preserved by fy. If this is not the case, we say that l breaks fy. An X-labeling l of G is called distinguishing if it is only preserved by the trivial automorphism. The distinguishing number D(G) of G is the least cardinal d such that there exists a distinguishing X-labeling of G with |X | = d.
Given a group A equipped with a homomorphism fy : A ^ Aut(G), we say that A acts on G. Moreover, we say that A acts nontrivially on G if there is an a G A such that fy(a)
J. Cuno et al.: Distinguishing graphs with infinite motion and nonlinear growth	203
moves at least one vertex of G. By abuse of language we write a(v) instead of ^(a)(v) and say that an X-labeling l of G is preserved by a e A if it is preserved by ^(a) e Aut(G).
The ball with center v0 G V(G) and radius r is the set of all vertices v e V(G) with dG(vo, v) < r and is denoted by BG (r), whereas SG (r) stands for the set of all vertices v e V(G) with dG(v0, v) = r. We call it the sphere with center v0 e V(G) and radius r. If G is clear from the context, we just write Bv0 (r) and Sv0 (r) respectively. For terms not defined here we refer to [7].
Although our graphs are infinite, as long as they are locally finite, all balls and spheres of finite radius are finite. The number of vertices in BVG (r) is a monotonically increasing function of r, because
r
BG(r)| = E|SvG0(i)| and |SG0(i)| > 1.
i=0
Nonetheless, the growth of |B^ (r) | depends very much on G, and it is helpful to define the growth rate of a graph.
We say that an infinite, locally finite, connected graph G has polynomial growth if there is a vertex v0 e V(G) and a polynomial p such that
Vr e N : |BG0 (r)| < p(r) .
It is easy to see that this implies that all functions |BVf(r) | are bounded by polynomials of the same degree as p, independent of the choice of v e V(G). In this context it should be clear what we mean by linear and quadratic growth. Observe that the two-sided infinite path has linear growth, and that the growth of the grid of integers in the plane is quadratic. We say that G has exponential growth if there is a constant c > 1 such that
Vr e N0 : |BG0 (r)| > cr .
Notice that homogeneous trees of degree d > 2, that is, infinite trees where every vertex has the same degree d, have exponential growth. For the distinguishability of such trees and tree-like graphs, see [16] and [9].
We are mainly interested is the distinguishability of infinite, locally finite, connected graphs of polynomial growth. For us, the following lemma will be helpful.
Lemma 2.1. Let A be a finite group acting on a graph G. If a coloring of G breaks some element of A, then it breaks at least half of the elements of A.
Proof. The elements of A that preserve a given coloring form a subgroup. If some element of A is broken, then this subgroup is proper and thus, by Lagrange's theorem, cannot contain more than half of the elements of A.	□
If the action is nontrivial, then we can always find a coloring that breaks at least one element. Hence, we have the following result.
Lemma 2.2. Let G be a graph. If A is a finite group acting nontrivially on G, then there exists a 2-coloring of G that breaks at least half of the elements of A.
The proof of Lemma 2.2 is based on the fact that A is a group. But a very similar result holds for any finite family of nontrivial automorphisms, as the following lemma shows.
204
Ars Math. Contemp. 7 (2014) 201-213
Lemma 2.3. Let G be a finite graph. If A is a finite set equipped with a mapping ^ : A ^ Aut(G) \ {id}, then there exists a 2-coloring of G that breaks ^>(a) for at least half of the elements of A.
Proof. Let V(G) = {vi, v2,..., vn}. For every k G {1,2,..., n}, let Ak be the set of all a G A with supp(^(a)) C {v1, v2,..., vk}. We show by induction that the assertion holds for all Ak and, in particular, for A. Because A1 is the empty set, the assertion is true for A1. Suppose it is true for Ak-1. Then we can choose a 2-coloring of G that breaks ^(a) for at least half of the elements of Ak-1. This remains true, even when we change the color of vk. Notice that, for every a G Ak \ Ak-1, ^(a) either maps vk into a white vertex in {v1, v2,..., vk-1} or into a black vertex in {v1, v2,..., vk-1}. Depending on which of the two alternatives occurs more often, we color vk black or white such that this 2-coloring also breaks ^(a) for at least half of the elements of Ak \ Ak-1 and, hence, for at least half of the elements of Ak.	□
If every nontrivial automorphism of a graph G has infinite motion, we say that G has infinite motion. For such graphs the following result from [10] will be of importance.
Lemma 2.4. Let G be an infinite, locally finite, connected graph with infinite motion. If an automorphism ^ G Aut(G) fixes a vertex v0 G V(G) and moves at least one vertex in Sv0 (k), then, for every i > k, it moves at least one vertex in Sv0 (i).
3 Graphs of nonlinear growth
In [10], it was shown that infinite, locally finite, connected graphs with infinite motion and linear growth have countable automorphism group, and therefore distinguishing number either 1 or 2.
If the growth rate of such graphs becomes nonlinear, then the automorphism group can become uncountable. This holds, even if the growth rate becomes only slightly nonlinear.
Theorem 3.1. Let e > 0. Then there exists an infinite, locally finite, connected graph G with uncountable automorphism group, infinite motion, and nonlinear growth function g : No ^ No such that, for sufficiently large n G N0, g(n) is bounded from above by n1+e.
Proof. We construct G from T3, that is, the tree in which every vertex has degree 3. First, choose an arbitrary vertex v0 G V(T3). Our strategy is to replace the edges of T3 by paths such that, for sufficiently large n G N0, g(n) = |BG (n) | < n1+e.
For every i G N0, there are 3 • 2® edges from S^3 (i) to S^3 (i + 1). If we replace them by paths of the same length, then the cardinality of the balls BG (n) grows linearly with slope 3 • 2® from S^3 (i) to S^3 (i + 1).
Observe that, given any affine linear function h : N0 ^ N0, there is a number nh G N such that, for all n > nh, h(n) < n1+e. In particular, we may consider the functions h® : N0 ^ N0 defined by h®(x) = 3 • 2® • x + 1, and choose numbers n® G N such that, for every n > n®, h®(n) < n1+e.
As illustrated in Figure 1, for every i G N0, we replace the edges from ST3 (i) to ST3 (i + 1) by paths of length n®+1. For every i G N and every vertex v G V(G) on such a path from ST3 (i) to ST3 (i + 1), we have dG(v, v0) > n® and, hence,
g(dG(v, v0)) < 3 • 2® • dG(v,v0) + 1 = h®(dG(v,v0)) < dG(v,v0)1+e
J. Cuno et al.: Distinguishing graphs with infinite motion and nonlinear growth	205
Figure 1: Replacing the egdes of T3 by paths.
So, for every n > ni, g(n) is bounded from above by n1+e. Every automorphism of T3 that fixes v0 induces an automorphism of G. It is easy to see that this correspondence is bijective. Thus, Aut(G) is uncountable. Furthermore, G inherits infinite motion from T3. Since Aut(G) is uncountable, the result of [10] mentioned at the beginning of Section 3 implies that G cannot have linear growth.	□
Though we cannot assume that the automorphism groups of our graphs are countable, we prove that infinite, locally finite, connected graphs with infinite motion and nonlinear, but moderate, growth are still 2-distinguishable, that is, they have distinguishing number either 1 or 2.
Our construction of a suitable coloring consists of several steps. In Lemma 3.2 we color a part of the vertices in order to break all automorphisms that move a distinguished vertex v0. In Lemma 3.3 we show how to color some of the remaining vertices in order to break more automorphisms. Iteration of this procedure yields a distinguishing coloring, as shown in Theorem 3.4.
Lemma 3.2. Let G be an infinite, locally finite, connected graph with infinite motion and v0 G V(G). Then, for every k G N, one can 2-color all vertices in Bv0 (k + 3) and Sv0 (Ak + 4), A G N, such that, no matter how one colors the remaining vertices, all automorphisms that move v0 are broken.
Proof. If k = 1, then we color v0 black and all v G V(G) \ {v0} white, whence all automorphisms that move v0 are broken. So, let k > 2. First, we color all vertices in Sv0 (0), Sv0 (1), and Sv0 (k + 2) black and the remaining vertices in Bv0 (k + 3) white. Moreover, we color all vertices in Sv0 (Ak + 4), A G N, black and claim that, no matter how we color the remaining vertices, v0 is the only black vertex that has only black neighbors and only white vertices at distance r G {2,3,..., k + 1}, see Figure 2.
It clearly follows from this claim that this coloring breaks every automorphism that moves v0. It only remains to verify the claim.
Consider a vertex v G V(G) \ {v0}. If v is not in Sv0 (1), then it is easy to see that v cannot have the aforementioned properties. So, let v be in Sv0 (1) and assume it has only
206
Ars Math. Contemp. 7 (2014) 201-213
vo ♦
Sv„ (1) Sv„ (0)
Sv„ (k + 4) Sv„ (k + 2)	Sv„ (2k + 4)
Figure 2: Breaking all automorphisms that move v0.
black neighbors and only white vertices at distance 2. Then it cannot be neighbor to any vertex in Sv„ (2), but must be neighbor to all vertices in Bv„ (1) except itself. Therefore, the transposition of the vertices v and v0 is a nontrivial automorphism of G with finite support. Since G has infinite motion, this is not possible.	□
Lemma 3.3. Let G be an infinite, locally finite, connected graph with infinite motion and v0 G V(G). Moreover, let e > 0. Then there exists a k G N such that, for every m G N and for every n G N that is sufficiently large and fulfills
|Sv„ (n)| <
(1 + e)log2 n
(3.1)
one can 2-color all vertices in Sv„ (m + 1),Sv„ (m + 2),... ,Sv„ (n), but not those in Sv„ (Ak + 4), A G N, such that all automorphisms that fix v0 and act nontrivially on Bv„ (m) are broken.
The coloring and the meaning of the variables m, n, and k is illustrated by Figure 3. Proof. First, choose a k G N that is larger than 1 + 1. Then
k - 1 1
>
k 1 + e Let m G N. By (3.2), there is an n0 G N such that
k - 1 1
V n > n0 : (n — m) •- > n •--+ 1.
k	1 + e
(3.2)
(3.3)
Let n G N be sufficiently large, that is, n > n0, and assume it fulfills (3.1). Then, the number of spheres Sv„ (m+1), Sv„ (m+2),..., Sv„ (n) that are not of the type Sv„ (Ak+4), A g N, is at least
(n — m)
k1
>
1
1+e
+1
>
1+e
(3.4)
n
n
n
J. Cuno et al.: Distinguishing graphs with infinite motion and nonlinear growth
207
Svo (m)	Sv0 (n)
Figure 3: Breaking all automorphisms that fix v0 and act nontrivially on Bv0 (m).
Our goal is to 2-color the vertices in these spheres in order to break all automorphisms that fix v0 and act nontrivially on Bv0 (m).
Let Aut(G, v0) be the group of all automorphisms that fix v0. Every ^ G Aut(G, v0) induces a permutation (n) of the vertices in Bv0 (n). These permutations form a group A. If a and t are different elements of A, then ctt-1 G A acts nontrivially on Bv0 (n). By Lemma 2.4, it also does so on Sv0 (n), which means that a and t do not agree on Sv0 (n). Therefore, the cardinality of A is at most |SV0 (n) |!, for which the following rough estimate suffices for our purposes:
|Sv0(n)|! < |Sv0(n)||Sv0(n)|-1 < ()	-1
n	/	n	N	(3.5)
< n(i+E)1og2 n-1 = 2l(1+fen-1) log2 n < 2T+T-1 .
It is clear that, if an element a G A that acts nontrivially on Bv0 (m) is broken by a suitable 2-coloring of some spheres in Bv0 (n), then all ^ G Aut(G, v0) with (n) = a are broken at once. So it suffices to break all a G A that act nontrivially on Bv0 (m) by a suitable 2-coloring of some spheres in Bv0 (n) in order to ensure that all ^ G Aut(G, v0) that act nontrivially on Bv0 (m) are broken.
Before doing this, let us remark that any element a G A that acts nontrivially on the ball Bv0 (m), also acts nontrivially on every sphere Sv0 (m + 1),..., Sv0 (n). This is a consequence of Lemma 2.4, and implies that we can break a by breaking the action of a on any one of the spheres Sv0 (m + 1),..., Sv0 (n).
Now, consider the subset S C A of all elements that act nontrivially on Bv0 (m). As already remarked, every a G S acts nontrivially on every sphere Sv0 (m + 1),..., Sv0 (n). Hence, we can apply Lemma 2.3 to break at least half of the elements of S by a suitable coloring of Sv0 (m +1). What remains unbroken is a subset S' C S of cardinality at most |S|/2. Now, we proceed to the next sphere. We can break at least half of the elements of S' by a suitable coloring of Sv0 (m + 2). What still remains unbroken, is a subset S" C S
208
Ars Math. Contemp. 7 (2014) 201-213
of cardinality at most |S |/4.
Iterating the procedure, but avoiding spheres of the type SVo (Ak + 4), A g N, we end up with the empty subset 0 C S after at most log2 |S| + 1 < log2 | A| + 1 < steps, see (3.5). This is less than the number of spheres not of the type SVo (Ak + 4), A g N, between SVo (m + 1) and SVo (n), see (3.4). Thus, we remain within the ball BVo (n). Hence, all s G S and, therefore, all ^ g Aut(G, v0) that act nontrivially on BVo (m) are broken, and we are done.	□
Theorem 3.4. Let G be an infinite, locally finite, connected graph with infinite motion and v0 G V(G). Moreover, let e > 0. If there exist infinitely many n G N such that
n
|Svo (n)|<-—^-,	(3.6)
(1 + e)log2 n
then the distinguishing number D(G) of G is either 1 or 2.
Proof. Consider the k G N provided by Lemma 3.3. First, we use Lemma 3.2 to 2-color all vertices in Bv0 (k + 3) and in Sv0 (Ak + 4), A G N, such that, no matter how we color the remaining vertices, all automorphisms that move v0 are broken.
Let m1 = k + 3. Among all n G N that satisfy (3.6) we choose a number n G N that is larger than m1 and sufficiently large to apply Lemma 3.3. Hence, we can 2-color all vertices in Sv0 (m1 + 1), Sv0 (m1 + 2),..., Sv0 (n1), except those in Sv0 (Ak + 4), A G N, such that all automorphisms that fix v0 and act nontrivially on Bv0 (m1) are broken. Next, let m2 = n1 and choose an n2 G N to apply Lemma 3.3 again. Iteration of this procedure yields a 2-coloring of G.
If an automorphism ^ G Aut(G) \ {id} moves v0, then it is broken by our coloring. If it fixes v0, consider a vertex v with ^(v) = v. Since G is connected and m1 < m2 < m3 < ..., there is an i G N such that v is contained in Bv0 (m;). Hence, ^ acts nontrivially on Bv0 (m;) and is again broken by our coloring.	□
Corollary 3.5. Let G be an infinite, locally finite, connected graph with infinite motion and
v0 G V(G). Moreover, let e > 0. If there exist infinitely many n G N such that
2
n2
|Bv0 (n)|< ——-,	(3.7)
(2 + e) log2 n
then the distinguishing number D(G) of G is either 1 or 2. In particular, the Infinite Motion Conjecture holds for all graphs of growth o(n2/ log2 n).
Proof. Let n1 < n2 < n3 < ... be an infinite sequence of numbers that fulfill (3.7). Notice that, for every k G N,
"k . 2 "k g (T+ipg-i > 52TÄ s 1*0<"k>l > E|S-«I ■ C3«
Since
(1 + 2)log2 J (2 + e)log2 nj ^,	(3.9)
J. Cuno et al.: Distinguishing graphs with infinite motion and nonlinear growth	209
we infer that
nk / ■ \ tlim E (	—^ -|Svo (i)M = ~ ,	(3.10)
V (1+ 2 )log2 i J
and that, for infinitely many i e N,
|Svo (i)| < 71—-: .	(3.11)
(1 + 2 ) log2 i
Hence, we can apply Theorem 3.4 to show that the distinguishing number D(G) of G is either 1 or 2.	□
A result similar to Theorem 3.4 can also be obtained for graphs with countably many ends1, none of which grows too fast. Readers not familiar with the notion of ends may safely skip the rest of this section, as the result is not used elsewhere in the paper.
Theorem 3.6. Let G be an infinite, locally finite, connected graph with countably many ends and infinite motion. Moreover, let v0 e V(G) and e > 0. For an end w of G let S-o (n) be the set of vertices in SVo (n) that lie in the same connected component of G \ BVo (n — 1) as w. If, for every end w, there are infinitely many n e N such that
i	i	n
S (n)i <7-r-,	(3.12)
1 Vo () < (1+ e) log2 n'	V 7
then the distinguishing number D(G) of G is either 1 or 2.
Proof. Basically the proof consists of three steps. First we color part of the vertex set in order to break all automorphisms that move v0. In the second step we break all automorphisms in Aut(G, v0) that do not fix all ends of the graph by coloring some other vertices. Finally, we color the remaining vertices to break the rest of the automorphisms.
In order to break all automorphisms that move v0 we apply Lemma 3.2, just as in the proof of Theorem 3.4. The only difference is that we choose k twice as large as proposed by Lemma 3.3, because we would like to color some additional spheres in the second step of the proof before applying an argument similar to that in Lemma 3.3.
For the second step consider the spheres SVo (k + 4), A e N. We wish to color those spheres such that every automorphism that fixes v0 and preserves the coloring also fixes every end of G.
It is not hard to see that the sets S"0 (k+4), w an end of G, A e N, carry the following tree structure. Consider v0, the root, which is connected by an edge to S"0 (3k + 4) for each end w. For every end w of G and every A e N, draw an edge from S"0 (k + 4) to S- (k + 4). To see that this is indeed a tree just notice that if S^1 (n) = S^2 (n), then, for every m < n, SV-1 (m) = S"02 (m). So there cannot be any circles. By construction, this tree structure is infinite, locally finite, and does not have any endpoints.
Next, notice that every automorphism ^ e Aut(G, v0) that does not fix all ends also acts as an automorphism on this tree structure. By [16], the distinguishing number of infinite, locally finite trees without endpoints is at most 2. Therefore it is possible to 2-color the sets S-o (k + 4), w an end of G, A e N, such that every such automorphism
1 Ends were first introduced by Freudenthal [4] in a topological setting, but here the definition of Halin [5] is more appropriate. For an accessible introduction to ends of infinite graphs see [2].
210
Ars Math. Contemp. 7 (2014) 201-213
is broken. It is also worth noting that so far we did not use the countability of the end space of G, nor did we use the growth condition on the ends.
Let us turn to the third step of the proof. So far we have colored the ball Bv0 (k + 3) and the spheres SVo (|k + 4), A > 2, in a way that color preserving automorphisms fix v0 and move every S"0 (n) into itself. Consider such an automorphism which acts nontrivially on G. If we remove the fixed points of ^ from G, then the infinite motion of G implies that the resulting graph has only infinite components. Hence, there is a ray in G which contains no fixed point of The image of this ray must lie in the same end w. Thus, there is an index n0, such that, for every n > n0, ^ acts nontrivially on S"o (n).
Let (wj)ieN be an enumeration of the ends of G. Choose a function f: N ^ N such that, for every i e N, f -1(i) is infinite. Assume that all spheres up to Sv0 (m) have been colored in the first i - 1 steps. In the i-th step we would like to color some more spheres in order to continue breaking all automorphisms in Aut(G, v0) that act nontrivially on each of the spheres S"/(i) (n), n > m. This can be done by exactly the same argument as the one used in the proof of Lemma 3.3.
As we already mentioned, every automorphism that was not broken in the first two steps acts by nontrivially on the rays of some end. Since, in the procedure described above, every end is considered infinitely often, it is clear that every such automorphism will eventually be broken. This completes the proof.	□
4 Graphs with higher cardinality
If a graph G has trivial automorphism group, then G is obviously 1-distinguishable, that is, D(G) = 1. From now on we assume that our graphs G have nontrivial automorphism group. In this case, the motion m(G) of G is defined as
m(G) = min m(^).	(4.1)
0eAut(G)\{id}
As already mentioned, the Infinite Motion Conjecture does not hold for graphs of higher cardinality. An example is the Cartesian product G = Kn □ Km of two complete graphs on infinitely many vertices n and m with 2n < m. By [9], G has motion n, but D(G) > n.
The question arises whether one can adapt the Infinite Motion Conjecture to graphs of higher cardinality. The starting point is [12, Theorem 1]. It asserts that a finite graph G is 2-distinguishable if m(G) > 2log2 |Aut(G)|. However, a second look at the proof shows that the inequality sign can be replaced by >. For details see Section 5. For finite graphs we thus infer that
m(G) > 2log2 |Aut(G)| implies D(G) = 2,	(4.2)
which can also be written in the form
m(G)
|Aut(G)| < 2 — implies D(G) = 2 .
Notice that 2m(G = 2m(G) if m(G) is infinite. We are thus tempted to conjecture for graphs G with infinite motion that |Aut(G)| < 2m(G) implies D(G) = 2. We formulate this conjecture as the
Motion Conjecture. Let G be a connected graph with infinite motion m(G) and |Aut(G)| < 2m(G). Then D(G) = 2.
J. Cuno et al.: Distinguishing graphs with infinite motion and nonlinear growth	211
How does this compare with the Infinite Motion Conjecture? It asserts that the distinguishing number of a locally finite, connected graph G is 2 if m(G) is infinite. Since locally finite graphs are countable, the condition that m(G) is infinite is equivalent to m(G) = K0. Furthermore, for countable graphs we have
|Aut(G)| < kQ0 = 2Qo .
Hence, for countable graphs, and thus also for locally finite, connected graphs with infinite motion, the inequality of the Motion Conjecture is automatically satisfied, which means that the Infinite Motion Conjecture is a special case of the Motion Conjecture.
Now, let us focus on the two results from [10] that imply the validity of the Infinite Motion Conjecture for graphs with countable group.
Theorem 4.1. Let G be a locally finite, connected graph that satisfies K0 < |Aut(G)| < 2Qo. Then |Aut(G)| = Ko, m(G) = Ko, and D(G) = 2.
Notice that the only thing that is required here, besides local finiteness and connectedness, is an upper and a lower bound on the size of Aut(G). And it turns out, that Aut(G) is countable, even without the continuum hypothesis. Even infinite motion and D(G) = 2 are consequences of this restriction on the size of the automorphism group.
Theorem 4.2. Let G be a countably infinite, connected graph that satisfies the conditions |Aut(G)| < m(G) and m(G) = K0. Then D(G) = 2.
Here, without local finiteness, one cannot drop the assumption of infinite motion. If we assume that Aut(G) has smaller cardinality than the continuum, then we can ensure 2-distinguishability if the continuum hypothesis holds, but we do not know whether this is really necessary.
Corollary 4.3. Let G be a countably infinite, connected graph with infinite motion. If the continuum hypothesis holds, and if |Aut(G)| < 2m(G), then D(G) = 2.
The next theorem shows that Theorem 4.2 also holds for graphs of higher cardinality and uncountable motion.
Theorem 4.4. Let G be a connected graph with uncountable motion. Then |Aut(G)| < m(G) implies D(G) = 2.
Proof. Set n = | Aut(G) |, and let Z be the smallest ordinal number whose underlying set has cardinality n. Furthermore, choose a well ordering - of A = Aut(G) \ {id} of order type Z, and let a0 be the smallest element with respect to -. Then the cardinality of the set of all elements of A between a0 and any other a e A is smaller than n < m(G).
Now we color all vertices of G white and use transfinite induction to break all automorphisms by coloring selected vertices black.
Induction base By the assumptions of the theorem, there exists a vertex v0 that is not fixed by a0. We color it black. This coloring breaks a0.
INDUCTION STEP Let fi e A. Suppose we have already broken all a - fi by pairs of distinct vertices (va, a(va)), where va is black and a(va) white. Clearly, the cardinality of the set R of all (va, a(va)), a - fi, is less than m(G) > n. By assumption, fi moves at least m(G) vertices. Since there are still n vertices not in R, there must be a pair of vertices (v^, fi(v^)) that does not meet R. We color v^ black. This coloring breaks fi.	□
212
Ars Math. Contemp. 7 (2014) 201-213
Corollary 4.5. Let G be a connected graph with uncountable motion. If the general continuum hypothesis holds, and if |Aut(G)| < 2m(G), then D(G) = 2.
Proof. Under the assumption of the general continuum hypothesis 2m(G) is the successor of m(G). Hence | Aut(G) | < m(G), and the assertion of the corollary follows from Theorem 4.4.	□
5 The Motion Lemma of Russell and Sundaram
In order to show that a finite graph G is 2-distinguishable if m(G) > 2log2 |Aut(G)|, Russell and Sundaram [12] first defined the cycle norm of an automorphism If
^ = (V11V12 . . .Vii! )(v21 . . . V2l2 ) . .. (vfc1 . . . vklk ) ,
then the cycle norm c(^) of ^ is
k
c(^) = E(1i - !).
i=1
The cycle norm c(^) is related to graph distinguishability as follows: Let G be randomly 2-colored by independently assigning each vertex a color uniformly from {black, white}. Then the probability that every cycle of ^ is monochromatic is 2- c(^. In this case, ^ preserves the coloring so chosen.
Further, they define the cycle norm c(G) of a graph G as
c(G) = min c(^).
0eAut(G)\{id}
We now reprove Theorem 2 of [12] with > instead of >. Because c(^) > m(^)/2 and thus c(G) > m(G)/2 we infer from Theorem 5.1 below that G is 2-distinguishable if m(G) > 2log2 |Aut(G)|. We propose to call this result "Motion Lemma of Russell and Sundaram". Actually, the only difference from the original proof is the insertion of the middle term in (5.2).
Theorem 5.1. Let G be a finite graph, and c(G)log d > log |Aut(G)|. Then G is d-distinguishable, that is, D(G) < d.
Proof. Let x be a random d-coloring of G, the probability distribution being given by selecting the color of each vertex independently and uniformly in the set {1,..., d}. For a fixed automorphism ^ G Aut(G) \ {id} consider the probability that the random coloring X is preserved by
/ 1 \ c(0) / 1 \ c(G)
Prx[Vv : x(^(v)) = x(v)] = ^J < (^J .	(5.1) Collecting these events yields the inequality
Prx[3$ G Aut(G) \ {id} Vv : x(^(v)) = x(v)] < (|Aut(G)| - 1) (d)c(G)
< |Aut(G)| (1 )c(G) .	.
By hypothesis the last term is at most 1. Thus there exists a coloring x such that, for every ^ G Aut(G) \ {id}, there is a v for which x(^(v)) = x(v), as desired.	□
J. Cuno et al.: Distinguishing graphs with infinite motion and nonlinear growth	213
Acknowledgement
We thank the referees for their comments and remarks, as they contributed considerably
to the readability of the paper. Furthermore, we are grateful to Norbert Sauer and Claude
Laflamme for their suggestions pertaining to Theorem 4.4 and Corollary 4.5.
References
[1]	M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), R18.
[2]	R. Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2006.
[3]	D. M. Evans. A note on the automorphism groups of countably infinite structures, Arch. Math. (Basel) 49 (1987), 479-483.
[4]	H. Freudenthal, Uber die Enden diskreter Raume und Gruppen, Comment. Math. Helv. 17 (1945), 1-38.
[5]	R. Halin, Uber unendliche Wege in Graphen, Math. Annalen 157 (1964), 125-137.
[6]	R. Halin, Automorphisms and endomorphisms of infinite locally finite graphs, Abh. Math. Sem. Univ. Hamburg 39 (1973), 251-283.
[7]	R. Hammack, W. Imrich and S. KlavZar, Handbook of product graphs, second ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011.
[8]	W. Imrich, J. Jerebic and S. KlavZar, The distinguishing number of Cartesian products of complete graphs, European J. Combin. 29 (2008), 922-929.
[9]	W. Imrich, S. KlavZar and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin. 14 (2007), R36.
[10]	W. Imrich, S. M. Smith, T. Tucker and M. E. Watkins, Infinite motion and the distinguishing number of graphs, in preparation.
[11]	C. Laflamme, L. Nguyen Van The and N. W. Sauer, Distinguishing number of countable homogeneous relational structures, Electron. J. Combin. 17 (2010), R20.
[12]	A. Russell and R. Sundaram, A note on the asymptotics and computational complexity of graph distinguishability, Electron. J. Combin. 5 (1998), R23.
[13]	S. M. Smith, T. Tucker and M. E. Watkins, Distinguishability of infinite groups and graphs, Electron. J. Combin. 19 (2012), P27.
[14]	V. I. Trofimov, Groups of automorphisms of graphs as topological groups, Russian, Mat. Zametki 38 (1985), 378-385.
[15]	T. Tucker, Distinguishing maps, Electron. J. Combin. 18 (2011), P50.
[16]	M. E. Watkins and X. Zhou, Distinguishability of locally finite trees, Electron. J. Combin. 14 (2007), R29.