Symmetry Breaking in Graphs

Michael O. Albertson ^{1} Karen L. Collins Department of Mathematics Department of Mathematics Smith College Wesleyan University Northampton MA 01063 Middletown, CT 06459-0128 albertson@smith.smith.edu kcollins@wesleyan.edu

Submitted: September 1, 1995; Accepted: June 9, 1996.

Abstract

A labeling of the vertices of a graph G, ϕ : V (G) → {1, …, r}, is said to be r-distinguishing provided no automorphism of the graph preserves all of the vertex labels. The distinguishing number of a graph G, denoted by D(G), is the minimum r such that G has an r-distinguishing labeling. The distinguishing number of the complete graph on t vertices is t. In contrast, we prove (i) given any group Γ, there is a graph G such that Aut(G) ≅ Γ and D(G) = 2; (ii) D(G) = O(log(|Aut(G)|)); (iii) if Aut(G) is abelian, then D(G) ≤ 2; (iv) if Aut(G) is dihedral, then D(G) ≤ 3; and (v) If Aut(G) ≅ S_{4}, then either D(G) = 2 or D(G) = 4. Mathematics Subject Classification 05C,20B,20F,68R

1 Introduction

A classic elementary problem with a surprise answer is Frank Rubin’s key problem [15], which Stan Wagon recently circulated in the Macalester College problem column [13].

Professor X, who is blind, keeps keys on a circular key ring. Suppose there are a variety of handle shapes available that can be distinguished by touch. Assume that all keys are symmetrical so that a rotation of the key ring about an axis in its plane is undetectable from an examination of a single key. How many shapes does Professor X need to use in order to keep n keys on the ring and still be able to select the proper key by feel?

1Research supported in part by NSA 93H-3051

The surprise is that if six or more keys are on the ring, there need only be 2 different handle shapes; but if there are three, four, or five keys on the ring, there must be 3 different handle shapes to distinguish them.

The answer to the key problem depends on the shape of the key ring. For instance, a linear key holder would require only two different shapes of keys. As long as the ends had differently shaped keys, the two ends could be distinguished, and one could count from an end to distinguish the other keys. Thinking about the possible shapes of the key holders, we are inspired to formulate the key problem as a problem in graph labeling.

A labeling of a graph G, ϕ : V (G) → {1, 2, …, r}, is said to be rdistinguishing if no automorphism of G preserves all of the vertex labels. The point of the labels on the vertices is to destroy the symmetries of the graph, that is, to make the automorphism group of the labeled graph trivial. Formally, ϕ is r-distinguishing if for every non-trivial σ ∈ Aut(G), there exists x in V = V (G) such that ϕ(x) ≠ ϕ(xσ). We will often refer to a labeling as a coloring, but there is no assumption that adjacent vertices get different colors. Of course the goal is to minimize the number of colors used. Consequently we define the distinguishing number of a graph G by

D(G) = min{r | G has a labeling that is r-distinguishing}.

The original key problem is to determine D(C_{n}), where C_{n} is the cycle with n vertices. Clearly, D(C_{1}) = 1, and D(C_{2}) = 2. Let n ≥ 3 and suppose the vertices of C_{n} are denoted v_{0}, v_{1}, v_{2}, …, v_{n−1} in order. We define two labelings, each of which makes the cycle look like a line with two differently shaped ends. Define labeling ϕ by ϕ(v_{0}) = 1, ϕ(v_{1}) = 2, and ϕ(v_{i}) = 3 for 2 ≤ i ≤ n − 1. Then ϕ is 3-distinguishing. None of C_{3}, C_{4}, C_{5} can be 2-distinguished. However, for n ≥ 6, if ψ is defined by ψ(v_{0}) = 1, ψ(v_{1}) = 2, ψ(v_{2}) = ψ(v_{3}) = 1 and ψ(v_{i}) = 2 for 4 ≤ i ≤ n − 1, then ψ is 2-distinguishing. Hence the surprise.

We next illustrate how different graphs with the same automorphism group may have different distinguishing numbers. Let K_{n} be the complete graph on n vertices, and J_{n} be its complement. Let K_{1,n} be J_{n} joined to a single vertex. Each of these graphs has S_{n} as its automorphism group. It is immediate that D(K_{n}) = D(J_{n}) = D(K_{1,n}) = n.

Now let G_{n} denote the graph with 2n vertices obtained from K_{n} by attaching a single pendant vertex to each vertex in the clique. Clearly Aut(G_{n}) ≅ S_{n}. In an r-distinguishing labeling, each of the pairs consisting of a vertex of the clique and its pendant neighbor must have a different ordered pair of labels; there are r^{2} possible ordered pairs of labels using r colors, hence D(G_{n}) = ⌈\sqrt{n} ⌉.

On the other hand, recall that the inflation of graph G, Inf(G), is defined as follows: the vertices of Inf(G) consist of ordered pairs of elements from G, the first being a vertex and the second an edge incident to that vertex. Two vertices in Inf(G) are adjacent if they differ in exactly one component [3]. In the context of polyhedra, the inflation of a graph is also known as the truncation [4]. Label the vertices of K_{n} with 1, …, n. Then vertices of Inf(K_{n}) can be labelled {i_{j}|1 ≤ i ≤ n, 1 ≤ j ≤ n, and i ≠ j} in the obvious way. Assigning the color 1 to vertex i_{j} if i < j, and the color 2 otherwise shows that D(Inf(K_{n})) = 2. It is easy to see that Aut(Inf(K_{n})) ≅ S_{n}, provided that n ≥ 4.

[figure: G_{5}; Inf(K_{4}); P]

Figure 1 There are only 4 different pairs of 2 colors, hence D(G_{5}) = 3. Inf(K_{4}) can be distinguished with 2 colors. The Petersen graph P can be distinguished with 3 colors, but not with 2.

As a final example, consider line graphs of complete graphs. Let L(G) be the line graph of G. If n ≥ 5, then Aut(L(K_{n})) ≅ Aut(K_{n}) ≅ S_{n} [10]. A case analysis proves that D(L(K_{5})) > 2. The distinguishing number of a graph must be the same as the distinguishing number of its complement, and the complement of L(K_{5}) is the Petersen graph. Thus our 3distinguishing labeling of the Petersen graph shown in Figure 1 above shows that D(L(K_{5})) = 3. In section 5 we sketch an argument due to Lovasz that for n ≥ 6, D(L(K_{n})) = 2.

There is a sense in which distinguishing vertices in a graph is reminiscent of Polya-Burnside enumeration. That context would provide a set, say C, of labeled graphs closed under the action of a given group, say Γ. The Burnside lemma is a tool for computing the number of inequivalent labeled graphs in C where equivalence is given by some action from Γ. Our perspective is essentially dual. We take a particular labeled graph chosen so that it generates a large set of equivalents. If that set has cardinality |Γ|, then the labeling is distinguishing.

We now digress for a bit to consider the complexity of the distinguishing question. First we observe that D(G) = 1 if and only if G is a rigid graph, i.e., one whose automorphism group is trivial. The complexity of deciding if a given graph has a non-trivial automorphism has not been settled [9, 11]. It is known to be Turing equivalent to Unique Graph Isomorphism, and is a candidate for a problem whose difficulty lies between being in P and being NP − complete. Hence determining if D(G) = 1 may be difficult. Let us fix the particular question to be: Given a graph G and an integer k, is D(G) > k? For k = 1, this question is in NP. To see this, it suffices to show that if D(G) > 1, there is a certificate that allows one to easily verify this fact. Here such a certificate could be a vertex bijection, since it is straightforward to check that a vertex bijection is a graph automorphism. In contrast, it seems plausible that this question is not in co − NP. For larger k, the question is not obviously in either NP or co − NP. To see this, suppose we are given a graph G with minimum degree at least 2 and an allegedly r-distinguishing labeling. If we attach a path of length i to each vertex in G that is labeled i, then the original vertices all have degree at least 3. The resulting graph is only polynomially larger than the original, and the original labeling is r-distinguishing if and only if the new graph is rigid.

Although a given group might be the automorphism group of graphs with different distinguishing numbers, there are some restrictions. An automorphism of a graph G can never take vertices in different vertex orbits to each other. Thus vertices in different orbits are always distinguished from each other. Recall that the orbit sizes must divide the order of the group. Thus it is no surprise that the automorphism group is inextricably entwined with the distinguishing number.

Let Γ be an abstract group. We will say that the graph G realizes Γ if Aut(G) ≅ Γ. We define the distinguishing set of a group Γ by

D(Γ) = {D(G)| G realizes Γ }

The purpose of this paper is to examine how properties of graphs and groups affect the parameters D. In section 2 we investigate arbitrary groups and show that D(G) = O(log|Aut(G)|) and 2 ∈ D(Γ). In section 3 we develop some tools to distinguish orbits. One consequence is that if Aut(G) is either abelian or hamiltonian (but not trivial), then D(G) = 2. We discuss dihedral groups in Section 4. If Aut(G) is dihedral, then D(G) ≤ 3. Furthermore if n ≠ 3, 4, 5, 6, 10 and Aut(G) ≅ D_{n} ( D_{n} ≅ Aut(C_{n}) ), then D(G) = 2. In section 5 we obtain the initially counterintuitive result that D(S_{4}) = {2, 4}. We make conjectures in Section 6.

2 Distinguishing arbitrary groups

Our first result says that given a fixed group, a graph that realizes that group cannot have an arbitrarily large distinguishing number.

Theorem 1 Suppose H_{k} = {e} < H_{k−1} < ⋯ < H_{2} < H_{1} = Γ is a longest chain of subgroups of Γ where H_{i+1} is a proper subgroup of H_{i} for 1 ≤ i ≤ k − 1. If G realizes Γ, then D(G) ≤ k.

Proof Suppose ϕ is an r-distinguishing labeling of G, where r = D(G). Let G_{1}, G_{2}, …, G_{r} be isomorphic copies of G. For 1 ≤ i ≤ r label G_{i} by c_{i} : V (G_{i}) → {1, 2, 3, …, i} where

c_{i}(v) = \{{ϕ(v) if ϕ(v) ≤ i \atop 1 if ϕ(v) > i}

Notice that if c_{i}(v) ≠ 1, then c_{i}(v) = ϕ(v).

Now the automorphism group of G_{i}, Aut(G_{i}), is the subgroup of Aut(G), each element of which preserves the labeling c_{i} of the vertices of G_{i}. Clearly Aut(G_{i+1}) is a subgroup of Aut(G_{i}). We claim Aut(G_{i+1}) is a proper subgroup of Aut(G_{i}). By contradiction, suppose Aut(G_{i+1}) = Aut(G_{i}). We show that there exists an automorphism that preserves ϕ, hence ϕ is not r-distinguishing. Let ψ : V (G) → {1, 2, 3, …, r} − {i + 1} by

ψ(v) = {1 if ϕ(v) = i + 1 ϕ(v) otherwise

Then ψ uses only r − 1 colors, and therefore cannot be distinguishing because D(G) = r. There must then exist a non-trivial automorphism g of G such that ψ(vg) = ψ(v) for all vertices v in G. If v is a vertex with ϕ(v) ≠ i+1, then ψ(vg) = ψ(v) = ϕ(v). If ϕ(vg) ≠ i + 1, then ϕ(vg) = ψ(vg) = ϕ(v). We need to prove that if ϕ(v) = i + 1 or ϕ(vg) = i + 1, then ϕ(vg) = ϕ(v).

Since g preserves the labels {1, 2, 3, …, i}, g preserves c_{i} and so g ∈ Aut(G_{i}). We have assumed that Aut(G_{i}) = Aut(G_{i+1}), hence g preserves c_{i+1}. If ϕ(v) = i + 1, then c_{i+1}(v) = i + 1 = c_{i+1}(vg). Hence ϕ(vg) = i + 1, so ϕ(v) = ϕ(vg). Conversely, if ϕ(vg) = i + 1, then c_{i+1}(vg) = i + 1 = c_{i+1}(v). Hence ϕ(v) = i + 1 = c_{i+1}(v). Therefore, g preserves ϕ and ϕ cannot be distinguishing. This contradicts our assumption that ϕ is an r-distinguishing labeling. □

We remark that this proves that the largest integer in D(S_{3}) is 3, since the subgroups of S_{3} have orders 1, 2, 3, 6, and no order 2 subgroup can be contained in an order 3 subgroup. The complete graph on 3 vertices requires 3 colors to distinguish, and we show in the next theorem that 2 is in the distinguishing set of every group, so D(S_{3}) = {2, 3}.

Corollary 1.1 Let Γ have m elements. Then the largest integer in D(Γ) is less than or equal to 1 + ⌊log_{2}(m)⌋.

Proof Let k be as defined in Theorem 1. Since \frac{|H_{i+1}|}{|H_{i}|} ≥ 2, |Γ| ≥ 2^{k}. □

The standard construction of a graph that realizes a particular group is due to Frucht, see [7]. Recall that the construction begins with one vertex for each group element. Vertices corresponding to group elements u and v are joined by a directed colored edge labeled g precisely if ug = v. A graph is obtained by replacing the colored arcs by graph gadgets (typically paths with different length paths off each vertex). Given a group Γ, we denote the Frucht graph by F (Γ) and note that Aut(F (Γ)) ≅ Γ. Now if Σ is a subgroup of Γ, then we may obtain a labeled graph whose automorphism group is isomorphic to Σ by labeling F (Γ) in the following way: If a vertex is one of the original vertices of the Cayley graph and is in Σ or if the vertex is in a gadget that replaced an arc labeled with an element of Σ, then that vertex is labeled 1. All other vertices are labeled 2. Any automorphism of the labeled graph must preserve the 1’s and is thus an automorphism from F (Σ). Consequently, we can realize any subgroup of a given group with a 2-colored Frucht graph.

Theorem 2 For any finite group Γ, 2 ∈ D(Γ).

Proof First we note that for any group Γ, there is a connected cubic graph G which realizes Γ, see [6]. Suppose G has n vertices. Attach a path with ⌈log_{2}n⌉ vertices to each vertex of G to obtain Ĝ. There are 2^{⌈log_{2}n⌉} ≥ n possible colorings of the paths using 2 colors. Color each one differently. Then this labeling is 2-distinguishing for Ĝ. Since we have attached the same sized path to every vertex, every automorphism of G is also an automorphism of Ĝ. An automorphism of Ĝ must preserve the original vertices of G, since the original vertices have degree 4 in Ĝ and the new vertices have degree less than or equal to 2. This fixes the first vertex of each new path, and hence the rest of the new path. □

3 Distinguishing via orbits

It is not necessary that a labeling distinguish every orbit separately in order to distinguish the entire graph. See Figure 2 below. Sometimes it is easy to distinguish each orbit separately. We say that an r-labeling distinguishes an orbit if every automorphism that acts non-trivially on the orbit maps at least one vertex to a vertex with a different label. Alternatively if U ⊆ V (G) let G[U] denote the induced subgraph of G on the vertex set U. Then if U is an orbit of G, a labeling distinguishes U if it distinguishes G[U]. Trivially an orbit of size 1 can be distinguished with 1 color.

[figure]

Figure 2 Two graphs which realize D_{4}. Each graph can be distinguished with 2 colors, even though no orbit is separately distinguished.

Theorem 3 Let Γ be the automorphism group of graph G. Let u be a vertex of G and H_{u} = {h ∈ Γ|uh = u} be the stabilizer subgroup of u. Let O_{u} be the vertex orbit that contains u. If H_{u} is normal in Γ, then O_{u} can be distinguished with 2 colors.

Proof Color vertex u red and the rest of the vertices in O_{u} blue. Then if there exists an automorphism h in Γ which does not distinguish O_{u}, it must fix u and there must exist x, y ∈ O_{u} such that xh = y, but x ≠ y. Since h fixes u, h ∈ H_{u}. Since x, y ∈ O_{u}, there are group elements g_{1}, g_{2} such that x = ug_{1} and y = ug_{2}. Then ug_{1}h = ug_{2}. Since H_{u} is normal, there exists h′ ∈ H_{u} such that g_{1}h = h′g_{1}. Therefore, uh′g_{1} = ug_{1}, since H_{u} is the stabilizer of u. This means x = ug_{1} = ug_{2} = y, hence h fixes every vertex in O_{u}. □

Recall that a non-abelian group is called hamiltonian if every subgroup is normal [8].

Corollary 3.1 If non trivial Γ is abelian or hamiltonian, then D(Γ) = {2}.

Proof Every subgroup of Γ is normal. Hence every orbit can be distinguished with 2 colors. □

A large orbit can force a graph to have a low distinguishing number.

Theorem 4 Let G be a graph with Aut(G) = Γ. If G has an orbit O = {u_{1}, u_{2}, u_{3}, …, u_{s}} that can be distinguished with k colors, and ∩_{i=1}^{s}H_{u_{i}} = {e} where H_{u_{i}} is the stabilizer group of u_{i}, then G can be distinguished with k colors.

Proof Let O be labeled with a k-distinguishing labeling. Let σ ∈ Γ. Then σ acts non-trivially on O because the only element that fixes every member of O is the identity. Therefore, there exists a member of O, say u_{i} such that the color of u_{i} is different from the color of u_{i}σ. □

If vertex u in G has stabilizer subgroup H_{u}, then the size of the orbit that contains u is |Aut(G)|/|H_{u}|.

Corollary 4.1 A graph G which has an orbit of size |Aut(G)| can be distinguished with 2 colors.

Proof Let O be such an orbit. Then the stabilizer subgroup of every element of O has order 1, hence is trivial. Color one vertex red and the rest blue. Then every non-trivial automorphism of the graph must take the red vertex to a blue one. □

Having many orbits can force a graph to be 2-distinguishable.

Theorem 5 Let G realize group Γ. Let u_{1}, u_{2}, …, u_{t} be vertices from different vertex orbits of G with H_{1}, H_{2}, …, H_{t} their respective stabilizing subgroups. If H_{1} ∩ H_{2} ∩ ⋯ ∩ H_{t} = {e}, then D(G) = 2.

Proof Color u_{1}, u_{2}, …, u_{t} red and the rest of the vertices blue. Let g ∈ Γ. Since the intersection of the stabilizers of u_{1}, u_{2}, …, u_{t} is just the identity, there is some some i such that g does not fix u_{i}. Thus u_{i}g is colored blue, while u_{i} is colored red. Thus we have a 2-distinguishing labeling of G. □

4 Dihedral groups

We use D_{n} (n ≥ 3) to denote the dihedral group of order 2n. Such groups arise naturally in geometry as the symmetries of the regular n-gon and in graph theory as the automorphism groups of the cycles. The dihedral groups are the most elementary non-abelian groups, having a cyclic subgroup half the size of the original group. In this section we compute the distinguishing set of every dihedral group.

Let D_{n} be generated by σ, τ where σ^{n} = e, τ^{2} = e, and τσ = σ^{n−1}τ. Every element τσ^{i} for 0 ≤ i ≤ n − 1 is an involution of D_{n}. These are the only involutions of D_{n} unless n is even, in which case σ^{\frac{n}{2}} is an involution and \{e, σ^{\frac{n}{2}} \} is the center of D_{n}.

The non-trivial subgroups of D_{n} fall into one of three types: a subgroup of < σ >, the cyclic half of D_{n}, a subgroup isomorphic to D_{m} where m|n, and a subgroup with the identity and an order 2 element (which is not a power of σ). We describe these three types by their generators, and select coset representatives for the orbits of vertices with one of these subgroups as its stabilizer. Let 0 ≤ i ≤ n − 1 and 1 ≤ j ≤ n − 1. The three types of subgroups are

< σ^{j} >, < σ^{j}, τσ^{i} >, < τσ^{i} >

Then < σ^{j} > is normal in D_{n}, so has no conjugates except itself. The intersection of its conjugates is also itself. If vertex v has stabilizer < σ^{j} >, then the orbit of v is {v, vσ, vσ^{2}, …, vσ^{j−1}, vτ, vτσ, vτσ^{2}, …, vτσ^{j−1}}.

The subgroups conjugate to < σ^{j}, τ > are the subgroups

< σ^{j}, τσ >, < σ^{j}, τσ^{2} >, …, < σ, τσ^{j−1} >

whose intersection is < σ^{j} >. If vertex v has stabilizer < σ^{j}, τσ^{i} >, then the orbit of v is {v, vσ, vσ^{2}, …, vσ^{j−1}}.

The subgroups conjugate to < τ > are generated by the involutions that have a τ:

< τσ >, < τσ^{2} >, …, < τσ^{n−1} >

whose intersection is just the identity. If vertex v has stabilizer < τσ^{i} >, then the orbit of v is {v, vσ, vσ^{2}, …, vσ^{n−1}}.

Lemma 1 Let G realize D_{n}, and suppose that G has t orbits. Let u_{1}, u_{2}, …, u_{t} be vertices from the t different vertex orbits of G with H_{1}, H_{2}, …, H_{t} their respective stabilizing subgroups. Then < σ > ∩H_{1} ∩ H_{2} ∩ ⋯ ∩ H_{t} = {e}.

Proof We observe that the conjugacy class of σ^{t} in D_{n} is {σ^{t}, σ^{n−t}}, since σ^{l}σ^{t}σ^{−l} = σ^{t} and τσ^{i}σ^{t}τσ^{i} = σ^{n−t}. Hence if σ^{t} is an element of any subgroup H, then σ^{t} is an element of any subgroup conjugate to H. Therefore, if σ^{t} ∈ H_{1} ∩ H_{2} ∩ ⋯ ∩ H_{t}, then σ^{t} is in every conjugate of each of these stabilizers, hence is in every stabilizer of every vertex of G. If σ^{t} fixes every vertex of G, since G realizes D_{n}, σ^{t} = e and t = n. □

Lemma 2 Let G realize D_{n}. Let u be a vertex in G whose stabilizer H_{u} =< σ^{j} >. Let O_{u} be the orbit of u. Then G can be distinguished with 2 colors.

Proof Let u, u_{2}, …, u_{t} be vertices from all the different vertex orbits of G with H_{u}, H_{2}, …, H_{t} their respective stabilizing subgroups. Then H_{u} ∩ H_{2} ∩ ⋯ ∩ H_{t} ⊆ H_{u} =< σ^{j} >. By Lemma 1 the intersection must be the identity, in which case G is 2-distinguishable by Theorem 5. □

Lemma 3 Let G realize D_{n}. Let u be a vertex in G whose stabilizer H_{u} =< σ^{j}, τσ^{i} > or < τσ^{i} >. Let O_{u} be the orbit of u. If |O_{u}| ≥ 6 then O_{u} can be distinguished with 2 colors.

Proof The orbit of u is O_{u} = {u, uσ, uσ^{2}, …, uσ^{j−1}}, where we may assume that j ≥ 6. Let A = {u, uσ^{2}, uσ^{3}}. Color the vertices in A red and the rest of O_{u} blue. Note that this corresponds with the labeling l′ from the introduction. We claim that this is a 2-distinguishing coloring of O_{u}, i.e. that every automorphism that acts non-trivially on O_{u} does not fix A. The proof goes as follows: Suppose g ∈ D_{n} fixes A, then ug ∈ A, hence ug = u, uσ^{2} or uσ^{3}. The automorphisms that send u to u are H_{u}, the automorphisms that send u to uσ^{2} are H_{u}σ^{2} and the automorphisms that send u to uσ^{3} are H_{u}σ^{3}. We check that each automorphism in H_{u}, H_{u}σ^{2}, H_{u}σ^{3} either acts trivially on O_{u} or does not fix A. The subgroup of automorphisms that act trivially on O_{u} is the intersection of the stabilizer subgroups of each vertex, hence, if H_{u} =< σ^{j}, τσ^{i} > this is < σ^{j} > and if H_{u} =< τσ^{i} >, this is {e}.

If H_{u} =< σ^{j}, τσ^{i} >, then j divides n and the elements of H_{u} are

e, σ^{j}, σ^{2j}, σ^{3j}, …, σ^{( \frac{n}{j} −1)j}, τσ^{i}, τσ^{i+j}, τσ^{i+2j}, …, τσ^{i+( \frac{n}{j} −1)j}

Let 0 ≤ d ≤ \frac{n}{j} − 1. The table below shows the outcomes when these automorphisms are applied to A.

\begin{aligned}Aσ^{dj} & = & A & Aτσ^{i+dj} & = & \{u, uσ^{n−2}, uσ^{n−3}\} \\ Aσ^{dj}σ^{2} & = & \{uσ^{2}, uσ^{4}, uσ^{5}\} & Aτσ^{i+dj}σ^{2} & = & \{uσ^{2}, u, uσ^{n−1}\} \\ Aσ^{dj}σ^{3} & = & \{uσ^{3}, uσ^{5}, uσ^{6}\} & Aτσ^{i+dj}σ^{3} & = & \{uσ^{3}, uσ, u\} \end{aligned}

Since n ≥ 6, only σ^{dj} preserve A, however, σ^{dj} acts trivially on O_{u}.

If H_{u} =< τσ^{i} >, then H_{u} = {e, τσ^{i}}. The table below shows the outcomes when τσ^{i}, τσ^{i}σ^{2}, τσ^{i}σ^{3} are applied to A.

\begin{aligned}Aτσ^{i} & = & \{u, uσ^{n−2}, uσ^{n−3}\} \\ Aτσ^{i}σ^{2} & = & \{uσ^{2}, u, uσ^{n−1}\} \\ Aτσ^{i}σ^{3} & = & \{uσ^{3}, uσ, u\} \end{aligned}

Since n ≥ 6, none of these preserve A. □

Lemma 4 Let G realize D_{n}. Let u be a vertex in G whose stabilizer H_{u} =< σ^{j}, τσ^{i} > or < τσ^{i} >. Let O_{u} be the orbit of u. If |O_{u}| ≥ 6 then G can be distinguished with 2 colors.

Proof If H_{u} =< τσ^{i} >, then the intersection of the subgroups conjugate to H_{u} is just the identity. Thus we apply Lemma 3 to prove that O_{u} is 2-distinguishable and Theorem 4 to prove that G is 2-distinguishable.

Assume that H_{u} =< σ^{j}, τσ^{i} >. Then since O_{u} is 2-distinguishable, every automorphism that acts non-trivially on O_{u} takes a red vertex to a blue vertex. The automorphisms which act trivially on O_{u} are those in the intersection of the stabilizers of vertices in O_{u}. This intersection is the cyclic subgroup Λ =< σ^{j} >.

The action of Λ on G makes vertex orbits U_{1}, U_{2}, …, U_{s} (which are contained in the vertex orbits of G under D_{n}). The orbit O_{u} under Λ is broken into 1-orbits, since σ^{j} fixes O_{u}. For each orbit U_{i} which has order greater than 1, choose a vertex v_{i} ∈ U_{i} and color v_{i} red and the rest of the vertices in U_{i} blue. Then we claim that every automorphism in Λ must take a red to a blue vertex, because every automorphism in Λ must move v_{i} for some i. Let σ^{dj} ∈ Λ, where 1 ≤ d ≤ (\frac{n}{j} − 1). If v_{i}σ^{dj} = v_{i}, then U_{i}σ^{dj} = U_{i} since Λ is abelian. Thus if σ^{dj} fixes v_{i} for every 1 ≤ i ≤ s, then σ^{dj} fixes U_{i} for every 1 ≤ i ≤ s, hence σ^{dj} fixes all of G. This contradicts our assumption that G realizes D_{n}. Thus our coloring 2-distinguishes G. □

Theorem 6 D(D_{n}) = {2} unless n = 3, 4, 5, 6, 10, in which case, D(D_{n}) = {2, 3}.

Proof Let G be a graph that realizes D_{n}. By Lemmas 2, 3, 4, if G has an orbit of size at least 6, then G is 2-distinguishable. Let p be a prime divisor of n, and suppose that p^{α} is the largest power of p that divides n. Then the action of the cyclic subgroup Λ =< σ^{\frac{n}{p^{α}}} > makes vertex orbits in G of size 1, p, p^{2}, …, or p^{α}. Let u be a vertex in G, and let d be the smallest positive integer such that uσ^{d \frac{n}{p^{α}}} = u. Then d is the size of the Λ-orbit that contains u. Therefore, d divides p^{α}. We claim that there must be an orbit O under Λ of size p^{α}. If not, then for each u ∈ G, uσ^{d \frac{n}{p^{α}}} = u for some d = p^{β} and β < α. Since d\frac{n}{p^{α}} = p^{β} \frac{n}{p^{α}} = \frac{n}{p^{α−β}}, and α − β ≥ 1, then uσ^{\frac{n}{p}} = u. Hence σ^{\frac{n}{p}} fixes all of G, which contradicts our assumption that G realizes D_{n}. Thus O stays the same size or becomes larger under the action of D_{n}. Therefore, if n has a divisor which is a prime power p^{α} greater than 6, then D(D_{n}) = {2}.

We may therefore assume that n has no prime divisor greater than 5, that n has at most one factor of 5, one factor of 3, and two factors of 2. Thus the only remaining cases are n = 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. We prove first that if n ≥ 12, then D(D_{n}) = {2}.

We may assume that every orbit of G has size less than or equal to 5. By Lemma 2, we may assume that the stabilizer of every vertex is one of the second two types: either < σ^{j}, τσ^{i} > of order \frac{2n}{j} or < τσ^{i} > of order 2. However, an order 2 stabilizer corresponds to an order n orbit, which is greater than 5 if n ≥ 12. Let u be a vertex in an orbit O of size d (where d = 1, 2, 3, 4 or 5 and d divides n) with stabilizer H_{u}, of size \frac{2n}{d}. Then H_{u} =< σ^{d}, τσ^{i} > for some 0 ≤ i ≤ d − 1. Thus < σ^{d} > fixes O. Let u′ be a vertex in an orbit O′ of size d′ with stabilizer H_{u′} =< σ^{d′}, τσ^{i′} >. Let l = lcm(d, d′). Then < σ^{d′} > fixes O′ and < σ^{l} > fixes both O and O′. In order for G to realize D_{n}, G must have orbits with sizes whose least common multiple is n.

Hence if n = 12, there are orbits of size 3, 4; if n = 15, there are orbits of size 3, 5; if n = 20, then 4, 5; if n = 30, then 2, 3, 5; if n = 60, then 3, 4, 5. Since 15 is odd and 30 has only one prime factor of 2, there is no 2-orbit if n = 15, and no 4-orbit if n = 30. If n = 12, 20, 60, then there must be a 4-orbit, but then there is no 2-orbit, because we can choose a stabilizer from the 2-orbit, < σ^{2}, τ >, and a stabilizer from the 4-orbit, < σ^{4}, τσ >, whose intersection is < σ^{4} >. By Lemma 1, the intersection of stabilizer subgroups from all the orbits is then just the identity, and hence by Theorem 5 G can be 2-distinguished. Similarly, G cannot have two orbits of the same size. Except for 1-orbits, then, the orbit sizes for each n must be exactly as listed in the first sentence of this paragraph.

Hence if n ≥ 12, the orbits of G have sizes which are all pairwise relatively prime. The bipartite graphs formed by the vertices of two orbits and the edges between the orbits are then either complete or empty. By Lemma 5 below, D_{n} is the product of the automorphism group of each orbit, considered as a subgraph of G. Since each orbit must form a vertex transitive graph, the orbits of size 3 are K_{3} or its complement; the orbits of size 4 are K_{4}, its complement, C_{4} or its complement; and the orbits of size 5 are K_{5} or its complement, C_{5}, or its complement. In each case, the product of the sizes of the appropriate groups is larger than the size of D_{n} for the corresponding value of n. Thus if n ≥ 12, D(D_{n}) = {2}.

Next we show that if n = 3, 4, 5, 6, 10, then D(D_{n}) = {2, 3}. As observed above, D(S_{3}) = {2, 3}, and D_{3} = S_{3}. ¿From the key problem, 3 ∈ D(D_{4}), D(D_{5}). Now D_{2m} has center C = {e, σ^{m}}, and D_{2m}/C ≅ D_{m} when m is odd by σ → (σ, τ) and τ → (e, τ). Hence K_{3,2}, which requires 3 colors to distinguish, realizes D_{6}, and C_{5} ∨ K_{2} realizes D_{10}.

It remains to be shown that if n = 3, 4, 5, 6, 10, every graph with automorphism group D_{n} can be distinguished with 3 colors. Let u_{1}, u_{2}, …, u_{t} be vertices from the t different vertex orbits of G with H_{1}, H_{2}, …, H_{t} their respective stabilizing subgroups. By Lemma 1, < σ > ∩H_{1}∩H_{2}∩⋯∩H_{t} = {e}.

Therefore the subgroup ∩_{l=1}^{t}H_{l} is of the third type, so ∩_{l=1}^{t}H_{l} =< τσ^{i} >, for some 0 ≤ i ≤ n − 1. Color u_{1}, u_{2}, …, u_{t} red, and choose one vertex v which is not fixed by τσ^{i} (all of u_{1}, u_{2}, …, u_{t} are fixed by τσ^{i}) and color v green. Color the rest of the vertices in G blue. Then every automorphism either moves a red vertex to a vertex which is not red, except for τσ^{i} which fixes all the red vertices, but moves the unique green vertex to either a red or a blue vertex. Thus every graph that realizes D_{n} can be 3-distinguished. □

Lemma 5 Suppose O is an orbit of G and for every other orbit O′ of G, G[O′] ≅ G̸[O]. Furthermore suppose that each bipartite graph formed by the vertices in O, O′ and the edges between these two orbits is either empty or complete. Then Aut(G) = Aut(G[O]) × Aut(G[V − O]).

Proof Let v ∈ V, h_{1} ∈ Aut(G[O]), and h_{2} ∈ Aut(G[V − O]). We define ω : Aut(G[O]) × Aut(G[V − O]) → Aut(G) by

ω(h_{1}, h_{2})(v) = \{ {(v)h_{1} if v ∈ O \atop (v)h_{2} if v ∈ V − O}

Then ω(h_{1}, h_{2}) is an automorphism of G, because it preserves the adjacencies in O, in V −O, and between O and V −O. Conversely, any automorphism of G, when restricted to O is an automorphism of G[O], and when restricted to V − O is an automorphism of G[V − O]. □

5 The symmetric group

Before proceeding to our principal result of this section (determining D(S_{4})), we present an argument (due to Lovasz [12]) to show that if n ≥ 6, then D(L(K_{n})) = 2. Since Aut(L(K_{n})) = Aut(K_{n}) = S_{n}, it is enough to show that by 2-coloring the edges of K_{n} we can break every vertex automorphism of K_{n}, since every automorphism of the vertices of K_{n} is an automorphism of the edges as well. Let G consist of a path of n vertices with one additional edge joining the second and fourth vertex. If n ≥ 6, then G is rigid. Thus if we color the edges of a copy of G in K_{n} red and all the complementary edges blue, we have destroyed all the automorphisms.

Theorem 7 D(S_{4}) = {2, 4}. Furthermore, if G is a graph such that D(G) = 4, then G has exactly one 4-orbit and every other vertex is fixed by every automorphism of G.

Outline of Proof Let G realize S_{4}. Every orbit size must divide 24. By Corollary 4.1, if G has a 24 orbit, then G can be 2-distinguished. It is not hard to show that any orbit with 8 or 12 vertices can be 2-distinguished. From Theorem 4 it follows that if G has an orbit of size 8 or 12, then G can be 2-distinguished. The rest of the argument falls into two cases depending on whether or not G has an orbit of size 4.

Suppose that G does have a 4-orbit U. The stabilizer of any vertex in U must be isomorphic to S_{3}. There are four copies of S_{3} in S_{4}, which are all conjugate, so each is the stabilizer of exactly one vertex in U. The induced subgraph G[U] on U must be a vertex transitive graph on 4 vertices. Since the stabilizer of each vertex in U contains a 3-cycle, G[U] cannot be a matching or a 4-cycle, Thus G[U] is either 4 independent vertices or K_{4}.

If every orbit besides U has size 1, then by Lemma 5, Aut(G) = Aut(G[U]) = S_{4}, hence four colors are necessary to distinguish the four vertices in U and sufficient to distinguish G. If there exists an orbit W besides U which has size greater than 1, then the proof proceeds by providing a 2 coloring of the graph between U and W which must be 2-distinguishing of G.

Suppose that G has no orbit of size 4. Then the possible orbit sizes for G are 1, 2, 3, or 6. The rest of the argument proceeds by analyzing the stabilizers of the possible orbits and providing 2-distinguishing colorings for graphs with 6-orbits, and graphs without 6-orbits, but with 3-orbits. Clearly graphs with largest orbit size 2 can be 2-distinguished. The authors will be happy to provide details of the proof upon request. □

6 Conjectures

Conjecture 1 There does not exist a group Γ such that D(Γ) = {2, 3, 4}.

Conjecture 2 If n ≥ 4, then n − 1 is not in D(S_{n}). In particular this would imply that D(S_{5}) = {2, 3, 5}. We further conjecture that for 6 ≤ n ≤ 9, D(S_{n}) = {2, 3, n}.

Conjecture 3 If G realizes S_{n} and D(G) = n, then G consists of K_{n} or its complement together with vertices in 1- orbits.

References

[1] Bela Bollobas, Graph Theory, Springer-Verlag, New York, 1979, Graduate Texts in Mathematics.

[2] N. L. Biggs and A. T. White, Permutation Groups and Combinatorial Structures, Cambridge Univ. Press, New York, 1979, London Math. Soc. Lect. Notes Ser. 33.

[3] V. Chvatal, Tough graphs and Hamiltonian circuits, Disc. Math. 5 (1973), 215-228.

[4] H. S. M. Coxeter, Regular Polytopes, Dover, New York, 1973.

[5] H. S. M. Coxeter and W. O. Moser, Generators and Relations for Discrete Groups, Springer-Verlag, Berlin, 1957.

[6] R. Frucht, Graphs of Degree Three with a Given Abstract Group, Canadian J. Math. 1 (1949) 365-378.

[7] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, Inc., New York, 1987.

[8] Marshall Hall, The Theory of Groups, Macmillan, New York, 1959.

[9] Christoph Hoffmann, Group Theoretic Algorithms and Graph Isomorphism, Springer Verlag, New York, 1982 (Lecture Notes in Computer Science 136).

[10] D. A. Holton and J. Sheehan, The Petersen Graph, Cambridge University Press, New York, 1993.

[11] J. Kobler, U. Schoning, and J.Toran, The Graph Isomorphism Problem, Its Structural Complexity, Birkhauser, Boston, 1993.

[12] L. Lovasz, personal communication.

[13] J. Konhauser, D. Velleman, and S. Wagon, Which Way Did the Bicycle Go?, Dolciani series, Mathematical Association of America, Washington, D.C. (1996).

[14] Joseph J. Rotman, An Introduction to the Theory of Groups, Springer-Verlag, New York, 1995.

[15] Frank Rubin, Problem 729 in Journal of Recreational Mathematics, volume 11, (solution in volume 12, 1980), p. 128, 1979.

[16] Arthur T. White, Graphs, Groups and Surfaces, North Holland, New York, 1984, North Holland Math Studies 8.