ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 77-87
The distinguishing index of the Cartesian product of finite graphs*
Aleksandra Gorzkowska, Rafal Kalinowski, Monika Pilsniak
Department of Discrete Mathematics, AGH University, Krakow, Poland Received 4 August 2015, accepted 2 March 2016, published online 20 May 2016
The distinguishing index D' (G) of a graph G is the least natural number d such that G has an edge colouring with d colours that is only preserved by the identity automorphism. In this paper we investigate the distinguishing index of the Cartesian product of connected finite graphs. We prove that for every k > 2, the k-th Cartesian power of a connected graph G has distinguishing index equal 2, with the only exception D'(K|) = 3. We also prove that if G and H are connected graphs that satisfy the relation 2 < |G| < |H| < 2|g| (2"gII - 1) - |G| + 2, then D'(GdH) < 2 unless GUH = K22.
Keywords: Edge colouring, symmetry breaking, distinguishing index, Cartesian product of graphs. Math. Subj. Class.: 05C15, 05E18
1 Introduction
We use standard graph theory notation (cf. [6]). In particular, Aut(G) denotes the automorphism group of a graph G.
An edge colouring breaks an automorphism p e Aut(G) if p does not preserve the colouring, i.e., there exists an edge of G that is mapped by p to an edge of different colour. The distinguishing index D'(G) of a graph G is the least natural number d such that G has an edge colouring with d colours that breaks all non-trivial automorphisms of G. Such a d-colouring is called distinguishing. This notion was introduced by Kalinowski and Pilsniak [10] as an analogue of the well-known distinguishing number D(G) of a graph G defined by Albertson and Collins [1] as the least number of colours in a vertex colouring that breaks all non-trivial automorphisms of G.1 As the distinguishing index is not defined for K2, we assume henceforth that K2 is not a connected component of any graph considered.
*The research was partially supported by the Polish Ministry of Science and Higher Education.
E-mail addresses: agorzkow@agh.edu.pl (Aleksandra Gorzkowska), kalinows@agh.edu.pl (Rafal Kalinowski), pilsniak@agh.edu.pl (Monika Pilsniak)
1 Fisher and Isaak [5] considered distinguishing edge colourings of complete bipartite graphs, but did not introduce any special notation or terminology.
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
70
Ars Math. Contemp. 12 (2017) 111-126
The distinguishing index of several examples of graphs was exhibited in [10]. For instance, D'(Pn) = D(Pn) = 2, for n > 3; D'(Cn) = D(Cn) = 2, for n > 6, and D'(Cn) = 3, for n = 3,4,5. There exist graphs G for which D'(G) < D(G), for instance D'(Kn) = D'(Kp,p) = 2, for any n > 6 and p > 4, while D(Kn) = n and D(Kpp) = p+1. It is also possible that D'(G) > D(G). All trees satisfying this inequality were characterized in [10]. The following general upper bound of the distinguishing index was proved in [10].
Theorem 1.1. [10] If G is a finite connected graph of order n > 3, then D'(G) < D(G) + 1. Moreover, if A is the maximum degree of G, then D' (G) < A unless G is a C3, C4 or C5.
The distinguishing index was also investigated for infinite graphs [2] and their Cartesian product [3].
The Cartesian product of graphs G and H is a graph, denoted GUH, whose vertex set is V(G) x V(H). Two vertices (g, h) and (g', h') are adjacent if either g = g' and hh' G E(H), or gg' G E(G) and h = h'. Denote GdG by G2, and recursively define the k-th Cartesian power of G as Gk = GUGk-1.
A non-trivial graph G is called prime if G = G1UG2 implies that either G1 or G2 is K1. It is easy to see that every non-trivial finite graph has a prime factorization with respect to the Cartesian product. For connected graphs it is also unique up to isomorphisms and the order of the factors, as has been shown by Sabidussi and Vizing (cf. [6]). Two graphs G and H are called relatively prime if K1 is the only common factor of G and H.
Let v be a vertex of H. A Gv-layer (called also a horizontal layer of GUH) is the subgraph induced by the vertex set {(u, v) : u G V(G)}. An Hu-layer, or vertical layer, is defined analogously for a vertex u of G. Clearly, each horizontal layer is isomorphic to G and each vertical one is isomorphic to H. Therefore, speaking of a specified layer of GUH, we shall usually use only one coordinate of a vertex. The same refers to edges.
We shall need knowledge of the structure of the automorphism group of the Cartesian product, which was determined by Imrich [7], and independently by Miller [11].
Theorem 1.2. [7, 11] Suppose ^ is an automorphism of a connected graph G with prime factor decomposition G = G1UG2U ... UGr. Then there is a permutation n of the set {1, 2,... ,r} and there are isomorphisms fa: Gn(i) ^ Gi, i = 1,... ,r, such that
^(X1,X2, ...,Xr ) = (fa (Xn(1)),fa(Xn(2)), . . .,fa (Xn(r))).
It follows in particular that every automorphism of the Cartesian product of two relatively prime graphs is a composition of a permutation of vertical layers generated by an automorphism of G and a permutation of horizontal layers generated by an automorphism of H. For additional results about the Cartesian product consult [6].
Our main results are extensions of theorems about the distinguishing number of Cartesian powers and of Cartesian products of connected graphs to the distinguishing index. The results (and some of the proofs) are inspired by a paper [8] by Imrich, Jerebic and Klavzar. In Section 2 we generalize a result of Imrich and Klavzar.
Theorem 1.3. [9] Let G be a connected graph and k > 2. Then D(Gk) =2 except for the graphs K2,K3, K whose distinguishing number is three.
The second result that we extend is also due to Imrich and Klavzar:
A. Gorzkowska et al.: The distinguishing index of the Cartesian product of finite graphs
79
Theorem 1.4. [9] Let G and H be connected, relatively prime graphs such that
|G| < |H| < 2|g| — |G| + 1.
Then D(GaH) < 2.
In Section 3 we prove an analogous result (Theorem 3.4) for the distinguishing index of the Cartesian product of connected graphs, not necessarily relatively prime (let us note that, using our method of proof, Theorem 3.4 was already strengthened in [4] by omitting the assumption that G and H are relatively prime). We also obtain a slightly stronger result for trees (Theorem 3.1).
In proofs, we usually use colours 1,..., d. If d = 2, then we also use colours 0 and 1, or alternatively red and blue.
2 Distinguishing Cartesian powers
Let us start with the Cartesian powers of K2. Recall that the k-dimensional hypercube is isomorphic to Kk and denoted by Qk. As mentioned earlier, the distinguished index is not defined for K2 = Q1. Clearly, D'(Q2) = 3 since Q2 = C4. The following result was proved in [13].
Theorem 2.1. [13] If a graph G of order at least 7 contains a Hamiltonian path, then D'(G) < 2.
Proposition 2.2. If k > 3, then D'(Qk) = 2.
Proof. For k > 3 a hypercube Qk is Hamiltonian and has at least eight vertices. Therefore, D'(Qk) = 2 by Theorem 2.1.	□
The distinguishing index of the square of cycles and for arbitrary powers of complete graphs with respect to the Cartesian, direct and strong products has been already considered by Pilsniak [12]. In particular, she proved that D'(Cm) =2 for m > 4, and D'(K^) = 2 for any n > 4 and k > 2.
Here we consider Cartesian powers of arbitrary connected graphs. We first prove some lemmas.
Lemma 2.3. Let G and H be connected, relatively prime graphs with D'(G) = D'(H) = 2. Then D'(GdH) = 2.
Proof. We colour one G-layer and one H-layer with distinguishing 2-colourings. The remaining edges can be coloured arbitrarily. Such a colouring breaks all permutations of both horizontal and vertical layers. Since G and H are relatively prime, it follows from Theorem 1.2 that this colouring breaks all automorphisms of GdH.	□
Lemma 2.4. Let G and H be two connected graphs where G is prime, |G| < ||H|| +1 and D'(H) = 2. Then D'(GdH) = 2.
Proof. We first colour the H-layers of the graph GdH. There are at least two H-layers, so we colour all edges of one layer blue, all edges of another one with a distinguishing red-blue colouring. If there are more H-layers, then we colour them such that each of them has a different number of blue edges (including the H-layers coloured previously). This is possible since |G| < ||H|| + 1. Next, we colour all edges in every G-layer red.
72
Ars Math. Contemp. 12 (2017) 111-126
All automorphisms of the Cartesian product generated by the automorphisms of H are broken, since one H-layer assumes a distinguishing colouring. Also, no H-layers can be interchanged as every H-layer has different number of blue edges.
If H has a factor H' isomorphic to G, then GdH has an automorphism interchanging H' with G. However, since all G-layers have only red edges and there exists an H-layer with only blue edges, such an automorphism does not preserve this colouring.	□
Lemma 2.5. If H is a graph with 2 < D'(H) = d, then
2 < D'(HDK2) < d.
Proof. We colour the edges of one H-layer with a distinguishing d-colouring, and all the edges of the other H-layer with the same colour, say 1. Next, we colour all edges of K2-layers with colour 2. Thus all automorphisms of the Cartesian product H□ K generated by the automorphisms of H are broken, since one of the H-layers assumes a distinguishing colouring. Also, the two H-layers cannot be interchanged as they have different numbers of edges coloured with 1.
If H has a factor H' isomorphic to K2, then K2 □ H has an automorphism interchanging H' with K2. However, since all K2-layers have only colour 2 and there exists an H-layer with all edges coloured with 1, such an automorphism does not preserve the colouring.
The equality for d = 2 is obvious since the prism of every graph has a non-trivial automorphism.	□
We now consider the Cartesian powers of arbitrary connected graphs and continue with powers of connected prime graphs on at least three vertices.
Lemma 2.6. If G is a connected prime graph with |G| > 3, then D'(Gfc) = 2 for every k > 2.
Proof. The proof goes by induction on k. Let k = 2. There are n horizontal and n vertical layers, where n = |G|.
Suppose first that G contains a cycle, i.e., ||G|| > n. We colour horizontal G-layers with two colours such that each of them has a different number of blue edges between 0 and n - 1. The other edges are coloured such that every vertical G-layer has a different number of blue edges between 1 to n. As every horizontal G-layer has a different number of blue edges they cannot be interchanged. The same is true for vertical G-layers. Therefore automorphisms of the Cartesian product generated by automorphisms of G are broken. Our colouring also breaks interchanging the factors, since there exists a completely red horizontal G-layer but no such vertical G-layer.
Assume now that G is a tree. Every tree has either a central vertex or a central edge fixed by every automorphism. In case of a tree with a central vertex v, we colour the edges of G2 such that consecutive horizontal layers have 0,..., n -1 blue edges, and consecutive vertical layers have 0,..., n - 1 blue edges in such a way that the horizontal Gv-layer and the vertical Gv-layer have all edges coloured red and blue, respectively. The vertex (v, v) is fixed by every automorphism of G2, hence this colouring is distinguishing. If G has a central edge e0 = uv, we colour the edge (u, u)(v, u) red and the remaining three edges of the subgraph e0^e0 blue. The vertical and horizontal Gv -layers have all edges blue and red, respectively. The remaining edges of G2 are coloured as in the case of a tree with a
A. Gorzkowska et al.: The distinguishing index of the Cartesian product of finite graphs
79
central vertex. Such colouring forbids exchange of the horizonal layers with the vertical layers. Thus D'(G2) = 2.
For the induction step, we apply Lemma 2.4 by taking H = Gk-1 since |G| <
||Gk-1|| + 1.	□
Let us now state the main theorem of this section that solves the problem of the distinguishing index of the k-th Cartesian power of a connected graph.
Theorem 2.7. Let G be a connected graph and k > 2. Then
D'(Gk) = 2
with the only exception: D'(K2) = 3.
Proof. Let G = Gf □ Gp2 □ ... □ GPr, where p > 1, i = 1,..., r, be the prime factor decomposition of G.
Assume first that Gj = K2, i = 1,2,..., r. Then for every i we have D'(Gkpi) = 2 due to Lemma 2.6. By repetitive application of Lemma 2.3 we get D'(Gk) = 2 since Gkpi and Gkpj are relatively prime if i = j.
Suppose now that G has a factor isomorphic to K2, say Gf = K2. If pf > 2, then D'(K2kpi) = 2 and again D'(Gk) = 2 by Lemma 2.3 applied to K2kpi and Gf □ ... □ Gp-. The same argument applies in case p1 = 1 and k > 3. Finally, if p1 = 1 and k = 2 we apply Lemma 2.4 twice and we also get D'(Gk) = 2 unless r =1, i.e., Gk = K2. □
3 Distinguishing Cartesian products
In this section we investigate sufficient conditions on the sizes of factors of the Cartesian product of two graphs to have the distinguishing index equal to two.
3.1 Trees
We begin with a result for trees. Observe first that, by Theorem 1.2, the Cartesian product of two non-isomorphic asymmetric trees is an asymmetric graph, so its distinguishing index is equal to 1.
Theorem 3.1. Let Tm and Tn be trees of size m and n, respectively. If
2 < m < n < 22m+1 -
+ 1,
then D'(TmDT„) < 2.
Proof. If Tm is isomorphic to Tn, then the conclusion follows from Lemma2.6. Therefore, assume that Tm and Tn are non-isomorphic. Then they are relatively prime, and it is enough to prove the existence of a 2-colouring of edges of TmnT„ that breaks the automorphisms generated by automorphisms of Tm and those generated by automorphisms of Tn.
In the proof we use the following well-known fact. In a rooted tree, if a parent vertex is fixed by every automorphism preserving a given colouring and its children cannot be permuted, then the children are also fixed.
Assume first that n = 22m+1 - [m 1 + 1. We choose a root u0 of Tm as follows. If Tm has a central vertex, then we take it as a root u0. If Tm has a central edge, then we choose
74
Ars Math. Contemp. 12 (2017) 111-126
one of its end-vertices as u0 and the other one as ui. Then we choose an enumeration w0,..., um of vertices of the rooted tree Tm satisfying the following condition: if uj is the parent of Uj, then i < j. We enumerate the edge WjWj = ej. Thus E(Tm) = {e1,..., em}. Let v0 be a root of Tn chosen by the same rule as the root w0 of Tm. Then we analogously enumerate vertices and edges of Tn to obtain V(Tn) = {v0,..., vn}, E(Tn) = {ei,.. .,£„}.
We begin by colouring the Tf -layer by putting colour 0 on the edges ej, for i = 1,..., [y], and colour 1 on the remaining edges of this layer. It is easy to see that we can choose such an enumeration of vertices, and hence of edges, that the root w0 is fixed by every automorphism of Tm preserving this colouring. Indeed, this is obvious if w0 is a central vertex; if ei = w0wi is a central edge of Tm, then we enumerate the vertices such that u1,..., u[mJ belong to the same subtree of Tm - e1, therefore our colouring breaks all automorphisms of Tm reversing the end-vertices of e1.
Then, we similarly colour the TU -layer with 0 and 1 in such a way that the vertex (u0,v0) is fixed by every automorphism of TmDT„ preserving this partial colouring. Hence, the Tm -layer, as well as the -layer, is mapped onto itself by every ^ g Aut(TmDT„) preserving this colouring.
Next, we colour the other layers. Consider the set S of all 22m+1 binary sequences of length 2m + 1. Each Tf -layer with i > 1 is assigned a distinct sequence
sj = («0, «1,..., a,, 61..., b,)
from S, where aj, j = 0,..., m, is the colour of the edge ej joining the vertex (wj, vj) with its parent in the Tu -layer (observe that a0 has been already defined for all i > 1), and bj, j = 1,..., m is the colour of the edge of the Tf -layer corresponding to ej. To break all permutations of Tn-layers we delete some sequences from the set S. First observe that the sum of each coordinate taken over all sequences in S is the same (and equal to 22m). Clearly, a T^3 -layer and a T„3' -layer cannot be permuted whenever j < [^ 1 < j' since the edges ej and ej' in the T,f -layer have different colours.
Consider the set A = {sk g S : k = 1,..., [f 1 - 1}, where sk = (a0, a1,..., am, b1,..., bm) is a sequence such that
«j = armHj = 1 j
and all other elements of sk are equal to 0. Thus |S \ A| = 22m+1 - [f 1 + 1. We use the set S \ A to colour Tf -layers, i = 1,..., 22m+1 - [f 1 + 1, hence the numbers of edges coloured with 1 is distinct for every pair of Tn-layers that could be permuted. Thus, all edges in TmDT„ are coloured, and we obtain a distinguishing 2-colouring of TmDT„, when n = 22m+1 - [ f 1 + 1.
Now, assume that the difference l = 22f+1 - [ f 1 +1 - n is positive. We have to choose l sequences from S \ A that will not be used in the colouring. To do this we apply the idea of complementary pairs used in [8]. Denote 0 = 1,1 = 0. A pair of sequences
(ao, a^ . .., am, .. ., bm), (ao, a^ . .., am, .. ., b,)
from S \ A is called complementary. When l is even, we choose | complementary pairs. When l is odd, we choose the sequence (0,..., 0) g S \ A and — complementary pairs. Again all permutations of layers in TmDT„ are broken by this colouring since for every
A. Gorzkowska et al.: The distinguishing index of the Cartesian product of finite graphs
79
pair of Tn-layers that could be permuted, the numbers of edges coloured with 1 is distinct, because aj + aj =1, j = 1,..., m.	□
The bound 22m+1 —" m 1+1 for the size of a larger tree is perhaps not sharp. However, it cannot be improved much since Proposition 3.2 below shows that the distinguishing index of the Cartesian product of a star K1n of size n and a path Pm of order m is greater than 2 whenever n > 22m+1. It also shows that the distinguishing index of the Cartesian product of two graphs with widely different orders and sizes can be arbitrarily large.
Proposition 3.2. If m > 2 and n > 2, then
D'(Ki,n npm} = \ 2m-yn\
unless m = 2 and n = r3 for some r. In the latter case D'(K1,nOP2} = r +1.
Proof. Let d be a positive integer such that (d — 1}2m-1 < n < d2m-1. Denote by v the central vertex of the star K1jn, by v1,..., vn its pendant vertices, and by u1,..., um consecutive vertices of Pm.
Suppose first that m > 3. Clearly, every automorphism of K1nnPm maps the Pm -layer onto itself. We colour the first edge of this layer with 1 and all other edges of it with 2. Thus the Pm-layer is fixed by every automorphism, hence the K1n-layers cannot be permuted.
• •
mmn
Figure 1: A distinguishing 2-colouring of K1j32DP3
We want to show that the remaining edges of K1nnPm can be coloured in such a way that Pm-layers also cannot be interchanged. Then all non-trivial automorphisms of K1nnPm will be broken. Note that a colouring of the yet uncoloured edges can be fully described by defining a matrix M with 2m — 1 rows and n columns such that in the j-th column the initial m — 1 elements are colours of consecutive edges of the Pm! -layer, and the other m elements are colours of the edges of K1n-layers incident to consecutive vertices of the Pm! -layer. It is easily seen that there exists a permutation of Pm-layers preserving colours if and only if M contains at least two identical columns. There are exactly d2m-1 sequences of length 2m — 1 with elements from the set {1,..., d}, hence there exists a colouring with d colours such that every column of M is distinct. Therefore, D'(K1inDPm} < d = I" 1. On the other hand, n > (d — 1}2m-1 so for every edge (d — 1)-colouring of K1jnnPm, the corresponding matrix has to contain two identical columns, therefore D'(K1innPm) > d — 1. Figure 1 presents the case n = 32 and m = 3.
For m = 2, we colour the edges of K1jnDP2 in the same way. The only difference is that every P2-layer has only one edge, hence the two K1n-layers need not be fixed. This
76
Ars Math. Contemp. 12 (2017) 111-126
is the case when n = d3, because then each element of {1,..., d}3 is a column in M, and there exists a permutation of columns of M which together with the transposition of rows of M defines a non-trivial automorphism of K1nnP2 preserving the colouring. Thus we need an additional colour for one edge in a K1n-layer. When n < d3, we put the sequence (1,1, 2) as the first column of M, and we do not use the sequence (1,2,1) any more, thus breaking the transposition of the K1jn-layers, and all automorphisms of K1inmP2. □
Let us mention in passing that D'(K1inmCm) = [ , unless m < 5 and n = 22m. In the latter case D'(K1inmCm) = 2*^/n +1 = 3. The proof can be led on the lines of the proof of Proposition 3.2.
3.2 Arbitrary factors
We now consider the Cartesian product of arbitrary connected graphs. We first formulate a result for relatively prime factors.
Lemma 3.3. Let G and H be connected, relatively prime graphs such that 3 < |G| < |H| < 2|G| (2||g| - 1) - |G| + 2.
Then D'(GdH) < 2.
Proof. Let V(G) = {«1,..., u|G|}, E(G) = {eb ..., e||G||}, V(H) = {v1,..., v|H|}, E(H) = {e1,..., £||H||}. Assume that v1 is a root of a spanning tree TH of the graph H, and the vertices of H are enumerated according to the rooted tree TH, i.e., each child has an index greater than that of its parent. As G and H are relatively prime, the only automorphisms of GdH are permutations of G-layers and H-layers. We first colour the edges of the GV1 -layer with a sequence
(&1,...,&||G||) = (1,..., 1).
We shall not use this sequence to colour the edges of any other G-layer any more. Thus the GV1 -layer will be mapped onto itself by every automorphism of GdH preserving the colouring.
From now on, we proceed similarly as in the proof of Theorem 3.1. For i = 2,..., n, the GVi -layer will be assigned a distinct sequence of colours
(«1, ... ,a|G|,&1,. .. ,b||G||),
where « is a colour of the edge joining the vertex («, vj) to its parent in the rooted tree Th in the Huj-layer, and bj is a colour of ej in the GVi-layer. We have 2|G| (2||G| — 1) such sequences, as we excluded all sequences of the form (a!,...,« G|, 1,..., 1). Thus all permutations of G-layers are broken. To break permutations of H-layers, we also exclude all sequences sk = (a1,..., a|G|, b1,..., b|G|) with a1 = ... = ak = 1 and ak+1 = ... = a|G| = b1 = ... = b||G|| ^ 0, for every k = 1,..., |G| — 1. We have 2|G| (2|G| — 1) — (|G| — 1) sequences to colour |H| — 1 G-layers. Depending on the size of |H|, we also exclude a suitable number of complementary pairs of sequences
(«1,..., a|G|, b1,..., b||G||), (aT,...,«[Gj, b1,..., b|G|)
A. Gorzkowska et al.: The distinguishing index of the Cartesian product of finite graphs
79
and, possibly, a sequence (0,..., 0). Thus we obtain a colouring of GDH with a set of sequences such that the number of 1's is distinct in any of the initial |G| coordinates. Therefore, no permutation of H-layers preserves this colouring. Hence, this is a distinguishing 2-colouring of GDH.	□
Finally, we state the main result of this section.
Theorem 3.4. Let G and H be connected graphs such that
2 < |G| < |H| < 2|G| (2"g" - 1) - |G| + 2. Then D'(GDH) < 2 unless G = H = K2.
Proof. If G = K2, then |H| < 4. If H = K4, then either D'(H) =2 or H is a cycle or a star, and these cases were already settled in Section 2. To construct a distinguishing 2-colouring of K2DK4, colour one edge in one K4-layer and two adjacent edges in the other K4-layer red, and all remaining edges blue.
Let |G| > 3. The case when G and H are relatively prime was settled by Lemma 3.3. Therefore, we focus here on the situation when G and H have at least one common factor. Then D'(GDH) > 2, since the automorphism group of GDH is non-trivial. Let G = Gk1 □ ... DG^4 and H = H^1 □ ... DH^ be the prime factor decompositions of G and H, respectively. Assume that the initial r factors are common, i.e., Gj = H for i = 1,..., r. Denote
Gn = Gk1 □ ... DGkr, Hn = H1 □ ... DH^r.
Thus G = G/ DG// and H = H/ DH//. We use the following notation
n i = |G/1, n2 = |G//1, m 1 = |H/1, m2 = |H//1.
We first show that the distinguishing index of the Cartesian product
G// DH// = Gii + k1 D ... DG^r + kr
is equal to 2. If G//DH// = K|, then |H/1 > 2 and the graphs G/DKf and H/ satisfy the assumptions of Theorem 3.3, hence D'(GDH) = 2, unless |G/DK2| > |H/1, that is |H/1 < 4|G/1. In the latter case, we can also apply Theorem 3.3 for the graphs G/ and H/ which are relatively prime and satisfy the inequalities |G/1 < |H/1 < 2|Gi |(2^Gi H - 1) -|G/1 + 2 unless |G/1 = 2 and < |H/1 < 7, i.e., GDH = Kf DH/, where H/ is prime. So we can apply Proposition 2.2 and Lemma 2.4. In any case D'(GDH) = 2.
If Gji+ki = K22 for every i = 1,..., r, then D'(Gj1+ki) = 2 due to Theorem 2.7, and hence D'(G//DH//) = 2 by repeated application of Lemma 2.3. If Gi1+k1 = K|, then analogously D'(G22+k2 D ... DG[r+kr) = 2, hence D'(G//DH//) = 2 by applying Lemma 2.5 twice.
Consider now the graphs G' = G/ DG// DH// and H' = H/. Clearly, they are relatively prime and
|H'| < |H| < 2|g| (2"g" - 1) - |G| + 2 < 2|g' 1 (2"g'" - 1) - |G'| + 2.
78
Ars Math. Contemp. 12 (2017) 111-126
If also |G'| = nin2m2 < mi = |H'|, then graphs G' and H' satisfy the conditions of Lemma 3.3, and consequently, D'(GDH) = D'(G'DH') = 2. Then suppose that nin2m2 > mi. We consider two cases here.
Assume first that ni < n2m2, i.e., |G/1 < |G//UHn|. Hence, |G/1 < ||G//OHn|| + 1, and by repeated application of Lemma 2.4 we get D'(G') = 2. As |H '| < |G'|, we infer again from Lemma 2.4 that D'(GDH) = D'(G'DH') = 2. In the second case, i.e., when n2m2 < ni, suppose first that
mi = |H/|< 2|Gi|(2i|Gi11 - 1) -|Gi| +2.
Then D'(G/ DH/) < 2 since the assumptions of Lemma 3.3 are satisfied whenever |G/1 < |H/1. Recall that also D'(G//DH//) = 2 and graphs G/DH/ and G//DH// are relati\)ely prime. Hence D'(GDH) = 2 by Lemma 2.3. Otherwise, if mi > 2|G 1 (2I|Gi II - 1) -|G/1 + 2, then we arrive at the sequence of inequalities
mi < nin2m2 < n2 < 2ni (2ni - 1) - ni + 2 < 2|Gi |(2|Gi 1 - l) - |G/1 +2 < mi, which is impossible.
Then suppose that |G/1 = ni > mi = |H/1 (and still n2m2 < ni). Let G'' = G/ and H'' = G//DH/DH//. Clearly, |G''| < |H''| since |G| < |H|. Moreover, we have
|H''| = n2m2mi < nimi < ni < 2^"' (2|G"" - 1) - |G''| + 2. It follows from Lemma 3.3 that D'(GDH) = D'(G''DH'') = 2.	□
Acknowledgment. The authors are very indebted to Wilfried Imrich for introducing them to the concept of symmetry breaking in graphs, and for many helpful discussions and suggestions.
References
[1]	M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), Research Paper 18, approx. 17 pp. (electronic), http://www.combinatorics. org/Volume_3/Abstracts/v3i1r18.html.
[2]	I. Broere and M. PilSniak, The distinguishing index of infinite graphs, Electron. J. Combin. 22 (2015), Paper 1.78, 10.
[3]	I. Broere and M. PilSniak, The distinguishing index of the Cartesian product of countable graphs, Submitted.
[4]	E. Estaji, W. Imrich, R. Kalinowski, M. PilSniak and T. Tucker, Distinguishing products of finite and countably infinite graphs, Discuss. Math. Graph Theory (to appear).
[5]	M. J. Fisher and G. Isaak, Distinguishing colorings of Cartesian products of complete graphs, Discrete Math. 308 (2008), 2240-2246, doi:10.1016/j.disc.2007.04.070, http://dx.doi. org/10.1016/j.disc.2007.04.070.
[6]	R. Hammack, W. Imrich and S. Klavzar, Handbook of product graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2nd edition, 2011, with a foreword by Peter Winkler.
A. Gorzkowska et al.: The distinguishing index of the Cartesian product of finite graphs
79
[7]	W. Imrich, Automorphismen und das kartesische Produkt von Graphen, OÖsterreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II 177 (1969), 203-214.
[8]	W. Imrich, J. Jerebic and S. KlavZar, The distinguishing number of Cartesian products of complete graphs, European J. Combin. 29 (2008), 922-929, doi:10.1016/j.ejc.2007.11.018, http://dx.doi.org/10.1016/j.ejc.20 07.11.018.
[9]	W. Imrich and S. KlavZar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006), 250-260, doi:10.1002/jgt.20190, http://dx.doi.org/10.1002/jgt.20190.
[10]	R. Kalinowski and M. PilSniak, Distinguishing graphs by edge-colourings, European J. Combin. 45 (2015), 124-131, doi:10.1016/j.ejc.2014.11.003, http://dx.doi.org/10. 1016/j.ejc.2014.11.003.
[11]	D. J. Miller, The automorphism group of a product of graphs, Proc. Amer. Math. Soc. 25 (1970), 24-28.
[12]	M. PilSniak, Edge motion and the distinguishing index, preprint Nr MD 076, http://www. ii.uj.edu.pl/preMD.
[13]	M. PilSniak, Nordhaus-Gaddum bounds for the distinguishing index, preprint Nr MD 083, http://www.ii.uj.edu.pl/preMD.