¿^creative , ars mathematica ^commons contemporánea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 13 (2017) 15-21 The distinguishing index of the Cartesian product of countable graphs Izak Broere * Department of Mathematics and Applied Mathematics, University of Pretoria Monika Pilsniak t AGH University, Department of Discrete Mathematics, Krakow, Poland Received 6 January 2015, accepted 12 July 2016, published online 11 August 2016, corrected 12 January 2017 Abstract The distinguishing index D'(G) of a graph G is the least cardinal d such that G has an edge colouring with d colours that is preserved only by the trivial automorphism. We derive some bounds for this parameter for infinite graphs. In particular, we investigate the distinguishing index of the Cartesian product of countable graphs. Finally, we prove that D'(k2^° ) = 2, where K2N° is the infinite dimensional hypercube. Keywords: Distinguishing index, automorphism, infinite graph, edge colouring, infinite dimensional hypercube. Math. Subj. Class.: 05C25, 05C80, 03E10 1 Introduction Albertson and Collins [1] introduced the (vertex-)distinguishing number D(G) of a graph G as the least cardinal d such that G has a labelling 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 [12], [13], and [14]. For graphs of higher cardinality, see [8]. The corresponding notion for endomorphisms instead of automorphisms is investigated in [5]. Let us consider now any edge colouring of a graph G; it is merely a function f : E(G) ^ C which labels each edge of G with a colour from some set C. Given a graph *This author is thankful to the AGH University of Science and Technology whose hospitality he enjoyed during the preparation of this paper; he is also supported in part by the National Research Foundation of South Africa (Grant Numbers 90841, 91128). tThe research was partially supported by the Polish Ministry of Science and Higher Education. E-mail addresses: izak.broere@up.ac.za (Izak Broere), pilsniak@agh.edu.pl (Monika Pilsniak) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 15 Ars Math. Contemp. 13 (2017) 125-136 G with an edge colouring f, we say that a graph automorphism < : V(G) ^ V(G) of G preserves the edge colouring f if f (xy) = f (<(x)<(y)) for every edge xy e E(G); if, on the other hand, there is an edge xy such that f (xy) = f (<(x)<(y)), then we say that < is broken by xy. It is easy to see that there is, for every connected graph G = K2, an edge colouring of G which is preserved only by the trivial automorphism of G, i.e., only by the identity idG : V(G) ^ V(G): Merely choose different colours for different edges. The distinguishing index D'(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 K2 the distinguishing index is not defined and it is the only such connected graph. For finite graphs this concept is investigated by Kalinowski and Pilsniak in [9] and by Pilsniak in [11]. In [2], the following general upper bound was proved. Theorem 1.1. Let G be a connected, infinite graph such that the degree of every vertex of G is not greater than A. Then D'(G) < A. A graph G is said to be prime with respect to the Cartesian product if whenever G = G1mG2, then either Gi or G2 is the graph consisting of a single vertex. It is well known (see [6]) that if G is connected, then G has a unique prime factorization, i.e., G = G1DG2D ■■■ OGt such that for 1 < i < t, Gi is prime. Two graphs G and H are called relatively prime if K1 is the only common factor of G and H. About forty-five years ago Imrich and Miller independently proved the following theorem - see Thm. 6.10 in [6]. Theorem 1.2. If G is connected and G = G1DG2D ■ ■ ■ OGr is its prime decomposition, then every automorphism of G is generated by the automorphisms of the factors and the transpositions of isomorphic factors. A basic fact, which is a reformulation of the above theorem for r = 2 and which is used frequently in this paper, is: If < is an automorphism of the Cartesian product G1mG2 of two connected relatively prime graphs, then there are automorphisms 2. Then D'(Gk) = 2 with the only exception: D'(Kf) = 3. 2 The distinguishing index of the Cartesian product First we consider the Cartesian product of two denumerable graphs with infinite edge sets. Lemma 2.1. Let Gi and G2 be two connected relatively prime denumerable graphs. Then D'(GiDG2) < 2. Proof. We start by labelling the edges of Gi with ei, e2,... and those of G2 with fi, f2,... This is possible since both edge sets have to be denumerable. Note that these labellings effectively order the edges of these graphs. We can now easily describe the required edge distinguishing colouring in colours 1 and 2: Colour the first (in terms of the above ordering) k edges of the k'th layer of Gi and the first k edges of the k'th layer of G2 with 1; colour all other edges with 2. Recall that every edge in GiDG2 lies in a Gi-layer or a G2-layer; hence this process colours indeed all edges of GinG2. Using the labels, this means that the edges corresponding to the edges {ei, e2,..., ek} of Gi in the k'th Gi-layer and the edges corresponding to the edges {fi, f2,..., fk} of G2 in the k'th G2-layer, for all k = 1, 2,..., are coloured 1 and all other edges are coloured 2. Now consider, if possible, any non-trivial automorphism ^ = (^i,^2) of GiDG2 which preserves the above edge colouring of Gi mG2. Since every two different Gi-layers have different numbers of edges coloured with 1, the automorphism ^>2 of G2 must be trivial. Similarly, must be trivial. Hence ^ is the trivial automorphism, proving that for every non-trivial automorphism ^ of Gi DG2 there is an edge e of Gi DG2 for which e and y(e) are coloured differently. □ The same result was obtained for the distinguishing number of two connected relatively prime denumerable graphs by Imrich and Klavzar in [7]. Recently it was shown by Estaji, Imrich, Kalinowski, Pilsniak and Tucker in [3] that the condition that the two graphs are relatively prime can be omitted. Note that Lemma 2.1 assures us that D'(GinG2) is at most two irrespective of the values of D'(Gi) and D'(G2). Next we consider the case in which both Gi and G2 of orders being any cardinals and with finite values for the distinguishing index. Lemma 2.2. Suppose Gi and G2 are connected relatively prime graphs with finite distinguishing indexes. If D'(Gj) < k, i = 1,2, then D'(GiDG2) < max{ki,k2}. Proof. Since D'(Gj) < kj, i = 1,2, there are, with k = max{ki, k2}, edge colourings fi of Gi and f2 of G2 using the colours 1,2,..., k which are distinguishing colourings of Gi and G2 respectively. In order to prove now that D'(Gi DG2) < k, we again use the notion of a "first" layer through a labelling of the vertices (which here is not explicitly chosen or named). Hence consider the function f : E(GiDG2) ^ {1, 2,..., k} defined by 1) f ((vi, w)(v2, w)) = fi(viv2) for edges of the first Gi-layer and 18 Ars Math. Contemp. 13 (2017) 125-136 2) f ((v, wi)(v, w2)) = /2(wiw2) for edges of the first G2-layer and 3) f (e) = 1 for all remaining edges. Consider any non-trivial automorphism a = (a1, a2) of G1mG2 with a1 a non-trivial automorphism of G1 or a2 a non-trivial automorphism of G2. Assume that the first is true (for G1): Then, since f1 is a distinguishing colouring of the first G1-layer, there is an edge e of G1 such that f1(e) = f1(a1(e)). Now, if a2 does not move the first layer, then this edge (considered as an edge of G1 mG2) is an edge of the required kind in the first G1-layer. On the other hand, if a2 does move the first layer to another layer, we can remark, since f1(e) = f1(a1(e)), that at least one of f1(e) and f1(a1(e)) is different from 1 so that this edge is moved by a2 to an edge in another layer which has colour 1 by 3) above. A similarly argument holds if the second is true (for G2) - merely interchange the roles of G1 and G2 (and their colourings and automorphisms) in the above argument. Hence we are assured that all non-trivial automorphisms of G1mG2 are broken by the colouring f. □ Observe, that D'(G1DG2) can be arbitrary large, for instance if G1 is isomorphic to and G2 is isomorphic to an infinite ray with many (but finitely many) leaves adjacent to its first vertex. In our next result we prove that if G1 satisfies D'(G1) = H0 and the graph G2 is finite (so that, in particular D'(G2) is finite), then D'(G1DG2) = H0. Lemma 2.3. Suppose G1 and G2 are connected relatively prime graphs with D'(G1) = H0 and G2 is finite. Then D' (G1DG2) = K0. Proof. Suppose, for a proof by contradiction, that D'(G1DG2) is finite. Since G2 is a finite graph, there are finite values for ||G2||, the number of edges of G2, and D'(G2) too. Hence we can choose a positive integer k such that each of these three numbers is at most k. Since D'(G1DG2) < k, there is a k-distinguishing edge colouring f of the edges of G1DG2. Furthermore, since D'(G1) = H0, there exists, for every positive integer t, anon-trivial automorphism at of G1 which needs at least t + 1 colours to break it. So if t > k, the colouring by f of any layer of G1 induces a colouring on G1 which cannot be broken by the automorphism at of G1. Since there are infinitely many such automorphisms, we may assume without loss of generality that as = at when s = t. Now consider non-trivial automorphisms of G1DG2 of the form a = (at, idG2) (for some t > k). For each such t, and each edge vw of G1 (which we can consider as an edge of any G1-layer of G1DG2), we have that f (vw) = f (at(v)at(w)), i.e., these automorphisms of G1nG2 are not broken by edges in layers of G1. The automorphisms a of the above form should therefore be broken by edges of layers of G2. But this means that, for each t > k, for at least one edge xy of the G2-layer determined by a vertex v g V(G1), we have that f (xy) in this layer is different from f (at(x)at(y)) in the G2-layer determined by at(v) g V(G1). Since there are infinitely many G2-layers, this requires infinitely many different colourings of G2. However, there are at most k||G2 ^different colourings of G2-layers. Hence the colouring f cannot break all the infinitely many automorphisms described above. □ As a consequence of the above three lemmas we immediately obtain the following characterisation. I. Broere andM. Pilsniak: The distinguishing index of the Cartesian product. 19 Theorem 2.4. If Gi and G2 are connected relatively prime countable graphs, then D'(GiDG2) is infinite if and only if for some i G {1,2} we have that D'(Gj) is infinite while for j = i we have that Gj is finite. □ Now we consider a graph which is the Cartesian power Gk of a denumerable graph G. For a finite graph G, the distinguishing number of the Cartesian power of G is considered in [4]. Here we prove a result for graphs G with a finite number of prime factors (counted with their multiplicities). We begin with a result for prime graphs. Lemma 2.5. Let k > 2 be an integer. If a connected denumerable graph G is prime with respect to the Cartesian product, then D' (Gk) = 2. Proof. If k = 2, the proof is similar to the proof of Lemma 2.1. Indeed, denote G2 = GiDG2, where Gi, G2 are isomorphic to G. Using an analogous proof technique but colouring distinct even numbers of edges of each Gi -layer with red and distinct odd numbers of edges of each G2 -layer with red will also take care of the additional automorphisms generated by the isomorphism between Gi and G2. Now we show that D'(GDH) = 2 if D'(H) = 2 and G is prime. In particular, if we consider H = Gk-i then we obtain the thesis by induction. Namely, let f be a distinguishing colouring of H with two colours. We define a colouring of GdH as follows: One H-layer is given the colouring f, hence all automorphisms of this H-layer are broken. We colour another H-layer completely blue and all remaining H-layers we colour with distinct numbers of red edges different from the number of red edges in f. Hence all automorphisms of G are broken. If G' isomorphic with G is a factor of H, then we have additional automorphisms, generated by interchanging of G and G'. To break them, we colour each G-layer red. Then every G'-layer contained in a blue H-layer is completely blue, so it cannot be interchanged with G. In this way we break all nontrivial automorphisms of GDH with two colours if D'(H) = 2 and G is prime. □ The above proof is analogous to the proof of a similar result in [7]. Observe that D'(GDH) = 2 if D'(H) = 2 and G is prime, also if G is finite. Theorem 2.6. Let k > 2 be an integer and G be a connected denumerable graph with the prime factor decomposition G = GiD...DGr, where Gi,..., Gr are not necessarily distinct. Then D'(Gk) = 2. Proof. If G is prime, the claim follows from Lemma 2.5. If G is not prime, we consider the prime factorization G = GiD...DGr and apply Lemma 2.5 to every infinite factor (G has at least one infinite prime factor). Moreover, we can use Theorem 1.4 for every finite factor. The result then follows from Lemma 2.2 unless G = K2DH and k = 2, where H is an infinite graph relatively prime with K2. But we already know that D'(H2) = 2 due to the above arguments, so let f be a distinguishing colouring of H2 with two colours. We then define a colouring of G2 in terms of its four H2-layers as follows: One H2-layer is given the colouring f, hence all automorphisms of this H2-layer are broken. The three remaining H2-layers are coloured with distinct numbers of red edges (while all remaining edges are blue), hence all automorphisms of G2 are broken. □ We say the G has infinite diameter if there are vertices of arbitrarily large distance. Such a situation occurs in particular in any weak Cartesian product G of infinitely many non-trivial factors (finite or infinite). Hence the above theorem immediately implies the following. 20 Ars Math. Contemp. 13 (2017) 125-136 Corollary 2.7. Let k > 2 be an integer and let G be a connected denumerable graph with finite diameter. Then D'(Gfc) = 2. 3 The distinguishing index of the infinite hypercube The situation is quite different when we have infinitely many factors in the Cartesian power - consider for example the infinite dimensional hypercube K2 0. This (uncountable) graph has vertices represented by (denumerable) sequences of 0's and 1's and two vertices are adjacent whenever their binary sequences differ in exactly one entry. This graph also has uncountably many connected components, each a countable graph, which are pairwise isomorphic. The automorphism group of K2 0 is well described (see [10]). Using this information, we are now ready to prove Theorem 3.1. Let K2 0 be the infinite dimensional hypercube. Then D'(K2 0) = 2. Proof. We first construct an asymmetric spanning tree and then show how it can be used to prove the existence of an asymmetric spanning subgraph in every component of K2 0; these subgraphs will be constructed in such a way that different components have non-isomorphic subgraphs. Towards the end of the proof, we shall show how they can be exploited to break all non-trivial automorphisms of the hypercube K2 0. It is convenient to describe the required asymmetric subgraphs by first handling the connected component C0 in which all sequences have only finitely many 1's (and therefore an infinite tail of 0's). First we build an asymmetric tree T, which is a spanning subgraph of C0, as follows: Take (0,0,0,0,...) and let it be the central vertex. Then add (1,0,0,0,...), and the edge between it and the central vertex, to form the first branch of the tree. Next take (0,1,0,0,0,...) and (1,1,0,0,0,...) and the path between them and the central vertex to form the second branch of the tree. The i'th branch of this tree will therefore be the path on the central vertex and (0i-1,1,0,0,0,...), (0i-2,1,1,0,0,0,...),... and will have length 2i-1. All these binary sequences have 1 on the i'th entry and if we restricted them to the first i - 1 entries, then we obtain the binary-reflected Gray code list with i - 1 bits. It can be generated recursively from the list for i - 2 bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with 0, and then prefixing the entries in the reflected list with 1. In particular, the last vertex of the i'th branch has the code (1,0i-2,1,0,0,0,...), and the last but one has the code (1,0i-3,1,1,0,0,0,...). Note that all branches of T are of different length, which ensures us that T is asymmetric, and note that it is a spanning tree of the component C0. So it means that we can easily distinguish the weak Cartesian product of H0 copies of K2 by two colors: Namely we colour all the edges of T with one colour and the remaining edges with the second colour. Now we would like to distinguish the Cartesian product of K0 copies of K2 by two colours. Consider any sequence x = (x1, x2,...) of 0's and 1's and suppose it is in the connected component C of the hypercube K2 0. Since C is isomorphic to C0, we can find a copy of T, say TC, in C. Now we use x and TC to create a spanning subgraph of C by adding edges to TC as follows: For every positive integer i we add the edge of K2 0 between the endvertex of the i'th branch and the last but one vertex of the (i + 1)'th branch of TC to this tree if and only if I. Broere andM. Pilsniak: The distinguishing index of the Cartesian product. 21 xi = 1. We remark that this edge is indeed in K^'0 since the binary sequences representing these vertices in C0 differ in exactly one entry, namely the (i + 1)'th entry, and therefore the same is true in the isomorphic copy TC of T. Note also that the choice of the added edges ensures us that Tx is not isomorphic to Tx> whenever x = x'. Since there are uncountably many sequences x, we thus have uncountably many pairwise non-isomorphic subgraphs all of which are asymmetric. Finally we prove, using these subgraphs of the components of K0, that the infinite hypercube is 2-distinguishable. Consider the following colouring f of the edges of K^0: Colour, for each component C of K^0 and some fixed choice of a vertex x of C, all the edges of the spanning subgraph TX with 1; colour all the other edges of K^0 with 2. Then consider any automorphism a of K^0. Since isomorphisms, and thus a, preserve connectivity, a has to take every component C of K0 to a component C' of K^00. But, if C = C', then the asymmetric spanning subgraphs T£ and T% of C and C' are not isomorphic (because x = x'), hence the colouring f breaks a. □ References [1] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), R18. [2] I. Broere and M. Pilsniak, The distinguishing index of some infinite graphs, Electron. J. Combin. 23(1) (2015), P1.78. [3] E. Estaji, W. Imrich, R. Kalinowski, M. Pilsniak and T. Tucker, Distinguishing number for the Cartesian product of countable graphs, Discuss. Mathem. Graph Th., http://dx.doi. org/10.7151/dmgt.1902. [4] A. Gorzkowska, R. Kalinowski and M. Pilsniak, Distinguishing the Cartesian product of finite graphs, Ars Math. Contemp. 12 (2017), 77-87. [5] W. Imrich, R. Kalinowski, F. Lehner and M. Pilsniak, Endomorphism breaking in graphs, Electron. J. Combin. 21(1) (2014), P1.16. [6] W. Imrich and S. KlavZar, Product Graphs, John Wiley & Sons, Inc. New York, 2000. [7] W. Imrich and S. KlavZar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006), 250-260. [8] W. Imrich, S. KlavZar and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin. 14 (2007), R36. [9] R. Kalinowski and M. Pilsniak, Distinguishing graphs by edge-colourings, Europ. J. Combin. 45 (2015). [10] M. Pankov, A note on automorphisms of the infinite-dimensional hypercube graph, The Electron. J. Comb. 19(4) (2012), P23. [11] M. Pilsniak, Edge Motion and the Distinguishing Index, Preprint MD 076, http://www. ii.uj.edu.pl/preMD. [12] S. M. Smith, T. Tucker and M. E. Watkins, Distinguishability of infinite groups and graphs, Electron. J. Combin. 19 (2012), P27. [13] T. Tucker, Distinguishing maps, Electron. J. Combin. 18 (2011), R50. [14] M. E. Watkins and X. Zhou, Distinguishability of locally finite trees, Electron. J. Combin. 14 (2007), R29.