ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 259-274
Improving upper bounds for the distinguishing
index
Received 27 November 2015, accepted 13 February 2017, published online 6 March 2017
The distinguishing index of a graph G, denoted by D'(G), is the least number of colours in an edge colouring of G not preserved by any non-trivial automorphism. We characterize all connected graphs G with D'(G) > A(G). We show that D'(G) < 2 if G is a traceable graph of order at least seven, and D' (G) < 3 if G is either claw-free or 3-connected and planar. We also investigate the Nordhaus-Gaddum type relation: 2 < D'(G) + D'(G) < max{A(G), A(G)} + 2 and we confirm it for some classes of graphs.
Keywords: Edge colouring, symmetry breaking in graph, distinguishing index, claw-free graph, planar graph.
Math. Subj. Class.: 05C05, 05C10, 05C15, 05C45
1 Introduction
We follow standard terminology and notation of graph theory (cf. [12]). In this paper, we consider general, i.e. not necessarily proper, edge colourings of graphs. Such a colouring f of a graph G breaks an automorphism p e Aut(G) if p does not preserve colours of f. The distinguishing index D'(G) of a graph G is the least number d such that G admits an edge colouring with d colours that breaks all non-trivial automorphisms (such a colouring is called a distinguishing edge d-colouring). Clearly, D'(K2) is not defined, so in this paper, a graph G is called admissible if neither G nor G contains K2 as a connected component.
The definition of D'(G) introduced by Kalinowski and Pilsniak in [17] was inspired by the distinguishing number D(G) which was defined for general vertex colourings by Albertson and Collins [1]. Another concept is the distinguishing chromatic number xd(G)
*The research was partially supported by the Polish Ministry of Science and Higher Education. The author would like to thank an anonymous reviewer whose remarks and comments have been a great help in preparing the final version.
E-mail address: pilsniak@agh.edu.pl (Monika Pilsniak)
Monika Pilsniak *
AGH University, Department of Discrete Mathematics, al. Mickiewicza 30, 30-059 Krakow, Poland

Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
260
Ars Math. Contemp. 13 (2017) 293-306
introduced by Collins and Trenk [7] for proper vertex colourings. Both numbers, D(G) and Xd (G), have been intensively investigated by many authors in recent years [4, 5, 6, 9, 16].
Our investigation was motivated by the renowned result of Nordhaus-Gaddum [18] who proved in 1956 the following lower and upper bounds for the sum of the chromatic numbers of a graph and its complement (actually, the upper bound was first proved by Zykov [22] in 1949).
Theorem 1.1 ([18]). If G is a graph of order n with the chromatic number x(G), then
< x(G) + X(G) < n +1.
Since then, Nordhaus-Gaddum type bounds were obtained for many graph invariants. An exhaustive survey is given in [2]. Here, we adduce only those closely related to the topic of our paper.
In 1964, Vizing [20] considered proper edge colourings and he proved Nordhaus-Gaddum type bounds for the chromatic index of a graph.
Theorem 1.2 ([20]). If G is a graph of order n with the chromatic index x'(G), then
n - 1 < x'(G)+ x'(G) < 2(n - 1).
In 2013, Collins and Trenk [8] proved Nordhaus-Gaddum type inequalities for the distinguishing chromatic number.
Theorem 1.3 ([8]). For every graph of order n and distinguishing number D(G) the following inequalities are satisfied
2Vn < xd(G) + xd(G) < n + D(G).
Kalinowski and Pilsniak [17] also introduced a distinguishing chromatic index xDd (G) of a graph G as the least number of colours in a proper edge colouring that breaks all non-trivial automorphisms of G. They proved the following somewhat unexpected result.
Theorem 1.4 ([17]). If G is a connected graph of order n > 3, then
Xd(G) < A(G) + 1
unless G e [CA, K4, C6, K33} when xDD(G) < A(G) + 2.
The following Nordhaus-Gaddum type inequalities for the distinguishing chromatic index are the same as in Theorem 1.2 but we have to be more careful in the proof.
Theorem 1.5. If G is an admissible graph of order n > 3, then
n - 1 < xD(G) + xD(G) < 2(n - 1)
with the only exception Ki,4.
Proof. Without loss of generality we may assume that G is connected. It can be easily checked that the conclusion holds if G e {K4, C6, C6, K3,3}. Otherwise, xD(G) < A(G) + 1. Suppose first that G is also connected. By Theorem 1.4,
A(G) + A(G) < xD(G) + xD(G) < A(G) + A(G) + 2.
M. Pilsniak: Improving upper bounds for the distinguishing index
261
Clearly, n - < A(G) + A(G) < 2(n - 2) since both G and G are connected.
Now, let G be disconnected (but admissible). If there are two nonisomorphic components of G of orders k1 and k2 such that 3 < k1 < k2, then A(G) < n — ki — 1 < n — 4, so xD (G) < n — 2. If G has t > 2 components isomorphic to a graph H of order at least three, then xD (H) < J + 1 as A(H) < J — 1. Even if we wastefully add an extra colour for each additional copy of H, we get xD (tH) < j + 1+t — 1 = j +t < n — 2 unless G = K3 3 but this we already checked.
To complete the proof it is enough to settle the case when G has only one component H of order at least three and some isolated vertices. Hence, A(H) < n — 2. It is easy to check that xD(G) + xD(G) < 2(n_— 1) for H G {K4, Ge, G6, ^3,3} except for H = K4 when G = K1j4. Otherwise, xD(G) < n — 1 and the conclusion holds unless |G| = |H| + 1 and A(H) = n — 2. But then G has a unique vertex x of degree n — 1 (hence, x is fixed by every automorphism of G) with a pendant edge. The graph G — x has a distinguishing colouring with n — 1 colours by Theorem 1.4 since A(G — x) < n — 2. It suffices to colour the pendant edge with a colour missing at x to see that xD (G) < n — 1.	□
Collins and Trenk observed in [8] that the Nordhaus-Gaddum type relation is trivial for the distinguishing number, as D(G) + D(G) = 2D(G) since Aut(G) = Aut(G) and every colouring of V(G) breaking all non-trivial automorphisms of G also breaks those of G.
In Section 4 we formulate and discuss the following conjecture.
Conjecture 1.6. Let G be an admissible graph of order n > 7, and let A = max{A(G), A(G)}. Then	_
2 < D'(G) + D'(G) < A+ 2.
In Section 2 we characterize graphs G which need exactly A(G) colours to break all non-trivial automorphisms. In Section 3 we give upper bounds for the distinguishing index of traceable graphs, claw-free graphs, planar graphs and 2-connected graphs.
2 Improved general upper bound
In the sequel, we make use of some facts proved in [17].
Proposition 2.1 ([17]). D'(P„) = 2 for every n > 3.
Proposition 2.2 ([17]). D'(G„) = 3 for n < 5, and D'(G„) =2 for n > 6.
Proposition 2.3 ([17]). D'(K„) = 3 if 3 < n < 5, and D'(K„) =2 if n > 6.
Proposition 2.4 ([17]). D'(Kj,3) = 3, and D'(K„,„) = 2 if n > 4.
By the well-known theorem of Jordan (cf. [12]), every finite tree T has either a central vertex or a central edge, which is fixed by every automorphism of T. In the proof of Theorem 2.8, which is the main result of this section, we use Lemma 2.5, a simple generalization of the theorem of Jordan. Recall that the eccentricity of a vertex v in a connected graph G is the number
eG(v) = max{d(v, u) : u G V(G)}.
The center of a graph G is the set Z(G) of vertices with minimum eccentricity. Clearly, the center of G is setwise fixed by every automorphism ^ G Aut(G), i.e. y(v) G Z(G) if v G Z(G). A proper subgraph H of G is called pendant if it has only one vertex adjacent to vertices outside H.
262
Ars Math. Contemp. 13 (2017) 293-306
Lemma 2.5. Let G be a connected graph such that every cycle is contained in a clique. Then the center of G is either a single vertex or a maximal clique.
Proof. The claim is true if G is a clique Kk of order k > 1. Otherwise, k(G) = 1, and each block of G is a clique of order at least two. We then modify the standard proof of the theorem of Jordan for trees. Let G- be a graph obtained from G by deleting k — 1 vertices of degree k — 1 in every pendant clique Kk with k > 2. Clearly, eG- (v) = eG(v) — 1 for each v e V(G-). Consequently, Z(G-) = Z(G). We continue this process until only one clique Kk is left for some k > 1. This clique is maximal whenever k > 2.	□
A symmetric tree, denoted by Th,d, is a tree with a central vertex v0, all leaves at the same distance h from v0 and all vertices that are not leaves of equal degree d. A bisymmetric tree, denoted by Th'd, is a tree with a central edge e0, all leaves at the same distance h from the edge e0 and all vertices which are not leaves of equal degree d.
Theorem 2.6 ([17]). If T is a tree of order n > 3, then D' (T) < A(T). Moreover, equality is achieved if and only if T is either a symmetric or a bisymmetric tree.
For connected graphs in general there is the following upper bound for D'(G).
Theorem 2.7 ([17]). If G is a connected graph of order n > 3, then
D'(G) < A(G)
unless G is C3, C4 or C5.
It follows for connected graphs that D'(G) > A(G) if and only if D'(G) = A(G) + 1 and G is a cycle of length at most 5. The equality D'(G) = A(G) holds for cycles of length at least 6, for K4, K3,3 and for all symmetric or bisymmetric trees. Now, we show that D'(G) < A(G) for all other connected graphs. A palette of a vertex is the multiset of colours of edges incident to it.
Theorem 2.8. Let G be a connected graph that is neither a symmetric nor a bisymmetric tree. If the maximum degree of G is at least 3, then
D'(G) < A(G) — 1
unless G is K4 or K3,3.
Proof. Denote A = A(G). The conclusion holds for trees due to Theorem 2.6. Then assume that G contains a cycle. The general idea of the proof is the following. If G does not contain a cycle of length greater than three, then we define G' as an empty graph. Otherwise, we consecutively delete pendant trees and pendant triangles until we obtain a subgraph G'. Then, we construct an edge colouring f with A — 1 colours stabilizing all vertices of G' by every automorphism preserving f. Finally, we colour pendant subtrees and pendant triangles to complete a distinguishing colouring with A — 1 colours of the whole graph G.
If A(G') = 2, then G' is a cycle Cp having a distinguishing colouring with A — 1 colours unless p e {4, 5} and A = 3. In this case, it can be easily checked that the graph G+ induced by Cp and the independent edges of G incident to Cp can always be coloured with two colours such that the vertices of Cp are fixed by every colour preserving
M. Pilsniak: Improving upper bounds for the distinguishing index
263
automorphism. So we can assume that A(G') > 3. If G' G {K4, K3,3}, then G' = G due to the assumption, hence A > 4, so we can stabilize K4 or K3,3 with three colours.
Let Ni (v) denote the i-th sphere in v, i.e. the set of vertices of distance i from the vertex v. Let x be a vertex with maximum degree in G'. We colour with 1 all edges incident with x. In our edge colouring f of the graph G', the vertex x will be the unique vertex of maximum degree with the monochromatic palette {1,..., 1}. Hence, x will be fixed by every automorphism ^ preserving f. Consequently, ^ maps each sphere Ni(x) onto itself.
The first sphere Ni(x) can be partitioned into subsets Mk, for k = 0,..., A - 1, defined as
Mfc = {v G Ni(x) : |Ni(v) n N2(x)| = k}.
Denote Mfc = {vi,..., vifc}. Thus, lo + Zi + ... + Za-i = A.
We want to find a colouring f of the edges of G'[Ni(x) U N2(x)] and, if necessary, of some subsequent spheres, such that each vertex of Ni(x) U N2(x) is fixed by every automorphism preserving this colouring. To do this, we proceed in a number of steps Mk, for k = 0,..., A - 1. In each step Mk, we find a colouring that fixes the vertices of Mk and their neighbours in N2(x).
Step M0. First we consider the case when the subgraph G' [M0] induced by the vertices of M0 is connected. Observe that A(G' [M0]) < A -1 and, by Theorem 2.7, we can colour distinguishingly the edges of G'[M0] with A - 1 colours, even if G'[M0] is a short cycle Cp with 3 < p < 5. Indeed, if G'[M0 = C3 and A = 3, then we would have G = K4, but K4 is excluded. Otherwise, A > 4 and we can use a third colour in a short cycle Cp. It may happen that there exists a vertex v g M0 of degree A in G' (so |M0| = A) with a monochromatic palette {1,..., 1} in a colouring of G'[M0] given by Theorem 2.7. In this case, either G is a complete graph Kn with n > 5 so D'(Kn) < A - 1 by Proposition 2.3, or it is not difficult to see that there exists a colour c such that there is no vertex with all incident edges coloured with c; whence we can exchange c and 1 in this colouring of G'[M0 ].
Now, let G' [M0] be disconnected. Let zi,..., zs be isolated vertices or end-vertices of isolated edges in G'[M0]. Clearly, s < A - 1 by the definition of G'. If s = A - 1, then we colour with i every edge ziu, where u G Ni(x) \ M0. Otherwise, we colour ziu with i + 1 for i = 1,..., s. Thus, we avoid a monochromatic palette of {1,..., 1} at another vertex of maximum degree in G'.
We also have to distinguish all isomorphic components of G'[M0] of order greater than 2. Denote such a component by H and suppose that G'[M0] contains t components isomorphic to H, for some t > 2. Hence t < A and A(H) < A - 1. Therefore, we can choose distinct sets of A colours for every component since
A - 1\ (A - 1\ A
A
> „ \>^>t-
3-3
Thus each vertex of M0 is fixed.
Step Mi. For every i = 1,..., Zi, we colour the edge viu, where u G N2(x), with a distinct colour from {1,..., A - 1}. This is impossible only if Zi = A, when we have to have two vertices a, b G Mi with the same colour of edges aa' and 66', where a' and b' are neighbours of a and b in N2 (x), respectively. If G'[Mi] contains an edge e, then we colour it with 1, and all other edges of G'[Mi] with 2. Then we choose exactly one of the vertices a, b incident to e. We proceed analogously when G'[N2(x)] contains an edge. Then all
264
Ars Math. Contemp. 13 (2017) 293-306
vertices of M1 are fixed unless Z1 = A and neither G'[Ni(x)j nor G'[N2(x)] contains an edge.
If |N2 (x)| = 1, then G' is isomorphic to K2,A. It is easy to see that D'(K2,A) < A -1 for A > 3 (for A > 4 this immediately follows from Lemma 3.1 and Corollary 3.8). If 2 < |N2(x)| < A - 1, then choosing a and b such that a' has at least two neighbours in N1 (x) and b' = a' yields a colouring fixing N1 (x) U N2 (x).
Suppose |N2(x)| = A. If there is a vertex v e N2(x) with less than A - 1 neighbours in N3(x), then we choose a such that a' = v, and it suffices to reserve a unique set of colours for the edges between a' and N3(x).
Hence, assume that every vertex of N2(x) has A - 1 neighbours in N3(x). We select two vertices a, b e M1 and assume that the colours of the edges aa' and bb' are the same. Next, we implement the following Procedure SUBTREES (a, b), which we also use in subsequent steps.
_Procedure SUBTREES (a, b)_
We are given two vertices a, b e N1 (x) such that each their neighbour in N2 (x) is adjacent to A - 1 vertices of N3(x).
Let Ta be a maximal subtree of the graph G'[{a} U |J2 N (x)], rooted at a, such that all leaves of Ta belong to the same sphere Nl_1(x) and each vertex of V(Ta) n Ni-1(x) has A - 1 neighbours in Nj(x) for i = 3,..., Z. Thus Z > 3. Define a graph
Ta = G' [ J N (v)],
(Ta )\{a}
i.e. Ta is a graph obtained from Ta by adding all edges incident with the leaves of Ta. Analogously, we define a tree Tb and a graph Tb. Observe that the trees Ta and Tb are disjoint and non-empty.
The edges incident to the roots a and b are already coloured. For every other vertex of Ta and Tb, we colour its incident edges going to the next sphere with distinct colours from {1,..., A - 1}. Thus we obtain an edge colouring f. The only automorphism of Ta (as well as of Tb) preserving f is the identity. The vertex x will be fixed by every colour preserving automorphism y>. Consequently, ^ maps Ta onto Tb whenever y>(a) = b. Thus, if Ta and Tb are not isomorphic, then f distinguishes all vertices in V(Ta) U V (Tb). Hence, assume that the rooted graphs Ta and Tb are isomorphic. Observe that there exists exactly one non-trivial isomorphism : V (Ta) ^ V (Tb) preserving f since each vertex in Ta has a distinct coloured path from the root a.
Denote = (V(Ta) U V(Tb)) n N;(x). By our choice of G', all vertices in Wi are of degree at least two in G'. It follows that one of the following three cases has to hold.
Case 1. There exist vertices in Wl adjacent to more than one vertex of Wl_1. Then we modify f by colouring again all edges between such vertices and Wl_1 in order to break any possible permutation of Wl. A permutation of a set L C Wl can be extended to an automorphism of G' that fixes all leaves of Ta U Tb only if every vertex from L have the same set of neighbours U = {u1,..., in Wl_1. Such a set L contains at most A - 1 leaves since the number of edges joining U to Wl equals d(A - 1). Every permutation of L will be broken whenever for every vertex w e L the multiset of colours of the edges wu1,..., wud will be distinct. Clearly, d < A. There are (A+d_2) such possible multisets of A - 1 colours. Clearly, (A+d_2) - 1 > A - 1 for A > 3 and d > 2. We can exclude a
M. Pilsniak: Improving upper bounds for the distinguishing index
265
a
Figure 1: An example of the subgraph Ta for A = 4 and l = 4. The edges of Ta between W3 and W4 that do not belong to the tree Ta are dashed.
rainbow multiset P = {1,..., d} (or an almost rainbow multiset P = {1,..., A—1, A-1} if d = A) and we still have enough multisets to colour the edges incident with vertices of L. Moreover, for d = A we can also exclude a monochromatic palette {1,..., 1} since (2A_2) — 2 > A — 1 for A > 3.
We partition the set W; into maximal subsets L with the same set of neighbours and assign suitable multisets of colours to each set L. We thus obtain a colouring fixing all vertices from W; unless can be extended to an isomorphism of Ta onto Tb preserving this colouring. To break every such possible extension it suffices to assign the excluded multiset P to one vertex of one set L.
Case 2. Every vertex in W; has only one neighbour in W;_i and the set of edges F = E (G'[W; ]) is non-empty. Then we colour one edge of F with 1, and all other edges in F with 2. This colouring fixes all vertices of Ta and Ta unless all edges in F are of the form w^0(w), where w^0(w) is one of possible extensions of to an isomorphism of Ta onto Tb. In such a case, we choose one edge ww' e F and exchange colours of the edge wu, where u e W;_1, with another edge between u and W;.
Case 3. Every vertex in W; has only one neighbour in W;-1 and no neighbours in W;. By the maximality of the trees Ta and Tb and the definition of G', each vertex in W; has at least one neighbour in N;+1(x) and there exists a vertex w0 e W; with s < A — 1 neighbours y1,..., ys e N;+1(x). We colour each edge w0yj with colour j + 1 for j = 1,..., s. Next, for every vertex w e W;, we colour the set of edges between w and N;+1 (x) with a set of A — 1 colours excluding the set {2,..., s +1}.
We thus obtained a colouring f of the edges of G' [V(Ta) U V(Tb)], and the edges incident to W; in Case 3, fixing all vertices of Ta and Tb.
_End of Procedure SUBTREES (a, b)_
Step M2. For every i = 1,..., l2, we colour the edges vju1, vju2 where {u1, u2} C N2(x), with distinct sets of colours from among (A-1) sets. This is impossible only in the following three cases (in each case, we can assume that neither G'[N1(x)] nor G'[N2(x)] contains an edge, otherwise we could construct a distinguishing colouring f of G' [N1 (x) U N2(x)] analogously as in step M1):
266
Ars Math. Contemp. 13 (2017) 293-306
a)	12 = A = 4. If there exist two vertices a and b in M2 such that N(a) n N(b) n N2 (x) = 0, then we colour with 2 both edges incident with b, and for the remaining vertices in M2 we have distinct sets of colours from among (3) sets. If for every two vertices a, b G M2, the set N(a) n N(b) n N2(x) is empty, then two vertices a and b are assign the same pair of distinct colours, and we can distinguish them in next spheres using the procedure SUBTREES (a, b).
b)	12 = A - 1 and A = 3. Let M2 = {a, b}. If N(a) n N(b) n N2(x) = 0, then we colour edges incident with a with colours 1 and 2, and both edges incident with b with 2. If the set N(a) n N(b) n N2(x) is empty, then a and b get the same pair of distinct colours and we can distinguish them in next spheres by the procedure SUBTREES (a, b).
c)	12 = A = 3. Let M2 = {a, b, c}. If for two vertices of M2, say a and b, the set N(a) n N(b) n N2(x) is non-empty, then we can colour with 2 both edges incident with b and we colour edges incident with the remaining vertices of M2 with a couple {1, 2}. It is not difficult to verify that this way, for every configuration of neighbours of M2, we can obtain colouring fixing the vertices of Ni(x) U N2(x) unless |N(a) n N(b) n N(c) n N2(x)| = 2. But then G' = G = #3,3, contrary to the assumption. If every vertex of N2(x) is adjacent only to one vertex of M2, then the pairs of edges incident to a and b are assign the same pair of colours {1,2}, and we distinguish them using the procedure SUBTREES (a, b). Both edges cu1, cu2 incident with c are coloured with 2, and to distinguish them, we split c into two vertices ci and c2, each joined by an edge coloured with 2 to u1 and u2, respectively, and apply the procedure SUBTREES (c1, c2).
Step Mk, for k > 3. For every i = 1,..., 1k, we colour the edges between vi and N2(x) with distinct sets of k colours from among (A-1) sets. It is always possible whenever (A-1) > 1k. This inequality does not hold only in two cases:
a)	k = A - 2 and 1k = A. In this case we define a colouring with A - 1 colours like in step M2 a). Namely, if either a vertex of Mk or its neighbour in N2(x) is adjacent to a vertex in the same sphere, then we can define a colouring fixing all these vertices analogously as in step M1 and step M2. Also, if there are two vertices a, b G MA-2 with a common neighbour in N2 (x), we can assign the same palette to a and b as in the previous steps. Otherwise, two vertices a, b G MA-2 are assign the same palette of A - 2 colours and we distinguish them using Procedure SUBTREES (a, b).
b)	k = A - 1 and 1k > 2. Hence, A > 4. For every i = 1,..., 1k, the set of edges between vi G MA-1 and N2 (x) will be assign a distinct multiset Pi of colours from the set {1,..., A - 1}, where only colour i appears twice. Moreover, one vertex can assign a rainbow palette {1,..., A - 1}. Thus every vertex of MA-1 will have a distinct palette, and hence will be stabilized. To stabilize the two vertices of N2(x) joined to vi by edges of colour i, we examine the vertices v1,..., vA-1 of MA-1 in the following order.
First, we consider each vertex vi that have a neighbour wi g N2 (x) with at least one but at most A - 2 neighbours in N3(x). We choose another neighbour w'i G N2(x) of vi and assign two distinct sets of colours for the edges going to N3 (x) from wi and wi, respectively. We colour the edges vi wi and viw' with the same colour i. Thus all neighbours of vi are stabilized.
M. Pilsniak: Improving upper bounds for the distinguishing index
267
In the next stage, we consider every vertex vi with every neighbour in N2 (x) adjacent to A - 1 vertices of N3(x). We colour the set of edges between vi and N2(x) with the palette P\ where two edges VjUi, v^2 are coloured with i. Then we delete vi and introduce two vertices v1, v? and edges v/u and v?u2 coloured with i. Then we use the procedure SUBTREES (v1, v?) to stabilize u1 and u2.
Further, we consider each vertex vi with a neighbour wi G N2(x) incident to an edge wiu, where u G N2(x). First, we look for such an edge wju, which is already coloured. If there is no such edge, we take an uncoloured wiu and colour it with colour 3. In both cases, we put colour i on the edge viwi and another edge viw with w — u. After we examine each such vertex vi, we colour with 2 all remaining edges contained in N2 (x).
Finally, we are left with at most A vertices vi such that every neighbour of vi is adjacent only to (at least two) vertices of N1(x). We take a first such vertex vi and assign colour i to two its incident edges viwi and viw-. Thus all neighbours of vi are stabilized unless common neighbours of wi and w' were not considered yet. Then we take such a neighbour vj and colour its incident edges with the palette Pj such that the edges vjwi and vjw- have distinct colours. We repeat this procedure until only one vertex of MA-1 is left. We put a rainbow palette {1,..., A - 1} on its incident edges.
After we accomplish steps M0,..., Ma_1, we colour all uncoloured edges in subgraphs G'[N1(x)j and G'[N2(x)] with 2. Each vertex of N1(x) U N2(x) is now fixed by every automorphism preserving our colouring f of edges of G'[{x} U N1(x) U N2(x)], and of some edges between next spheres, if the procedure SUBTREES was used.
Then we recursively colour all yet uncoloured edges incident to consecutive spheres Ni(x) as follows: for v G Ni(x), i > 2, we colour all edges vu, where u G Ni+1(x), with distinct colours from {1,..., A - 1}. This is always possible since every vertex of Ni(x) has at most A - 1 neighbours in Ni+1(x). Finally, we colour all uncoloured edges with end-vertices in the same sphere with 2. Hence, all vertices of G' are fixed by any automorphism preserving our colouring f. It is also easily seen that the already coloured edges can save their colours. Moreover, it is not difficult to observe that x is the unique vertex of maximum degree with a monochromatic palette {1,..., 1}. Thus, the whole subgraph G' (or G+) is fixed.
To end the proof, we colour pendant trees and triangles deleted from G at the beginning. First assume that G' is not empty. Let Ni(G'), for i > 0, be the set of vertices of distance i from G'. Then we recursively colour the edges incident to consecutive spheres Ni(G') in the following way: for v G Ni(G'), i > 0, we colour all edges vu, where u G Ni+1(G'), with distinct colours from {1,..., A - 1} and the remaining edges incident to v, contained in Ni(x), with 2. Hence, all vertices of G will be fixed by any automorphism preserving our colouring f.
If G' is empty, then we start with the centre Z(G) that is setwise fixed by every automorphism. It follows from Lemma 2.5 that Z(G) either induces K3, or K2 (not contained in K3), or K1. Let first Z(G) induce a triangle K3. If A — 3, then we stabilize Z(G) by colouring with two colours all edges incident with vertices of Z(G). When A > 4, we can colour the edges of the triangle Z(G) with three colours. Next, we recursively colour edges incident to subsequent spheres Ni(Z(G)) with A - 1 colours.
If Z(G) is an edge e, then G - e has two components. We distinguish each of them
268
Ars Math. Contemp. 13 (2017) 293-306
by colouring subsequent spheres Ni(Z(G)) with A - 1 colours. If the components are isomorphic, then by assumption, each of them has a triangle. We colour two edges of these triangles contained in a sphere Ni(Z(G)), for some i > 2, with two distinct colours.
Finally, let Z (G) be a single vertex z. Hence, G - z has q > 2 components, each joined to z by one or two edges. If q < A, then we can easily colour distinguishingly the edges incident with subsequent spheres Ni(z), i > 0, with A - 1 colours. If q = A, then we choose two components of G - z, at least one of them with a triangle, and colour their two edges incident with z with the same colour. Then we distinguish these two components by an edge of the triangle.	□
3 Some classes of graphs
A graph G is called asymmetric if its automorphism group is trivial. Then obviously
D'(G) = 1.
We say that a graph G is almost spanned by a subgraph H (not necessarily connected) if G - v is spanned by H for some v e V(G). The following observation will play a crucial role in this section.
Lemma 3.1. If a graph G is spanned or almost spanned by a subgraph H, then
D'(G) < D'(H) + 1.
Proof. We colour the edges of H with colours 1,..., D'(H), and all other edges of G with an additional colour 0. If p is an automorphism of G preserving this colouring, then p(x) = x, for each x e V(H). Moreover, if H is a spanning subgraph of G - v, then also p(v) = v. Therefore, p is the identity.	□
3.1	Traceable graphs
Recall that a graph is traceable if it contains a Hamiltonian path.
Theorem 3.2. If G is a traceable graph of order n > 7, then D'(G) < 2.
Proof. Let Pn = viv2... vn be a Hamiltonian path of G. If G = Pn, then the conclusion follows from Proposition 2.1. If G is isomorphic to Pn+v i v3, then we colour the edge v i v3 with 1, and all other edges with 2 breaking all non-trivial automorphisms of G. So suppose that G contains an edge vivj- distinct from viv3 and vn_2vn with i < j - 1. Without loss of generality we may assume that i - 1 < n - j (otherwise we reverse the labeling). It is easy to see that at least one of the graphs Pn + vivj - vj-ivj, Pn + vivj - vj-_i or Pn + vivj - vn is an asymmetric spanning or almost spanning subgraph of G for any n > 7. The conclusion follows from Lemma 3.1.	□
The assumption n > 7 is substantial in Theorem 3.2 as D'(K3,3) = 3.
3.2	Claw-free graphs
A Ki 3-free graph, called also a claw-free graph, is a graph containing no copy of Ki 3 as an induced subgraph. Claw-free graphs have numerous applications, e.g., in operations research and scheduling theory. For a survey of claw-free graphs and their applications consult [10].
A k-tree of a connected graph is its spanning tree with maximum degree at most k. Win [21] investigated spanning trees in 1-tough graphs and proved the following result.
M. Pilsniak: Improving upper bounds for the distinguishing index
269
Theorem 3.3 ([21]). A 2-connected claw-free graph has a 3-tree.
We use this result to give an upper bound for the distinguishing number of claw-free graphs.
Theorem 3.4. If G is a connected claw-free graph, then D'(G) < 3.
Proof. Assume first that G is 2-connected. By Theorem 3.3, G contains a 3-tree T. By Theorem 2.6, we have D'(T) < 2 if T is neither symmetric nor bisymmetric tree. In such a case, D'(G) < 3 by Lemma 3.1.
Let T be a symmetric tree Th,3. Denote a central vertex of T by x and its neighbours by a, b, c. Since G is a claw-free graph, there^xists in G at least one edge, say bc, in the neighbourhood of x in T. Define a subgraph T = T + bc. We colour bc, xa and xb with 1, and xc with 2. Thus all vertices a, b, c, x are fixed by every non-trivial automorphism of T. We now colour the remaining edges in T starting from the edges incident to a, b, c in such a way that two uncoloured adjacent edges obtain two different colours 1 and 2. This 2-colouring breaks all non-trivial automorphisms of T. Hence, D'(G) < 3 by Lemma 3.1.
Let T be a bisymmetric tree Th'3. Denote a central edge by xy and its neighbours by a, b adjacent to x, and c, d adjacent to y. We colour xy, xa and yc with 1, and xb and yd with 2. Since G is claw-free, there exists in G either at least one of the edges by, cx (or symmetrically dx or ay) or both ab and cd. We define a subgraph T obtained from the tree T by adding either one of the edges by, cx (or symmetrically, dx or ay) or both ab and cd. In the first case we colour by or cx (or symmetrically, dx or ay) with 1, in the second case we colour ab with 1 and cd with 2. Now all vertices a, b, c, d, x, y are fixed by every non-trivial automorphism of T. We then colour the remaining edges of T as above, and we obtain the claim.
If a graph G is not 2-connected, then its graph of blocks and cut-vertices is a path, since G is claw-free. We colour every block according to the rules described above. Then to break all non-trivial automorphisms of G, it is enough to break a possible automorphism 0 € Aut(G) that exchanges two terminal blocks. Let z be a cut-vertex that belongs to a terminal block B0. It follows that z and its neighbours in B0 induce a clique K of order k > 2. We have three colours in our disposal, so it is easily seen that we can permute the colours to obtain a nonisomorphic colouring of K, thus breaking 0.	□
The theorem is sharp for graphs of order at most 5. We conjecture that the distinguishing index of claw-free graphs of order big enough is 2.
3.3 Planar graphs
First, recall that by the famous Theorem of Tutte [19], every 4-connected planar graph G is Hamiltonian. Hence, its distinguishing index is at most 2, by Theorem 3.2, whenever |G| > 7. A similar result as for claw-free graphs we obtain for 3-connected planar graphs. In the proof, we use the following result of Barnette about spanning trees of such graphs.
Theorem 3.5 ([3]). Every 3-connected planar graph has a 3-tree.
Using a similar method as in the proof of Theorem 3.4, we obtain the following.
Theorem 3.6. If G is 3-connected planar graph, then D'(G) < 3.
270
Ars Math. Contemp. 13 (2017) 293-306
Proof. Let T be a 3-tree of G. It follows from Theorem 2.6 that D'(T) < 2 and hence, D'(G) < 3 by Lemma 3.1, if T is neither a symmetric nor a bisymmetric tree.
Let then T be a symmetric tree Th,3. Denote the central vertex by x, and by Ta, Tb and Tc the connected components of T - x which are trees rooted at the neighbours a, b, c of a vertex x, respectively. Since G is 3-connected, there exist an edge e between Ta and Tb in G. Consider a spanning subgraph T = T + e. Then we colour xa and xc with 1, and xb with 2, and extend this colouring as in Jhe proof of Theorem 3.4 to a colouring of T breaking all non-trivial automorphisms of T (the colour of e is irrelevant). Consequently, D'(G) < 3 by Lemma 3.1.
If T is a bisymmetric tree Th'3 with the central edge xy, then we can add to T one edge in a subtree of T - xy rooted at x, and such a graph can be easily distinguished by two colours. Again, our claim follows from Lemma 3.1.	□
3.4 2-connected graphs
For a 2-connected planar graph G, the distinguishing index may attain 1 +
2
VAG)
as it
is shown by the complete bipartite graph K2q with q = r2 for a positive integer r. In this case, D'(K2q) = r + 1 as it follows from the result obtained independently by Fisher and Isaak [11] and by Imrich, Jerebic and KlavZar [14]. They proved the following theorem. Actually, they formulated it for the distinguishing number D(KpUKq) of the Cartesian product of complete graphs, but D'(Kp,q) = D(KpUKq).
Theorem 3.7 ([11, 14]). Let p, q, d be integers such that d > 2 and (d - 1)p < q < dp . Then
D'(K ) = / d if q < dp - [logd p\ - 1 D (Ap'q) = \ d + 1, if q > dp - \logd pl + 1.
If q = dp - \logdpl then the distinguishing index D'(Kpq) is either d or d +1 and can be computed recursively in O(log* (q)) time.
In the next section, we make use of the following immediate corollary.
Corollary 3.8. Ifp < q, then D'(Kpq) < + 1.
In the proof of Proposition 3.10 we also make use of an earlier result of Imrich and KlavZar [15] which is a slightly weaker version of Theorem 3.7 for d =2.
Theorem 3.9 ([15]). If 2 < p < q < 2p - p +1, then D'(KPq) = 2.
Proposition 3.10. If p < q < 2p - p +1 and p + q > 7, then there exists a distinguishing edge 2-colouring of Kp,q such that the edges in one of colours induce a connected spanning or almost spanning, asymmetric subgraph of Kp,q.
Proof. The assumptions imply that p > 3, and D'(Kp,q) = 2 by Theorem 3.9. Let P and Q be the two sets of bipartition of Kpq with |P| = p and |Q| = q. If p = q, then p > 4, and there exists a spanning asymmetric tree of Kpp (see [17]). If p < q < 2p - p +1, then for the proof of Theorem 3.9, Imrich and KlavZar in [15] constructed a distinguishing vertex 2-colouring of KpUKq that corresponds to a distinguishing edge 2-colouring f of Kpq, where a colouring of vertices in a Kq-layer can be represented by a sequence from {1, 2}q and it corresponds to a colouring of edges incident to a vertex in P (the same is true
M. Pilsniak: Improving upper bounds for the distinguishing index
271
for Kp-layers and vertices in Q). We wish to show that this colouring yields a connected asymmetric subgraph of Kp,q which is spanning or almost spanning.
First assume that q = 2p - p +1. In the coloring f, every vertex in P has distinct positive number of edges coloured with 1, and there exists a vertex v1 with all incident edges coloured with 1. Moreover, distinct vertices from Q have distinct sets of neighbours joined by edges coloured with 1, and there exists a vertex, say v2, with all incident edges coloured with 2. Let S be a subgraph induced by edges coloured with 1. Then S is an almost spanning subgraph since v2 is the only vertex outside S. The graph S is connected because vi is adjacent to every vertex in Q, and every vertex in P is joined to a vertex in Q by an edge coloured with 1. Moreover, S is also asymmetric since f breaks all non-trivial automorphisms of Kp q and any automorphism interchanging some parts of the sets P and Q does not preserve distances in S.
Following [15] for p < q < 2p - p + 1, we exclude a relevant number of such pairs of sequences of colours that the sum of them is a sequence (3,..., 3). Additionally, if both q and p are odd, we exclude the sequence (0,..., 0). Again, we obtain a connected spanning
(or almost spanning) asymmetric subgraph S of Kp q induced by the edges coloured with 1.
' □
Proposition 3.10 and Lemma 3.1 immediately imply the following.
Corollary 3.11. If a graph G of order at least 7 is spanned by Kp,q and p < q < 2p —p +1, then D'(G) < 2.
In general, for 2-connected graphs we conjecture that the complete bipartite graph K2,r2 is the worst case, i.e. attains the highest value of the distinguishing index.
Conjecture 3.12. If G is a 2-connected graph, then
D'(G) < 1 + [^A(G)" .
4 Nordhaus-Gaddum inequalities for D'
In this section, we discuss Conjecture 1.6, formulated at the end of Introduction, stating that
2 < D'(G) + D'(G) < A + 2
for every admissible graph G of order n > 7, where A = max{A(G), A(G)}.
The left-hand inequality is obvious. Indeed, if a graph G is asymmetric, then so is G. Thus we are only interested in the right-hand inequality D'(G) + D'(G) < A + 2. Note also that at least one of the graphs G and G is connected.
The bound A + 2 cannot be improved. To see this, consider a star K1n_1 of any order n > 7. As K1n_1 is a disjoint union of a complete graph Kn-1 and an isolated vertex, it follows from Proposition 2.3 that D/(K1i„_1) = 2. Therefore, D/(K1i„_1) + D'(K1,n_1) = n — 1 + 2 = A + 2.	'	_	'
If T is a tree, then A(T) can be much smaller than A = A(T) = n — 1. However, the following holds.
Proposition 4.1. If T is a tree of order n > 7, then
D'(T) + D'(T) < A(T)+2.
272
Ars Math. Contemp. 13 (2017) 293-306
Proof. As it was shown above, the conclusion holds for stars. If T is not a star, then D'(T) < 2 by Lemma 3.1. Indeed, as it was proved by Hedetniemi et al. in [13], a complete graph Kn contains edge disjoint copies of any two trees of order n distinct from a star K1in-1. Thus, the complement T contains a spanning asymmetric tree. By Theorem 2.6, we have the inequality D'(T) + D'(T) < A(T) + 2.	□
This fact emboldened us to formulate the following stronger conjecture.
Conjecture 4.2. Every connected admissible graph G of order n > 7 satisfies the inequality	_
D'(G) + D'(G) < A(G) +2.
Now we show that Conjecture 1.6 holds not only for trees, but also for some other classes of graphs. To do this we use the following fact.
Theorem 4.3. Let G be a connected admissible graph of order n > 7. If either G or every connected component of G has the distinguishing index at most 3, then
D'(G) + D'(G) < A+ 2,
where A = max{A(G), A(G)}.
Proof. Our claim is true for trees by Proposition 4.1. Observe also, that it is true if G is a path or a cycle of order at least 7 since its complement G is Hamiltonian, and D'(G) + D'(G) < 4. So, now we can assume that A(G) > 3 and neither G nor G is a tree. We consider two cases.
Case A. Every component H of G satisfies D'(H) < 3. Then D'(G) < A(G) — 1 by Theorem 2.8, and if G is connected, then our claim holds. Assume now that G is disconnected. Then G is spanned by Kp,q with p < q and A > q, where p + q = |V(G)|. Suppose that the graph G has t isomorphic components. If we had a distinct set of three colours for every component, then D'(G) < f$6]. We then consider two cases:
a)	If q < 2p — p +1, then D'(G) = 2 by Corollary 3.11. Moreover, we then have at most n components of G, so D' (G) < f -^^n]. And we can easily see that
f-2n] +2 < n + 2
for every n > 4.
b)	If q > 2p — p +1, then there exists a big component (of order q) in G and we can assume that t < | remaining components are isomorphic. In this case, by assumptions we havep < [log2(q + p — 1)], therefore
D'(G) < r■\/6i] < ^2 [log2 (q + p — 1)1.
On the other hand, D'(G) < f-j/q1 +2 by Corollary 3.8 and Theorem 3.1. Then it is not difficult to check that for q > 2p — p + 1
^2 flog2 (q + p — 1)1 + r -q 1 +2 < q + 2
what finishes the proof in Case A.
M. Pilsniak: Improving upper bounds for the distinguishing index
273
CaseB. D'(G) < 3.
If graph G is connected, then the claim follows immediately from Theorem 2.7 whenever D'(G) = 2 or D'(G) = 2, and it follows from Theorem 2.8 if D'(G) = 3. Assume now that G has t > 2 components. Then A > J and, in the worst case, all components of G are isomorphic. Observe that maximal degree of every component is at most J - 1. If we assign one extra colour to every component, then we need at most J - 1 + (t - 1) colours to distinguish G. Hence, if
n	n
- + t <--1,
t + < 2 ,
then D'(G) < A - 1, and our claim is true. The above inequality holds unless t = 2.
If there exist two isomorphic components in G, then D'(G) < 2 due to Corollary 3.11 since G is spanned by Kn, n .Then D'(G) < J, and finally D'(G) + D'(G) < J + 2. □
Now we can formulate some consequences of Theorem 4.3 and suitable results proved in Section 3.
Corollary 4.4. Let G be an admissible graph of order n > 7. If G satisfies at least one of the following conditions:
i)	G	is a	traceable graph, or
ii)	G	is a	claw-free graph, or
iii)	G	is a	triangle-free graph, or
iv)	G	is a	3-connected planar graph
then			
D'(G) + D'(G) < A+ 2, where A = max{A(G), A(G)}.
Proof. It suffices to apply Theorem 4.3 together with Theorem 3.2, Theorem 3.4 and Theorem 3.6, respectively. Observe also that if the girth of a graph G is at least 4, i.e., G is triangle-free, then its complement G is claw-free.	□
Finally, it has to be noted that there exist graphs of order less than 7 such that the right-hand inequality in Conjecture 1.6 is not satisfied. For example, for the graph K3,3 we have D'(K3,3) = 3, D'(K33) =_D'(2Ks) =4 and A = 3, hence D'(K3<3) + d''(K33) = A + 4. Also, D'(C5) + D'(C5) = 3 + 3 = A + 4, and D'(Klji) + D'(Kl}i) = A + 3 for i = 3,4, 5.
References
[1]	M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Com-bin. 3 (1996), #R18, http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v3i1r18.
[2]	M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013), 466-546, doi:10.1016/j.dam.2011.12.018.
[3]	D. W. Barnette, Trees in polyhedral graphs, Canad. J. Math. 18 (1966), 731-736, doi:10.4153/ cjm-1966-073-4.
274
Ars Math. Contemp. 13 (2017) 293-306
[4]	D. L. Boutin, The cost of 2-distinguishing Cartesian powers, Electron. J. Com-bin. 20 (2013), #P74, http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v2 0i1p7 4.
[5]	J. O. Choi, S. G. Hartke and H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, SIAM J. Discrete Math. 24 (2010), 82-100, doi:10.1137/060651392.
[6]	K. L. Collins, M. Hovey and A. N. Trenk, Bounds on the distinguishing chromatic number, Electron. J. Combin. 16 (2009), #R88, http://www.combinatorics.org/ojs/ index.php/eljc/article/view/v16i1r8 8.
[7]	K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Com-bin. 13 (2006), #R16, http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v13i1r16.
[8]	K. L. Collins and A. N. Trenk, Nordhaus-Gaddum theorem for the distinguishing chromatic number, Electron. J. Combin. 20 (2013), #P46, http://www.combinatorics.org/ ojs/index.php/eljc/article/view/v2 0i3p4 6.
[9]	E. Estaji, W. Imrich, R. Kalinowski, M. PilSniak and T. W. Tucker, Distinguishing Cartesian products of countable graphs, Discuss. Math. Graph Theory 37 (2017), 155-164, doi:10.7151/ dmgt.1902.
[10]	R. Faudree, E. Flandrin and Z. Ryjacek, Claw-free graphs — a survey, Discrete Math. 164 (1997), 87-147, doi:10.1016/s0012-365x(96)00045-3.
[11]	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.
[12]	R. Hammack, W. Imrich and S. KlavZar, Handbook of Product Graphs, Discrete Mathematics and Its Applications, CRC Press, Boca Raton, Florida, 2nd edition, 2011, doi:10.1201/b10959.
[13]	S. M. Hedetniemi, S. T. Hedetniemi and P. J. Slater, A note on packing two trees into Kn, Ars Combin. 11 (1981), 149-153.
[14]	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.
[15]	W. Imrich and S. KlavZar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006), 250-260, doi:10.1002/jgt.20190.
[16]	W. Imrich, S. M. Smith, T. W. Tucker and M. E. Watkins, Infinite motion and 2-distinguishability of graphs and groups, J. Algebraic Combin. 41 (2015), 109-122, doi: 10.1007/s10801-014-0529-2.
[17]	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.
[18]	E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175-177, doi:10.2307/2306658.
[19]	W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99-116, doi: 10.2307/1992980.
[20]	V. G. Vizing, The chromatic class of a multigraph, Kibernetika 1 (1965), 29-39, doi:10.1007/ bf01885700.
[21]	S. Win, On a connection between the existence of k-trees and the toughness of a graph, Graphs Combin. 5 (1989), 201-205, doi:10.1007/bf01788671.
[22]	A. A. Zykov, On some properties of linear complexes, Mat. Sbornik(N. S.) 24 (1949), 163-188, http://mi.mathnet.ru/eng/msb5974.