ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 173-187
https://doi.org/10.26493/1855-3974.1849.148
(Also available at http://amc-journal.eu)
Distinguishing numbers of finite 4-valent vertex-transitive graphs*
*
Florian Lehner t ©
Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
Gabriel Verret * ©
Department of Mathematics, The University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
Received 8 November 2018, accepted 25 February 2020, published online 13 November 2020
The distinguishing number of a graph G is the smallest k such that G admits a k-colouring for which the only colour-preserving automorphism of G is the identity. We determine the distinguishing number of finite 4-valent vertex-transitive graphs. We show that, apart from one infinite family and finitely many examples, they all have distinguishing number 2.
Keywords: Vertex colouring, symmetry breaking in graph, distinguishing number, vertex-transitive graphs.
Math. Subj. Class. (2020): 05C15, 05E18
1 Introduction
All graphs in this paper will be finite. A distinguishing colouring of a graph is a colouring which is not preserved by any non-identity automorphism. The distinguishing number D(G) of a graph G is the least number of colours needed for a distinguishing colouring of the vertices of G. These concepts were first introduced by Albertson and Collins [1] and have since received considerable attention.
*	We would like to thank the anonymous referees for a number of helpful suggestions. t Supported by the Austrian Science Fund (FWF), grant J 3850-N32.
*	Gabriel Verret is grateful to the N.Z. Marsden Fund for its support (via grant UOA1824).
E-mail addresses: mail@florian-lehner.net (Florian Lehner), g.verret@auckland.ac.nz (Gabriel Verret)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
22
Ars Math. Contemp. 19 (2020) 189-208
It is an easy observation that a graph has distinguishing number 1 if and only if its automorphism group is trivial. Hence, by [6] almost all graphs have distinguishing number 1. This obviously is not true for non-trivial vertex-transitive graphs which always have non-trivial automorphisms. However, it seems that the vast majority of vertex-transitive graphs still have the lowest possible distinguishing number, namely 2. Hence let us call a vertex-transitive graph exceptional if its distinguishing number is not equal to 2.
One of the most interesting results concerning distinguishing numbers of vertex-transitive graphs is that, apart from the complete and edgeless graphs, there are only finitely many exceptional vertex-primitive graphs [3, 14]. It is only natural to ask whether something similar holds for vertex-transitive graphs as well. As a first step, Huning et al. recently determined the exceptional 3-valent vertex-transitive graphs and their distinguishing numbers.
Theorem 1.1 ([7, Corollary 2.2]). The exceptional connected 3-valent vertex-transitive graphs are
1.	K4 and K3,3, with distinguishing number 4, and
2.	Q3 = K4 x K2 and the Petersen graph, with distinguishing number 3.
This result shows that there are only finitely many connected 3-valent vertex-transitive exceptional graphs. This is not true for 4-valent graphs, as shown by the following family of graphs. For n > 3, the wreath graph Wn is the lexicographic product Cn [2Ki] of a cycle of length n with an edgeless graph of order 2, see Figure 1.
Figure 1: The wreath graph W10.
It is easy to see that wreath graphs form an infinite family of connected exceptional 4-valent vertex-transitive graphs, thus providing a negative answer to [7, Question 2]. Our main result shows that this is the only such family, that is, apart from the wreath graphs, there are only finitely many connected exceptional 4-valent vertex-transitive graphs.
Theorem 1.2. The exceptional connected 4-valent vertex-transitive graphs are
1.	K5 and K4,4 = W4, with distinguishing number 5, and
2.	K3 □ K3, K4 □ K2, K5 x K2 and Wn for some n > 3, n = 4, with distinguishing number 3.
In particular, there is no example with distinguishing number 4. This leads us to the following question.
F. Lehner and G. Verret: Distinguishing numbers of finite 4-valent vertex-transitive graphs 175
Question 1.3. For A > 5, is there a connected A-valent vertex-transitive graph G with
D(G) = A?
More generally, one could ask about "gaps" in the set of distinguishing numbers of connected A-valent vertex-transitive graphs, as a subset of {2,..., A + 1}.
Using lexicographic products, it is not hard to construct infinite families of connected exceptional vertex-transitive graphs with fixed valency.
Example 1.4. Let Hi be a connected vertex-transitive graph of valency Ai and let H2 be a vertex-transitive graph of valency A2 on n2 vertices. Then the lexicographic product Hi[H2] is connected, has valency Ain2 + A2 and its distinguishing number is at least D(H2) + 1. For an infinite family of examples that are not lexicographic products, note that, for every n > 3 and every d > 2, the graph (Cn[d2Ki]) □ K2 has valency 2d2 + 1 and distinguishing number strictly greater than d.
We hence pose the following (informal) problem.
Problem 1.5. Is there a "natural small family" F of exceptional graphs such that, for every positive integer k, all but finitely many k-valent connected exceptional vertex-transitive graphs are contained in F ?
2 Definitions and auxiliary results
Throughout this paper, all graphs are assumed to be finite and simple. Graph theoretic notions that are not explicitly defined will be taken from [5].
An automorphism of a graph is an adjacency preserving permutation of its vertices. The group of all automorphisms of a graph G is denoted by Aut G. We say that a graph is vertex-transitive if its automorphism group is transitive (that is, for every pair of vertices, there exists an automorphism mapping the first to the second).
An arc in a graph G is an ordered pair of adjacent vertices, or equivalently, a walk of length 1 in G. An s-arc is a non-backtracking walk of length s in G, i.e. a sequence of vertices v0,... ,vs where vi is adjacent to vi+i for 0 < i < s - 1, and vi-i = Vi+i for 1 < i < s - 1. The automorphism group Aut G acts on the set of edges, arcs, and s-arcs of G in an obvious way. Call a graph edge-transitive, arc-transitive, or s-arc-transitive, if the action of Aut G on edges, arcs, or s-arcs is transitive, respectively. Analogously define arc-regular and s-arc-regular.
The local group at a vertex v is the permutation group induced by the stabiliser of v acting on its neighbourhood N(v). Note that, for vertex-transitive graphs, this does not depend on the choice of v (up to permutation equivalence). We say that a graph is locally r, if the local group is isomorphic to r.
A graph G is called k-connected if it remains connected after removing any set of at most k - 1 vertices and all incident edges, and k-edge connected if it remains connected after removing any set of k edges. The following result about the connectivity of vertex-transitive graphs is due to Watkins [16].
Lemma 2.1. A vertex-transitive graph with valency r is at least 2r -connected.
If we impose additional properties on the set of vertices to be removed, then we can remove much larger sets without disconnecting the graph. The following lemma follows easily from results in [15].
24
Ars Math. Contemp. 19 (2020) 189-208
Lemma 2.2. If G is a k-valent vertex-transitive graph with k > 4 and girth g > 5, then there is a g-cycle C in G such that G — C is 2-edge connected.
Proof. By [15, Theorem 4.5], there is a g-cycle C such that the edges with one endpoint in C and the other endpoint in H := G — C form a minimum (w.r.t. cardinality) cut separating two cycles in G. Assume that H was not 2-edge connected and let e be a cut-edge of H. Let A and B be the two components of H — e. By [15, Lemma 3.3], the minimum degree of H is 2, so A and B each contain at most one vertex of degree 1, and thus there are cycles in both components. Now either the cut separating A U C from B, or the cut separating B U C from A contains strictly fewer edges than the cut separating C from H, contradicting the minimality.	□
We will also need the notion of distinguishing index D'(G) of a graph G, which is the least number of colours needed for a distinguishing colouring of the edges of G. Here are a few results giving upper bounds on D'(G). The first two are Theorems 2.8 and 3.2 in [11].
Theorem 2.3. Let G be a connected graph that is neither a symmetric nor a bisymmetric tree. If the maximum degree A(G) of G is at least 3, then D'(G) < A(G) — 1 unless G is K4 or K3 3.
Theorem 2.4. If G is a graph of order at least 7 with a Hamiltonian path, then D' (G) < 2.
Lemma 2.5. If G is a connected graph on 5 or more vertices, then AutL(G) is permu-tationally equivalent to Aut G with its natural action on E(G). Furthermore, in this case D'(G) < D(G), unless G is a tree.
Proof. The first part is a variant of Whitney's theorem due to Jung [8], the second part
follows by applying [10, Theorem 1.3] to a distinguishing colouring with D(G) colours.
□
In the remainder of this section, we discuss some known results on distinguishing numbers and determine the distinguishing numbers of several graphs that will occur in the proof of Theorem 1.2. The following lemma gives a general bound on distinguishing numbers and was independently proved in [4] and [9].
Lemma 2.6. If G is a connected graph with maximum degree A, then D(G) < A + 1, with equality if and only if G is either C5, or Kn or Kn,n for some n > 1.
For n > 2, we define a family of graphs Cn,K33 as follows. For 1 < i < n, let Hi be disjoint copies of K3,3 with bipartition V(Hi) = Xi uYj. Let Cn,K33 be the graph obtained from this collection by adding a matching between Xi and Yi+1 for 1 < i < n — 1, and between Xn and Yi, see Figure 2.
Lemma 2.7. The following graphs have distinguishing number at most 2:
(1)	The line graph of every non-exceptional 3-valent graph;
(2)	The line graphs of the following graphs: the Petersen graph, Q3, K3 □ K3, K5 x K2, and Wn for every n > 3;
(3)	The bipartite complement of the Heawood graph;
(4)	The 4-dimensional hypercube Q4;
F. Lehner and G. Verret: Distinguishing numbers of finite 4-valent vertex-transitive graphs 175
(5)	The (4,6)-cage, and
(6)	The graph Cn K3 3 for n > 2.
Figure 2: Distinguishing colouring of C6 K3 3.
Proof. Lemma 2.5 immediately implies (1).
For (2), it suffices to observe that all the base graphs have at least 7 vertices and a Hamiltonian path, and then apply Theorem 2.4 and Lemma 2.5 .
For (3) note that the bipartite complement of the Heawood graph has the same automorphism group as the Heawood graph and thus also the same distinguishing number. By Theorem 1.1, this distinguishing number is 2.
(4) follows from [2], where distinguishing numbers of all hypercubes were determined. For the proof of (5) first note that the (4, 6)-cage is bipartite and any two vertices in each of its parts have exactly one neighbour in common. Let v be any vertex, let Vj for 1 < i < 4 be the neighbours of v, and let Vj 1 < i < 3 be the neighbours of Vj.
Colour v white, for 1 < i < 4 colour Vj black, and colour Vj black if i < j and white otherwise. Finally colour the common neighbours of v22 and v32, and v22 and v33 black and all other vertices at distance 3 from v white, see Figure 3.
v
Figure 3: Colouring of the (4, 6)-cage, all vertices at distance 3 from v not shown in the picture are coloured white.
Let y be a colour preserving automorphism. Then 7 must fix v, since it is the only white vertex with 4 black neighbours. Furthermore 7 must fix all neighbours of v since they have a different number of black neighbours. It must also fix the two black vertices at distance
26
Ars Math. Contemp. 19 (2020) 189-208
3 from v for the same reason. Now it is easy to see that y has to fix all vertices at distance
2	from v and hence it is the identity.
For (6), consider the colouring shown in Figure 2. Note that the automorphism group has two orbits on edges: those that belong to a copy of K3 3, and those that don't, which we call matching edges. There is a unique matching edge both of whose endpoints are coloured white. Every colour preserving automorphism must fix this edge and the matching it is contained in. The colours on the remaining edges in this matching make sure that every colour preserving automorphism must fix this matching pointwise, and thus must fix every matching between two copies of K3 3 setwise. It is now easy to see that a colour preserving automorphism fixes all vertices of C6,K3,3. Finally note that this colouring can be generalised to a colouring of Cn,K3 3 for any number n > 2.	□
3	The proof of Theorem 1.2
In this section, we prove our main result. Determining the distinguishing numbers of the exceptional graphs is straightforward and will be left to the reader.
To show that the remaining graphs have distinguishing number 2, we distinguish cases according to the local group of A := Aut G. Define the type of an edge uv as the size of the orbit of u under the action of the local group at v. By the orbit-stabiliser lemma, this is the index of Auv in Av. Since by vertex transitivity |Av | = |Au|, this also shows that the type is well-defined, i.e. it does not depend on the endpoint of the edge.
Note that since the orbits of the local group at v partition the neighbourhood of v the types of edges incident to v correspond to a partition of 4. Since G is vertex-transitive, this partition is the same for every vertex. Since the only partitions of 4 that do not contain a part of size 1 are (2, 2) and (4), we split up the proof of Theorem 1.2 into the following three cases:
1.	There are edges of type 1. This case is treated in Section 3.1.
2.	All edges have type 2. This is treated in Section 3.2.
4. All edges have type 4, and hence G is arc-transitive. For this case, see Section 3.3. 3.1 Graphs with edges of type 1
Let Gt> 2 be the graph obtained from G by removing all edges of type 1. Note that the components of Gt>2 form a system of imprimitivity for A. We will need the following results.
Lemma 3.1. Assume that every vertex of G is incident to a unique type 1-edge, Gt>2 is not connected, and any two components of Gt>2 are connected by at most one type 1-edge. Then G has a distinguishing 2-colouring.
Proof. Let k be the number of vertices in a component of Gt>2. Consider the graph H obtained from G by contracting every component of Gt>2 to a single vertex. By our assumptions, H is a k-regular graph and it follows from Lemma 2.6 that its distinguishing number is at most k +1. Let c! be a distinguishing colouring of H with colours {0,1,..., k}. We now colour G in the following way: in every component of Gt>2, we colour as many vertices black as the colour of the corresponding vertex of H suggests.
F. Lehner and G. Verret: Distinguishing numbers of finite 4-valent vertex-transitive graphs 175
Since c' is distinguishing, any automorphism which preserves the resulting colouring has to fix all components of Gt>2 setwise. As every type 1 edge is uniquely identified by the components it connects, each type 1 edge and hence also every vertex must be fixed by
Lemma 3.2. Let G be a connected vertex-transitive graph. Assume that Gt>2 is not connected, let H be a component of Gt>2 and let v e H. If H admits a 2-colouring c' such that the only automorphism of H fixing v and preserving c' is the identity, then G has a distinguishing 2-colouring.
Proof. Denote the components of Gt>2 by Hi,..., HR. Note that each Hj is isomorphic to H. Let vi e Hi. Note that the graph obtained from G by contracting the components Hi,..., Hr is connected and vertex-transitive and thus at least 2-connected. Hence G-Hi is connected, and thus (G - Hi) + vi is connected as well.
For i e {2,..., R}, pick some shortest path from Hj to vi in (G - Hi) + vi and let vj and ej be the first vertex and edge of this path, respectively. Without loss of generality we may assume that the number of black vertices in c' is not exactly one—otherwise change the colour of v to obtain a colouring with this property. Let nj: H ^ Hj be an isomorphism which maps v to vj. Such an isomorphism exists because G (and thus also H) is vertex-transitive. Now define a colouring c of G by
Let y be an automorphism of G preserving c. We show that 7 fixes every vertex and thus c is distinguishing.
First, note that 7 must fix vi, since vi is the only black vertex in Hi which in turn is the only component with a unique black vertex.
Next we show that, for i = 1, every Hj must be fixed pointwise by 7. Assume not. Let Hj be a component such that the distance from Hj to vi is minimal, among the components that are not fixed pointwise. The endpoint uj of ej which does not lie in Hj is either vi, or it lies in some component Hj which is closer to vi. Hence uj is fixed by 7. Since ei has type 1, 7 must also fix vj and thus induce an automorphism of Hj. By hypothesis, this induced automorphism is trivial and thus 7 fixes Hj pointwise.
Finally, let x e Hi - vi. Then x is incident to an edge of type 1 which connects Hi to a different component Hj. Since the other endpoint of this edge is fixed by 7, the same must be true for x.	□
Corollary 3.3. Let G be a connected, vertex-transitive graph and let H be a component of Gt>2. If H has a distinguishing 2-colouring, then so does G.
Proof. If H is the only component of Gt>2, then a distinguishing colouring of H is also distinguishing for G, otherwise apply Lemma 3.2.	□
Theorem 3.4. Let G be a connected 4-valent vertex-transitive graph containing edges of type 1. Then D(G) = 2, unless G is K4 □ K2.
every colour-preserving automorphism.
□
28
Ars Math. Contemp. 19 (2020) 189-208
Proof. If all edges are of type 1, then Av = 1 and thus colouring one vertex black and all other vertices white yields a distinguishing colouring.
Next assume that the local group has two orbits of size 1 and one orbit of size 2. In this case Gt>2 is a union of cycles. If there is only one such cycle, then it must have length 6 or more, and hence G is 2-distinguishable by Corollary 3.3. If there is more than one, then the conditions of Lemma 3.2 are satisfied.
Finally consider the case where the local group has one orbit of size 1 and one orbit of size 3. All components of Gt>2 are isomorphic to some 3-regular vertex-transitive graph G'. Also note that the induced action of A on G' is arc-transitive.
If G' has distinguishing number 2, then we can apply Corollary 3.3 to obtain a distinguishing 2-colouring of G. By Theorem 1.1, the only other possibility is that G' is isomorphic to one of K4, K33, Q3 or the Petersen graph.
If Gt>2 is connected, then G is obtained from G' by adding edges of type 1. Since A is arc-transitive on G', no edge of type 1 can connect two neighbours (in G') of the same vertex. Otherwise any two neighbours of this vertex would have to be connected by an edge, contradicting the fact that each vertex of G is adjacent to only one edge of type 1 . Hence an edge of type 1 can't connect vertices at distance at most 2 in G'. This rules out K4, K3 3 and the Petersen graph as possibilities for G', since they have diameter at most 2. The only way to add edges with respect to this constraint in the cube Q3 yields G = K4 4 which does not contain edges of type 1 .
Thus we can assume that Gt>2 is not connected. Both the Petersen graph and Q3 have colourings satisfying the condition of Lemma 3.2, see Figure 4. Hence if G' is one of them, then G has a distinguishing 2-colouring.
Figure 4: Colourings satisfying the condition of Lemma 3.2, v is the square vertex.
We may thus assume that G' is either K4 or K3,3. By Lemma 3.1 we may assume that there is a pair of components of Gt>2 connected by multiple type 1 edges. Since G is vertex-transitive and each vertex is incident to a unique edge of type 1, the number of type 1 edges between any pair of adjacent components of Gt>2 is independent of the choice of the pair. Furthermore, recall that A acts arc-transitively on G'. Hence if two adjacent vertices in a component H are both adjacent to the same component H' (via type 1 edges), then all vertices of H are adjacent to H'. For G' = K4, this is the only possibility, and the resulting graph is G = K4 □ K2. For G' = K3,3, the above observation tells us that all vertices in the same bipartite class of a component send their type 1 edges to the same component, and hence G = Gn,K3,3 (see Figure 2) for some n > 2, which has distinguishing number 2. □
#
F. Lehner and G. Verret: Distinguishing numbers of finite 4-valent vertex-transitive graphs 175
3.2 Graphs with only edges of type 2
In this section, we assume that all edges of G are of type 2. This implies that A has two orbits on arcs and therefore at most two orbits on edges. We distinguish two subcases according to whether G is edge-transitive or not.
3.2.1	Edge-transitive case
Theorem 3.5. Let G be a connected 4-valent graph that is vertex- and edge-transitive but not arc-transitive. Then D(G) = 2.
Proof. In this case, A has two orbits on arcs and each arc is in a different orbit than its inverse arc. By removing one of the two orbits, G becomes an arc-transitive directed graph in which every vertex has in- and out-degree 2. There is some s > 1 such that A acts regularly on directed s-arcs (see for example [12, Lemma 5.4(v)]).
Let P = (v0,..., vs) be a directed s-arc in G. Suppose for a contradiction that there is an arc from vs to v0. Clearly, in this case s > 2, as G does not contain any 2-cycles. There is an automorphism fixing (v0,..., vs_i) pointwise, but not fixing vs. Therefore, the second out-neighbour vs = vs of vs-1 must also have v0 as an out-neighbour. By directed 2-arc-transitivity we conclude that for any vertex v4 on P, the out-neighbours of vj are exactly the in-neighbours of vi+2, so the digraph is a directed wreath graph and G is arc-transitive, which gives the desired contradiction.
We may thus assume that there is no arc from vs to v0. Colour the vertices of P black and the remaining vertices white. Note that v0 is the unique black vertex with no black in-neighbour. Hence v0 and thus all of P must be fixed by any colour-preserving automorphism. By s-arc-regularity, this implies that the colouring is distinguishing and G has distinguishing number 2.	□
3.2.2	Non-edge-transitive case
If G is not edge-transitive, then there must be 2 orbits on edges each of which forms a disjoint union of cycles. Denote the two subgraphs induced by the edge orbits by G1 and G2. By transitivity, all cycles in G1 have the same length, the same is true for G2.
We will inductively construct a distinguishing colouring from partial colourings of G. Let c be a partial colouring of G with domain V C V(G), that is, c is a function from V to some set C of colours. An extension of c is a colouring c of G such that c and c coincide on V.
Lemma 3.6. Let G be a connected 4-valent vertex-transitive but not edge-transitive graph and assume that all edges have type 2. Let G1 and G2 be the subgraphs induced by the two edge orbits. Let V' be a set of vertices of G and let C be a cycle in G1 which is disjoint from V' and contains a neighbour v of some vertex in V'. Then there is a cycle D in G1 which is disjoint from V' (possibly D = C) and a partial 2-colouring c of G with domain C U D such that
•	C and D both contain either 1 or 2 black vertices, and
•	if y G Aut G fixes V' pointwise and fixes any extension of c, then 7 fixes V' U C U D pointwise.
30
Ars Math. Contemp. 19 (2020) 189-208
Proof. Call a vertex u a twin of v if there is an automorphism in the stabiliser of V' that moves u to v. Note that v has at most one twin, since there is an edge in G2 connecting v to some w in V', and w has only one other neighbour in G2.
If v has no twin then every automorphism that fixes V' pointwise must fix v. Set D = C, colour v and one of its neighbours on C black and colour the remaining vertices of C white. Then every automorphism which fixes V' as well as an extension of this colouring must fix v and its black neighbour and thus also fixes C.
Next assume that v has a twin that lies on C. Again let D = C and colour v and one of its neighbours in C black, but make sure that the black neighbour of v is not a twin of v. The same argument as above tells us that this colouring has the desired properties.
Finally assume that v has a twin u that lies outside of C. Let D be the cycle in G1 containing u and observe that D is also disjoint from V'. Colour v and one of its neighbours in C black, colour one of the neighbours of u in D black, and colour the remaining vertices of C U D white. Any automorphism that fixes V' as well as an extension of this colouring must fix u and v and their respective black neighbours, whence we have found the desired colouring.	□
Theorem 3.7. Let G be a connected 4-valent vertex-transitive but not edge-transitive graph and assume that all edges have type 2. Then D(G) = 2.
Proof. Let G1 and G2 be the subgraphs induced by the two edge orbits respectively and without loss of generality assume that cycles in G1 are at least as long as cycles in G2.
If G1 consists of a single cycle then this cycle must have length at least 6. Hence there is a distinguishing 2-colouring of G1 which must also be distinguishing 2-colouring of G. Hence we may assume that G1 consists of more than one cycle.
If cycles in G1 have length at least 4, then let C1 be a cycle in G1 and let v1 be a vertex on this cycle. Now inductively apply Lemma 3.6. For the first step, let V' = {v1}. In each step, pick a cycle C = C1 which contains a G2-neighbour of V', colour it according to the lemma and add the vertices of CUD to V'. The graph obtained from G by contracting every cycle in G1 is connected and vertex-transitive. Hence, by Lemma 2.1 it is 2-connected and remains connected after removing C1. In particular, the above colouring procedure assigns colours to all vertices except those in C1 . Finally colour v1 and its neighbours on C1 black, and colour the rest of C1 white.
We claim that the resulting colouring is distinguishing. Clearly, every colour-preserving automorphism must fix v1 since it is the only black vertex both of whose neighbours in G1 are black (recall that C1 is the only cycle in G1 containing 3 black vertices). Using Lemma 3.6 inductively, we see that every colour-preserving automorphism must fix every cycle pointwise, except possibly C1. Hence the colouring is distinguishing unless the two neighbours of v1 in G1 have the same G2-neighbourhood. In this case, by vertex-transitivity any two vertices at distance 2 in G1 have the same G2-neighbourhood. If cycles in G1 have length 5 or more, this implies that vertices have degree at least 3 in G2 which is a contradiction. If cycles in G1 have length 4, then so do cycles in G2 and G is a graph obtained by identifying antipodal points of 4-cycles, i.e., a wreath graph, which contradicts the assumption that G is not edge transitive.
It remains to deal with the case when both G1 and G2 are disjoint unions of 3-cycles. Let H be the graph with vertices these 3-cycles, with two such 3-cycles being adjacent in H if they share a vertex in G. It is easy to see that H is regular of valency 3 and G = L(H).
F. Lehner and G. Verret: Distinguishing numbers of finite 4-valent vertex-transitive graphs 175
By Theorem 2.3, we have D(G) = D'(H) < 2, unless H is K4 or K3,3. Finally, note that
L(K4) =W3 while L(K3,3) = K3 □ K3.	'	□
3.3 Arc-transitive graphs
We first prove a few lemmas to show that we can restrict ourselves to graphs with girth 4.
Lemma 3.8. Let G be a connected 4-valent arc-transitive graph. If G has girth 3, then G is either K5 or W3, or the line graph of a 3-valent arc-transitive graph.
Proof. Follows from [13, Theorem 5.1(1)]).	□
Lemma 3.9. Let G be a connected graph of minimal valency at least 3 and girth g > 5. If G is s-arc-transitive, then s < g — 3, unless G is a Moore graph of girth 5, or the incidence graph of a projective plane.
Proof. Assume for a contradiction that G is (g — 2)-arc-transitive. Let C = (v0,..., vg_i) be a cycle of length g. Note that (v0,..., vg_2) is a (g — 2)-arc and that its endpoints have a common neighbour. By (g — 2)-arc-transitivity, every (g — 2)-arc has this property. Let v'g_2 be a neighbour of vg_3 outside of C. Then (v0,..., vg_3, vg_2) is a (g — 2)-arc, whence v'g_2 and v0 have a common neighbour vg_1. Now the closed walk (v0,vg_i,vg_2,vg_3,v'g_2,v'g_i,v0) shows that g < 6.
If g = 5, then the fact that the endpoints of every 3-arc have a common neighbour implies that G has diameter 2 and is thus a Moore graph.
If g = 6, then an analogous argument as above yields that G has diameter 3. If G was not bipartite, then for v G V(G) there would be an edge connecting two vertices x and y at the same distance from v, and since g = 6 we have d(x, v) = d(y, v) = 3. But then there is a 4-arc from v to x whence by the above argument v and x have a common neighbour, contradicting d(x, v) = 3.
Hence G is bipartite and every vertex at distance 2 from a given vertex v has a unique
common neighbour with v. It follows that G is the incidence graph of a projective plane.
□
Lemma 3.10. Let G be a connected 4-valent arc-transitive graph of girth at least 5, then D(G) = 2.
Proof. Let g be the girth of G and let s be such that G is s-arc-transitive but not (s + 1)-arc-transitive. Note that there is no 4-valent Moore graph, and that there is a unique 4-valent graph that is the incidence graph of a projective plane, namely the (4, 6)-cage. By Lemmas 2.7 and 3.9 we may thus assume that s < g — 3.
By Lemma 2.2, there is a cycle C = (v0,..., vg_1) such that G — C is 2-edge connected. Let P = (vs+1, vs,..., v1) and let X be its pointwise stabiliser. Note that P is an s-arc and thus X is not transitive on N(v1) \ {v2} (otherwise G would be (s + ^-arc-transitive). Let v0 be a neighbour of v1 that is in a different orbit than v0 under X.
Note that the subgraph induced by the vertices {v0, v0, v1,..., vg_2} is a tree since any additional edge between these vertices would give a cycle of length less than g. Denote this tree by T and let H be the subgraph obtained from G by removing all vertices of T. Observe that v'0 has degree at most 3 in G — C. If H is not connected, then there is one component of H that is connected to v'0 by a unique edge. Removing that edge from G — C
32
Ars Math. Contemp. 19 (2020) 189-208
would disconnect it, contradicting the fact that G - C is 2-edge connected. It follows that H is connected.
Colour all vertices of T black and colour vg-1 white. Inductively colour the vertices of G as follows: Let x be a vertex at minimal distance to vg-1 in H that has not been coloured yet. If x is fixed by the pointwise stabiliser in A of all previously coloured points, then colour it white. Otherwise colour it black.
We claim that this colouring is distinguishing. First note that if an automorphism fixes two neighbours u and w of a vertex v, then it must also fix v, since otherwise the image of v would also be a common neighbour of u and w contradicting g > 5. Note that this implies that all vertices in H with a neighbour outside of H are coloured white. Indeed, at the time such a vertex x is considered for colouring, two of its neighbours are already coloured: its predecessor on a shortest vg-1-x-path in H and its neighbour outside of H. Hence by the previous observation, x is coloured white.
Next we show that v1 is the only black vertex with three black neighbours. By the above observations it is the only such vertex in T. Now let x be a black vertex in H. Then at most one neighbour of x was coloured before x (otherwise we would have coloured x white). Furthermore, if P is a shortest vg-1-x-path in H, then P U C contains an s-arc ending in x. Hence the pointwise stabiliser of x and all vertices coloured before x does not act transitively on the remaining neighbours of x, whence at most one of them will be coloured black.
Let y be a colour preserving automorphism. The above discussion shows that 7 must fix v1. Furthermore all neighbours of T are white, so 7 must preserve T setwise. Since there is no automorphism of G that fixes (v1,..., vg-2) and moves v0 to v0, 7 must fix T pointwise. Finally assume that there is a vertex in H that is not fixed by 7 and let x be the first such vertex that was coloured in the inductive procedure. Clearly, x is coloured black. Let y be the neighbour of x on a shortest vg-1-x-path P, and let S be an s-arc contained in C U P. Then S is pointwise stabilised by 7, and since the orbit of x under the pointwise stabiliser of S is not a singleton, it contains exactly one other element x'. Every automorphism that fixes x and S also fixes x' and vice versa. Hence at most one of x and x' can be coloured black and thus neither of them can be moved by 7.	□
Next we give some results for the case when G has girth exactly 4. Note that in this case, there must be vertices at distance 2 from each other with 2 or more common neighbours. The following two lemmas follow from results in [13].
Lemma 3.11. Let G be a connected 4-valent arc-transitive graph. If there are two vertices at distance 2 with 3 or more common neighbours, then G is isomorphic to either K5 x K2 or Wn for some n > 4.
F. Lehner and G. Verret: Distinguishing numbers of finite 4-valent vertex-transitive graphs 175
Proof. If there are vertices with 4 common neighbours, then by [13, Lemma 4.3], G is a wreath graph. Otherwise, Subcase II.A of the proof [13, Theorem 3.3] implies that G =
K5 x K2.	□
Lemma 3.12. Let G be a connected 4-valent 2-arc-transitive graph. If G has girth 4 but no two vertices at distance 2 have more than 2 common neighbours, then G is isomorphic to either Q4, or the bipartite complement of the Heawood graph.
Proof. By 2-arc-transitivity, every edge is contained in at least three 4-cycles. Subcase II.B of the proof of [13, Theorem 3.3] then implies that G is isomorphic to one of the two graphs as claimed.	□
The hardest case to deal with is when the graph is locally D4. In this case, we take advantage of the following structural property. Note that D4 in its natural action on 4 points admits a unique system of imprimitivity with 2 blocks of size 2. We say that a 2-arc (v0, vi, v2) is straight, if {v0, v2} is a block with respect to the local group at vi, and crooked otherwise. Note that, of the three 2-arcs starting with a given arc, one is straight and two are crooked. Further note that fixing a crooked 2-arc fixes all neighbours of its midpoint. Finally, note that A acts transitively on crooked 2-arcs of G. Call a cycle in G straight, if all sub-arcs of length 2 are straight.
Theorem 3.13. Let G be a connected 4-valent arc-transitive graph, then D(G) = 2 unless G is K5, K3 □ K3, K5 x K2, or Wn for some n > 3.
Proof. By Lemmas 3.8, 3.10, as well as Lemma 2.7, we can assume that G has girth 4. By Lemma 3.11, we can assume that no two vertices have more than two common neighbours.
Since G is arc-transitive, the local group must be a transitive subgroup of S4. If the local group is 2-transitive, then G is 2-arc-transitive and this case is handled with Lemmas 3.12 and 2.7.
If the local group is C4 or V4, then G is arc-regular. One can then colour one vertex v and three of its neighbours black, and colour the remaining vertices white. Any colour preserving automorphism must fix the arc from v to its unique white neighbour, thus the colouring is distinguishing.
The last remaining case is that G is locally D4. Suppose first that G contains a 4-cycle that is not straight. Let (u, v, w, x) be a 4-cycle of G such that (u, v, w) is a crooked 2-arc.
We claim that any automorphism fixing u and all of its neighbours must be the identity. By arc-transitivity and connectedness it is enough to show that such an automorphism must fix all neighbours of v. Since no pair of vertices has more than two common neighbours, u and w are the only two common neighbours of v and x. In particular, if an automorphism fixes w and all its neighbours, then it must also fix u. Hence it fixes a crooked 2-arc with midpoint v, and thus it fixes v and all of its neighbours, thus proving our claim.
Let y be the unique vertex such that (v, w, y) is a straight 2-arc, and let P = (u, v, w, y). Suppose that y is adjacent to u. Let u' be the unique vertex other than u such that (u', v, w) is crooked. Note that there is an automorphism fixing v and w (and thus y) and mapping u to u', and thus y is adjacent to u', and v and y have at least 3 common neighbours (u, u', and w), contradicting an earlier hypothesis. We conclude that y is not adjacent to u and thus the induced subgraph on P is a path of length 3. Colour P black and colour the remaining vertices white. Since (u, v, w) is crooked, but (v, w, y) is straight, every colour preserving
34
Ars Math. Contemp. 19 (2020) 189-208
automorphism fixes P pointwise, and thus it fixes v and all its neighbours. Hence, by the above claim, this colouring is distinguishing.
From now on, we can assume that all 4-cycles of G are straight. Let C be the set of all 4-cycles. Note that every edge is contained in a unique straight 4-cycle, whence C forms a partition of E(G). Furthermore, any two elements of C intersect in at most one vertex, since otherwise there would be vertices with 3 or more common neighbours.
Now consider the auxiliary graph G' with vertex set C and an edge between two vertices if the 4-cycles have a vertex in common. Note that G' is a 4-valent graph on |C| = |E(4G)| = |V(2G)| vertices.
Note that A has a natural induced action on G', and this is easily seen to be locally D4. Furthermore any distinguishing colouring of L(G') corresponds to a distinguishing colouring of G. By Lemma 2.5 and the above observations D(G') > D(L(G')) > D(G). Hence if D(G') = 2, then D(G) = 2 and we are done. By induction, we may thus assume that G' is one of K5, K3 □ K3, K5 x K2, or Wn for some n > 3. If G' = K5, then by Lemma 2.7(2), we have D(L(G')) = 2 and we are done. Finally note that G' = K5 is not possible, since A induces a transitive, locally D4 action on G', but K5 admits no such action.	□
ORCID iDs
Florian Lehner © https://orcid.org/0000-0002-0599-2390 Gabriel Verret © https://orcid.org/0000-0003-1766-4834
References
[1]	M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), #R18 (17 pages), doi:10.37236/1242.
[2]	B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube, Discrete Math. 283 (2004), 29-35, doi:10.1016/j.disc.2003.11.018.
[3]	P. J. Cameron, P. M. Neumann and J. Saxl, On groups with no regular orbits on the set of subsets, Arch. Math. (Basel) 43 (1984), 295-296, doi:10.1007/bf01196649.
[4]	K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), #R16 (19 pages), doi:10.37236/1042.
[5]	R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer, Heidelberg, 4th edition, 2010, doi:10.1007/978-3-642-14279-6.
[6]	P. Erd6s and A. Renyi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295-315, doi:10.1007/bf01895716.
[7]	S. Huning, W. Imrich, J. Kloas, H. Schreiber and T. W. Tucker, Distinguishing graphs of maximum valence 3, Electron. J. Combin. 26 (2019), #P4.36 (27 pages), doi:10.37236/7281.
[8]	H. A. Jung, Zu einem Isomorphiesatz von H. Whitney fur Graphen, Math. Ann. 164 (1966), 270-271, doi:10.1007/bf01360250.
[9]	S. KlavZar, T.-L. Wong and X. Zhu, Distinguishing labellings of group action on vector spaces and graphs, J. Algebra 303 (2006), 626-641, doi:10.1016/j.jalgebra.2006.01.045.
[10]	F. Lehner and S. M. Smith, On symmetries of edge and vertex colourings of graphs, Discrete Math. 343 (2020), 111959, doi:10.1016/j.disc.2020.111959.
[11]	M. PilSniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13 (2017), 259-274, doi:10.26493/1855-3974.981.ff0.
F. Lehner and G. Verret: Distinguishing numbers of finite 4-valent vertex-transitive graphs 175
[12]	P. Potočnik and G. Verret, On the vertex-stabiliser in arc-transitive digraphs, J. Comb. Theory Ser. B 100 (2010), 497-509, doi:10.1016/j.jctb.2010.03.002.
[13]	P. Potočnik and S.Wilson, Tetravalent edge-transitive graphs of girth at most 4, J. Comb. Theory Ser. B 97 (2007), 217-236, doi:10.1016/j.jctb.2006.03.007.
[14]	A. Seress, Primitive groups with no regular orbits on the set of subsets, Bull. London Math. Soc. 29 (1997), 697-704, doi:10.1112/s0024609397003536.
[15]	B. Wang and Z. Zhang, On cyclic edge-connectivity of transitive graphs, Discrete Math. 309 (2009), 4555-4563, doi:10.1016/j.disc.2009.02.019.
[16]	M. E. Watkins, Connectivity of transitive graphs, J. Comb. Theory 8 (1970), 23-29, doi:10. 1016/s0021-9800(70)80005-9.