An introduction to

SYMMETRY BREAKING IN GRAPHS

Michael O. Albertson Department of Mathematics Smith College Northampton MA 01063 albertson@smith.smith.edu

Karen L. Collins Department of Mathematics Wesleyan University Middletown, CT 06459-0128 kcollins@wesleyan.edu

This is intended to be a short summary of results that will appear elsewhere, with the goal being to reach the list of open problems at the end. Our motivation is the following:

Professor X has a key ring with n seemingly identical keys (that open different doors). We put colored labels on the keys to distinguish them. What is the minimum number of colors needed?

This first appeared in [3], and was brought to our attention by S. Wagon [2].

It translates to the following graph labeling problem: What is the minimum number of colors needed to label the vertices of C_{n} so that no automorphism of C_{n} preserves the labeling? The surprise is that three colors are needed if n = 3, 4, 5, but for n ≥ 6, two colors suffice.

Let G be a graph with vertex set V. We define an r-distinguishing labeling to be a map ϕ : V → {1, 2, 3, …, r} such that for any nontrivial automorphism γ of G, there exists vertex u such that ϕ(u) ≠ ϕ(γ(u)). We define D(G) to be equal to the minimum r such that G has an r-distinguishing labeling.

Here are some examples of the distinguishing number. Let K_{n} be the complete graph on n vertices and R_{n} be the star on n + 1 vertices. Then D(K_{n}) = D(R_{n}) = n. Let G_{n} be the complete graph on n vertices with a vertex of degree one attached to each vertex in the complete graph (so G_{n} has 2n vertices. Then D(G_{n}) = ⌈\sqrt{n}⌉, since G_{n} is distinguished when every leaf edge is colored distinctly. Let L(K_{n}) be the line graph of K_{n}. Then by exhaustion, L(K_{3}) = L(K_{4}) = L(K_{5}) = 3, but an elegant proof by L. Lovász shows L(K_{n}) = 2 for n ≥ 6.

[figure: G_{5}; P]

Figure 1 3-distinguishing labelings of G_{5} and the complement of L(K_{5}), the Petersen graph, P.

Now K_{n}, R_{n}, G_{n} and L(K_{n}) have different distinguishing numbers, but for n ≥ 5, they all have automorphism group S_{n}. This leads us to make the following definition. Let Γ be a group. Then define

D(Γ) = {r | there exists a graph G such that Aut(G) ≅ Γ and D(G) = r.}

Then D(Γ) = {1} if and only if Γ is trivial. We show in [1] that (i) If Γ is abelian, then D(Γ) = 2; (ii) If Γ is dihedral, then D(Γ) is either {2} or {2, 3}; (iii) For any Γ, 2 ∈ D(Γ); and (iv) D(S_{4}) = {2, 4}.

We are interested in bounds on the size of the largest element of D(Γ). In [1], we show that this is less than or equal to the length of the longest chain of increasing subgroups of Γ. Another bound, inspired by D. Kleitman, shows that the largest element of D(Γ) ≤ k if the order of Γ ≤ k!. This proves, for example, that the largest element of D(S_{n}) is n.

We are also interested in bounds on the distinguishing number of graph. In this direction, we have shown that if G is regular of degree j, then D(G) ≤ j + 1. For example, D(K_{4}) = 4, but D(P) = 3.

Another interesting question that arises is the pattern of the distinguishing number for graph families. For instance, let C_{n} be the cycle on n vertices, then the sequence D(C_{n}), starting with, n = 3 is 3, 3, 3, 2, 2, 2, 2, 2, 2, . . .. Similarly, let Q_{n} be the n-dimensional cube, then the sequence D(Q_{n}), starting with n = 2, is 3, 3, 3, 2, 2, 2, 2, 2, 2, …, which was proven independently by E. Friedgut; J. Smith; C. Tardif and G. Hahn. In contrast, A. Russell has shown us an infinite family of graphs, all with the same automorphism group, that all have distinguishing number 3; and we have discovered a family of cubic graphs (with increasing automorphism groups) which all have distinguishing number 3.

We had previously asked if | G |≥| Aut(G) |, and G was a graph with no 1-orbits, then was it the case that D(G) must be 2? However, A. Russell’s example mentioned above shows that this need not be true.

Open Questions

1. Is there a family of 4-regular graphs that each have distinguishing number 4?

2. Is there a family of 3-connected cubic graphs that each have distinguishing number 3?

3. Is there a family of graphs whose distinguishing numbers grow to k (for any integer k ≥ 4) and then go back down to 2?

4. What is D(S_{n})? We know 2, ⌈\sqrt{n}⌉, n are all contained in D(S_{n}) and that n is the largest element in D(S_{n}). Does D(S_{5}) contain 4? We conjecture that, in general, n − 1 ∉ D(S_{n}).

5. We conjecture that there is no group Γ such that D(Γ) = {2, 3, 4}.

6. We conjecture that any graph G such that Aut(G) ≅ S_{n} and D(G) = n must have a vertex orbit of size n which forms a complete subgraph.

References

[1] M. O. Albertson and K. L. Collins, Symmetry Breaking in Graphs, preprint.

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

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