ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 18 (2020) 117-126 https://doi.org/10.26493/1855-3974.1852.4f7 (Also available at http://amc-journal.eu) The distinguishing index of connected graphs without pendant edges* Wilfried Imrich © Montanuniversität Leoben, Franz Josef-Str. 18, 8700 Leoben, Austria Rafal Kalinowski , Monika Pilsniak , Mariusz Wozniak © AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland Received 13 November 2018, accepted 19 December 2019, published online 24 September 2020 We consider edge colourings, not necessarily proper. The distinguishing index D'(G) of a graph G is the least number of colours in an edge colouring that is preserved only by the identity automorphism. It is known that D'(G) < A for every countable, connected graph G with finite maximum degree A except for three small cycles. We prove that D'(G) < |"\/A] + 1 if additionally G does not have pendant edges. Keywords: Symmetry breaking, distinguishing index of a graph. Math. Subj. Class. (2020): 05C15, 05E18 1 Introduction and main result We use standard graph theory terminology and notation [3]. In particular, the circumference of a graph G, denoted by c( G), is the length of a longest cycle of G. A graph that contains a Hamiltonian path, i.e. a path that visits each vertex of the graph, is called traceable. A finite tree is called symmetric (respectively, bisymmetric) if it contains a central vertex v0 (resp. a central edge e0), all leaves are at the same distance from v0 (resp. e0) and all vertices that are not leaves have the same degree. An infinite path is an infinite connected 2-regular graph. We consider edge colourings, not necessarily proper. Such a colouring breaks an automorphism ( € Aut(G) if there exists an edge that is mapped into an edge with a different *The research was partially supported by OEAD grant no. PL 08/2017. E-mail addresses: imrich@unileoben.ac.at (Wilfried Imrich), kalinows@agh.edu.pl (Rafal Kalinowski), pilsniak@agh.edu.pl (Monika Pilsniak), mwozniak@agh.edu.pl (Mariusz Wozniak) Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 106 Ars Math. Contemp. 18 (2020) 105-115 colour. A colouring is called distinguishing, if it breaks all non-trivial automorphisms. The minimum number of colours in a distinguishing colouring of a graph G is called the distinguishing index of G and is denoted by D'(G). Obviously, the distinguishing index is defined only for graphs without K2 as a component and with at most one isolated vertex. In this paper, we exclusively consider connected graphs, hence in the sequel, we assume that each graph in question is of order at least 3. The following general upper bound for the distinguishing index of finite connected graphs was proved in [5]. Theorem 1.1 ([5]). If G is a finite, connected graph of order n > 3, then D'(G) < A(G) unless G is C3, C4 or C5. This result was improved by the third author who characterized all connected graphs with the distinguishing index equal to the maximum degree. Theorem 1.2 ([9]). Let G be a finite, connected graph of order n > 3. Then D'(G) < A(G) - 1 unless G is a cycle, a symmetric or a bisymmetric tree, K4 or K3,3. For infinite graphs, a sharp upper bound was proved by Pilsniak and Stawiski in [10]. Theorem 1.3 ([10]). Let G be a connected, infinite graph with finite maximum degree A(G). Then D'(G) < A(G) - 1 unless G is an infinite path with D'(P^) = A(P^) = 2. However, D'(G) < 2 if G belongs to some classes of graphs, e.g. G is a traceable graph of order at least 7 ([ ]), G is any Cartesian power of a graph unless G = Kf ([ ]), or G is a countable graph every non-identity automorphism of which moves infinitely many vertices ([6]). Pilsniak [9] formulated the following conjecture. Conjecture 1.4 ([9]). If G is a 2-connected graph, then D'(G) < [VAMj +1- We prove this conjecture in a bit stronger form. Theorem 1.5 (Main result). If G is a connected, countable graph with minimum degree 5(G) > 2, then D'(G) < vAG) + 1- In view of Theorem 1.3, the claim obviously holds for countable graphs with infinite A(G). Hence, from now on, we assume that the maximum degree of any graph G in question is finite. W. Imrich et al.: The distinguishing index of connected graphs without pendant edges 121 This result is tight for complete bipartite graphs K2,r2 since D'(K2,r2) = r +1 for any integer r > 2. Indeed, there are r2 internally disjoint paths of length two between the two vertices u, v of maximum degree in K2r2, and they have to be coloured with distinct ordered pairs of colours. With r colours, we have r2 distinct pairs, but if all of them are used, we can transpose u and v and permute the other vertices to obtain an automorphism preserving this colouring. There are also some small graphs G with D'(G) = A(G)] + 1, e.g. Kn, Cn for n G {3,4,5}, and K3,3. We conjecture that the only connected graphs of order at least seven satisfying this equality are complete bipartite graphs K2 r2. The proof of the Main result for 2-connected graphs is given in Section 2 (Theorem 2.2). In Section 3, we prove it for graphs of connectivity 1 (Theorem 3.5). We believe that the following much stronger claim is true1. Conjecture 1.6. If G is a connected, countable graph with finite minimum degree S > 2, then D'(G) < ^A(G) + 1. Moreover, for graphs of order at least seven, the equality holds if and only if G = KSrs, for some positive integer r. If true, this would imply that D'(G) < 2 for every regular graph G of order at least seven. Observe that for vertex-transitive graphs this result would be also implied by the famous Lovasz Conjecture [8] that every vertex-transitive graph is traceable since, as it was already mentioned, D'(G) < 2 for every traceable graph of order at least 7. Let us add that recently Lehner, Pilsniak and Stawiski [7] proved that D'(G) < 3 for every connected, regular graph G, finite or infinite. 2 2-connected graphs In the proof of the Main result, we colour the edges of a graph G with colours from the set Z = {0,1,..., \%/A]}. Observe that we always have at least three colours at our disposal. Given a vertex a of a graph H, by Aut(H)a we denote the stabilizer of a vertex a, i.e. Aut(H)a = {( G Aut(H) : f(a) = a}. For two vertices a, b, we denote Aut(H)a,b = Aut(H)a n Aut(H)b. In this section, we prove the Main result for 2-connected, countable graphs. The following lemma plays a key role in the proof. Lemma 2.1. Let a, b be two vertices of a graph H of finite maximum degree at most A, such that dist(a, v) + dist(v, b) = dist (a, b) for every vertex v G V(H). Then H admits an edge colouring with ^VA] colours breaking every automorphism of Aut(H)a,b. Proof. For r G {0,1,..., dist(a, b)}, let Sr(a) = {v G V(H) : dist(a, v) = r} 1 Actually, this conjecture was earlier posed by Pilsniak and WoZniak, and the first part of it was independently formulated by Alikhani and Soltani in [1]. The latter authors claimed a proof therein but we found two errors and a few gaps that we cannot fix. 106 Ars Math. Contemp. 18 (2020) 105-115 be the r-th sphere centered at the vertex a. Thus, for r < dist(a, b), every vertex v G Sr (a) has at least one and at most A - 1 neighbours in Sr+i(a). For r > 1, denote Hr = H [S0(a) U • • • U Sr(a)]. We recursively colour the edges between Sr(a) and Sr+1(a) with [%/A] colours such that for each r the following two conditions are satisfied: (1) Sr (a) is fixed pointwise by every automorphism ^ G Aut(H)a,b preserving the colouring of Hr+1, whenever Sr+1(a) is fixed so; (2) if A C Sr+1(a) is a set of vertices such that there exists a cyclic permutation of A that can be extended to an automorphism ^ g Aut(H)a Sr+ i(a) Figure 1: (Colouring of edges between subsequent spheres centered at the vertex a breaking all automorphisms of Autaib(ii). First we partition the set of edges incident to a into at most [%/A] subsets of cardinality at most [%/A], and we colour edges in each subset with the same colour. Suppose that we have already defined an edge colouring f of Hr satisfying the above two conditions for r - 1 instead of r. Let A = {v1;..., vp}, with p > 2, be a set of vertices of Sr (a) such that there exists a cyclic permutation of A that can be extended to an automorphism ^ G Aut(H)a ([vA] - 1)[vA], then we put aj = k - ([VA] - 1)[VA], and aj = [VA] for W. Imrich et al.: The distinguishing index of connected graphs without pendant edges 121 j e Z \ {0, i}. Otherwise, [VA +1 < k < ( [VA - 1) [VA. If this case, a» = 0, and for j = i we put aj > 0 such that |aj - pyj]^ I < 1. Thus, a» = aj for j = i, whence the vertices of A are distinguished. Moreover, this way we produce at most [\/Al vertices in Sr+1(a) that can be interchanged by an automorphism preserving the colouring of Hr+1 because at most [\/Al edges joining any vertex of A to Sr+1(a) have the same colour. The second last sphere Sr (a), i.e. for r = dist(a, b) -1, has at most A vertices and, due to our construction, any of its subsets A that can be permuted, has at most [\/Al vertices. We colour the edges between b and the vertices of A with distinct colours. The unique vertex b of the last sphere is fixed by assumption, hence all spheres are fixed pointwise with respect to any automorphism ^ e Aut(H)a,b preserving the edge colouring f of H. Finally, we colour edges within each sphere with an arbitrary colour. □ Given a cycle C of a 2-connected graph G = C4 and two distinct colours a, ,0 e Z \ {0}, by Co (a, ,0) we denote this cycle coloured such that three consecutive edges are coloured with a, 0, ft in that order, and all other edges of the cycle are coloured with 0. Exceptionally, in case G = C4, by a colouring C0(a, ,0) of C4 we mean the colouring a, ,0, 0,0 of its consecutive edges. Theorem 2.2. If G is a 2-connected, countable graph with finite maximum degree A, then D'(G) < VA + 1. Proof. If the circumference of G equals 3, then G = C3 and the claim holds. Figure 2: For a given n > 5, there are exactly two non-isomorphic graphs of order n and circumference 4 (the dashed edge may exist or not). Let c(G) = 4. If G e {C4,K4,K4 - e}, then D'(G) < 3, and the claim is true. Suppose |V(G)| > 5. Then either G = K2ja or G = K2ia-1 + e, where e is an edge between the two vertices of maximum degree A > 3 (see Figure 2). Indeed, let V(G) = {u1,..., un} with n > 5, and suppose that u1, u2, «3, u4 are consecutive vertices of a cycle C of length 4. As G is 2-connected and c(G) = 4, all other vertices «5,..., un have to be adjacent to the same pair of non-consecutive vertices of C, say u1;u3. Thus, we get a complete bipartite graph K2 n-2. The only possible additional edge not violating the condition c(G) = 4, is e = u1u3. As it was mentioned in the Introduction, in such a graph G e {K2,a, K2,a-1 + e}, we have enough colours for a distinguishing colouring of G. It is also easy to see that we can require that colour 0 appears only in one cycle of length four, coloured as C0(a, Suppose then that G has a cycle C of length at least 5. We colour it as C0(a, for some distinct a, ^ e Z \ {0}. Moreover, we colour all chords of C with a. We can require 106 Ars Math. Contemp. 18 (2020) 105-115 that the colour 0 appears only in this cycle C. Thus each vertex of C is fixed by every automorphism of G preserving the colouring. To see this it is enough to observe that both endpoints of the unique edge coloured with fi are fixed. We define a colouring of the remaining edges of G recursively, as follows. Suppose that we have already coloured the edges of an induced 2-connected subgraph F of G such that the only automorphism of G preserving this colouring is the identity, regardless of a colouring of the edges outside F. Thus F = G[V(C)] in the initial step. If F = G, then we choose a shortest path P between any two vertices of F containing at least one vertex outside F. Let a, b be the end-vertices of P, and let p be the length of P. As P is shortest possible, each path of length p between a and b in G is either uncoloured or fully coloured. Consider the subgraph H induced by the vertices of P and of all uncoloured paths between a and b of length p. Thus, all edges of H are uncoloured yet. We colour the edges of H with [a/AI colours according to Lemma 2.1. Let F' = G[V(F) U V(H)]. We thus obtained a colouring of all edges of F' that breaks every non-trivial automorphism of G, because the colouring of F already break them. If F' = G, the we repeat this procedure with F' instead of F until all edges of G are coloured. □ Actually, we have proved the following result which we use in the next section. Corollary 2.3. Let G be a 2-connected, countable graph with finite maximum degree A and let C be a longest cycle or any cycle of length at least five in G. Then for every two distinct colours a, fi G Z \ {0}, any colouring Co (a, fi) of its edges can be extended to a distinguishing colouring of G with colours from the set Z such that all edges coloured with 0 belong to the cycle C. Proof. The claim follows directly from the proof of Theorem 2.2 unless |G| = 4. In the latter case, Z = {0,1,2}, and G contains a cycle C4, which we colour as C0(1,2) (recall that this means a colouring a, fi, 0,0 of consecutive edges if G = C4, and a, 0, fi, 0 otherwise). This is clearly a distinguishing colouring of G = C4. If G = K4, then the other two edges get distinct colours 1,2. Otherwise, G = K4 - e, and the chord of C4 gets colour 1. □ 3 Graphs of connectivity 1 Observe that it follows from Theorem 1.2 and Theorem 1.3 that Theorem 1.5 is true for graphs of maximum degree A < 5 satisfying the conditions of the Theorem. This fact did not matter in the proof for 2-connected graphs, but it facilitates a bit our proof for graphs with cut vertices. From now on, assume that G is a countable graph of finite maximum degree A > 6 and connectivity 1. Hence, we have at least four colours 0,1, 2, 3 at our disposal. Two edge colourings f 1, f2 of a graph H are called isomorphic with respect to a group r C Aut(H) if there exists an automorphism ^ G r such that fi(uv) = f2(y(w)<^(v)) for every edge uv G E(H). Furthermore, f1, f2 are called isomorphic if they are isomorphic with respect to Aut(H). Lemma 3.1. Let u0 be a vertex of a 2-connected, countable block H0 of finite maximum degree at most A, where A > 6. Then H0 admits at least [%/A~| edge colourings with colours from the set Z, breaking all non-trivial automorphisms of Aut(H0)„0, which are pairwise non-isomorphic with respect to Aut(H0)u0, and do not contain C0(1, 2). W. Imrich et al.: The distinguishing index of connected graphs without pendant edges 121 Proof. First observe that if H0 is a 2-connected, countable graph and c(H0) > 5, then every vertex of H0 belongs to a cycle of length at least five. This easily follows from the fact that every vertex outside a given cycle C of length at least five is the origin of two internally disjoint paths to two vertices of C, which partition the cycle C into two paths, one of which is of length at least three. We choose a longest cycle C in B passing through the vertex u0 if B is finite, or a cycle of length at least five if B is infinite. It is easy to see that C is a longest cycle in G whenever |C| < 4. We colour C as Co(a,P), for {a,P} = {1, 2}. By Corollary 2.3, regardless of location of colours a and P on C, this colouring can be extended to a distinguishing colouring of H0 using colours from Z \ {0}. We have (^^^) -1 choices for the set of two colours {a, P} = {1, 2}. For a given colouring C0(a, P), there are at least three possible placements for u0 (actually, there are more possibilities if |H0| > 3). Hence, there are at least L = 3((^^1) - 1) edge colourings of H0 that are pairwise non-isomorphic with respect to Aut(Ho)„0. The inequality L > [a/A] , equivalent to 3( [a/A] )2 -5 [a/A] -6 > 0, holds whenever [a/A] ) > 3. □ Lemma 3.2. Let H0 be a graph of finite maximum degree at most A, with A > 6, consisting of s > 2 copies of a 2-connected block B sharing a common cut vertex u0. Then H0 admits at least [a/A| pairwise non-isomorphic distinguishing edge colourings with colours from the set Z, such that C0(1,2) does not appear in any of these colourings. Proof. Let H0 be a graph satisfying the assumptions. Observe that Aut(H0) = Aut(H0)„0 for s > 2. Clearly, s < [f J. As we have shown above, the block B admits at least L = 3((^^1) - 1) colourings which are pairwise non-isomorphic with respect )o Aut(H0)„0. To colour the graph H0, we select s of them. Hence, we have at least (L) pairwise non-isomorphic colourings of Ho. Clearly, (L) > L, when 1 < s < [f J < L -1, which is the case for A > 6. We know that L > [a/A], hence there are at least [a/A] non-isomorphic distinguishing colourings of Ho. □ Lemma 3.3. Let H0 be a graph satisfying the assumptions of Lemma 3.1 or of Lemma 3.2. Let T be a symmetric tree of order at least 3 with a central vertex v0. A graph H is obtained by attaching a copy of the graph H0 to every leaf of T in such a way that each pendant edge of T is incident to the same vertex u0 of H0. If the maximum degree of H is at most A and A > 6, then there exists a distinguishing colouring of H with colours from the set Z, and without C0(1,2). Proof. We colour the edges of T with [%/A] colours similarly as in the proof of Lemma 2.1. That is, at most [%/A] edges incident to the central vertex v0 of T get the same colour. Then recursively, at each level of T, any set A of vertices that can be cyclically permuted by an automorphism of H preserving the hitherto defined colouring, has at most [a/A] elements. For each vertex v of A, we choose a distinct colour i e Z such that the number of edges joining v to the next level of T and coloured with i, is different from the number of such edges coloured with any other colour. We arrive at the leaves of T with a colouring such that every set A of leaves that can be cyclically permuted by an automorphism of T preserving the colouring of T has at most [a/A] elements. It follows from Lemma 3.1 or Lemma 3.2 (depending on the structure of H0) that each copy of H0 attached at a leaf 106 Ars Math. Contemp. 18 (2020) 105-115 Figure 3: Example of a 4-colouring of a graph H of Lemma 3.3 with A = 9, where a graph H0 consisting of four triangles sharing a cut vertex u0 is attached to every leaf of a tree T = Ki,9. belonging to the same set A has a distinct colouring satisfying our assumptions. Thus we obtain a desired colouring of the whole graph H. □ The following result of Broere and Pilsniak [2] will be useful in the next proof. Theorem 3.4 ([2]). If T is an infinite tree without leaves, then D'(T) < 2. We are now ready to prove Theorem 1.5 for graphs with cut vertices. Theorem 3.5. Let G be a countable graph of connectivity 1 and without pendant edges. If G has finite maximum degree A, then D'(G) < Va' + 1. Proof. Recall that we may assume that A > 6, whence the set Z contains at least four colours. If G is a tree, then it has no leaves, so D'(G) < 2 by Theorem 3.4. Suppose then that G contains a 2-connected block B0. Let C be a longest cycle of B0, if it exists, or any cycle of length at least five of B0. Colour it with C0(1, 2). By Corollary 2.3, there is a distinguishing edge colouring of B0, where colour 0 is used only on the cycle C. In our colouring of the whole graph G, we ensure that C0(1,2) does not appear again, therefore each vertex of Bo is fixed by every automorphism of G preserving the colouring of B0. We recursively extend this colouring in such a way that every vertex with at least one coloured incident edge is fixed as well. Now, we set any ordering v1; v2,... of all cut vertices of G. We recursively consider the first vertex vj in this ordering that belongs to an already coloured block, as well as to an uncoloured one. Hence, vj is already fixed by every p e Aut(G) preserving the existing partial colouring. We proceed with vj in four stages. W. Imrich et al.: The distinguishing index of connected graphs without pendant edges 121 1. Let Bl,...,Bl be pairwise non-isomorphic, uncoloured 2-connected blocks containing vi. For each j e {1,...,/}, we consider a maximal subgraph H0 of G that consists of s > 1 copies of Bj sharing the cut vertex vi. Taking u0 = vi, by Lemma 3.1 if s = 1, or by Lemma 3.2 if s > 2, there is a distinguishing colouring of H0 with colours from the set Z, not containing C0(1,2). 2. We consider every uncoloured maximal subgraph H satisfying the assumptions of Lemma 3.3. We colour H distinguishingly according to the conclusion of Lemma 3.3. Consequently, all 2-connected blocks containing vi are now coloured. 3. If some components of G - vi are uncoloured infinite trees, then we consider the infinite tree T containing all those components and the vertex vi, and we colour the edges of T with two colours, by Theorem 3.4. 4. We colour every yet uncoloured edge e incident to vi arbitrarily. Note that both endpoints of e are already fixed by any ^ e Aut(G) preserving the existing partial colouring, because uncoloured components of G - vi are pairwise non-isomorphic. This recursive procedure yields a distinguishing colouring of G with [\/A] + 1 colours, which completes the proof of Theorem 3.5, and thus of Theorem 1.5. □ ORCID iDs Wilfried Imrich E> https://orcid.org/0000-0002-0475-9335 Rafal Kalinowski 0 https://orcid.org/0000-0002-3021-7433 Monika PilSniak © https://orcid.org/0000-0002-3734-7230 Mariusz Wozniak E> https://orcid.org/0000-0003-4769-0056 References [1] S. Alikhani and S. Soltani, Relationship between the distinguishing index, minimum degree and maximum degree of graphs, arXiv:1705.05758 [math.CO]. [2] I. Broere and M. PilSniak, The distinguishing index of infinite graphs, Electron. J. Combin. 22 (2015), #P1.78 (10 pages), doi:10.37236/3933. [3] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer, Berlin, 5th edition, 2018. [4] A. Gorzkowska, R. Kalinowski and M. PilSniak, The distinguishing index of the Cartesian product of finite graphs, Ars Math. Contemp. 12 (2017), 77-87, doi:10.26493/1855-3974.909. 0e1. [5] 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. [6] F. Lehner, Breaking graph symmetries by edge colourings, J. Comb. Theory Ser. B 127 (2017), 205-214, doi:10.1016/j.jctb.2017.06.001. [7] F. Lehner, M. PilSniak and M. Stawiski, A bound for the distinguishing index of regular graphs, European J. Combin. 89 (2020), 103145 (9 pages), doi:10.1016/j.ejc.2020.103145. [8] L. LovaSsz, Problem 11, in: Combinatorial Structures and Their Applications, Gordon and Breach, New York-London-Paris, 1970, proceedings of the Calgary International Conference on Combinatorial Structures and their Applications held at the University of Calgary, Calgary, Alberta, Canada, June. 106 Ars Math. Contemp. 18 (2020) 105-115 [9] M. PilSniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13 (2017), 259-274, doi:10.26493/1855-3974.981.ff0. [10] M. Pilsniak and M. Stawiski, The optimal general upper bound for the distinguishing index of infinite graphs, J. Graph Theory 93 (2020), 463-469, doi:10.1002/jgt.22496.