A Note on Breaking the Symmetries of Tournaments

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

1. Introduction

A labeling of a graph G, ϕ : V (G) → {1, 2, …, r}, is said to be r-distinguishing if no automorphism of G preserves all of the vertex labels. We define the distinguishing number of a graph G by

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

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 Γ }

See [1, 2, 4, 5, 6, 10] for related results.

The purpose of this note is to introduce the conjecture below.

2. A conjecture on tournaments

Mike Saks asked:

Question 2.1. [11]. If Γ has no element of order k is D(Γ) bounded? In particular if Γ has no element of order 2 is D(Γ) = {2}?

Since a group of even order must have an involution, the second question above is really about odd order groups. All groups of odd order are solvable [7], hence it might seem reasonable to look at solvable groups. However, S_{3} is solvable, and D(S_{3}) = {2, 3}.

One special class of graphs that all have odd order automorphism groups are tournaments. The following conjecture surfaced several years ago.

Conjecture 2.2. If T is a tournament, then D(T) = 2.

Tournaments well represent the groups of odd order, since Babai and Imrich [3, 8] have shown that every odd order group (with two exceptions) has a tournament T which realizes the group as its autmorphism group. The tournaments described in their paper are all easily 2-distinguishable. Here is a simple argument that provides an upper bound on the distinguishing number of tournaments.

Theorem 2.3. Let T be a tournament on n vertices. Then T can be 1 + ⌈(\frac{⌈log(n)⌉}{2})⌉-distinguished.

Proof. Since the automorphism group of T has odd order, T contains no vertex orbits of size 2 (or any even size). Therefore, if 2 vertices u, v are both labeled i and no other vertices are labeled i, then both u and v must be fixed. We describe a (1 + (\frac{log(n)}{2}))-distinguishing labeling of T.

First we observe that in the subtournament induced by a vertex orbit O of T, indegree must equal outdegree. Choose a vertex v_{O} from each vertex orbit of T and label it 1. We will label at most two vertices in each original vertex orbit of T with 1, therefore each v_{O} must be fixed. Let A_{O} be the vertices in O which go in to v_{O} and B_{O} be the vertices in O which come from v_{O}. Then any automorphism ϕ that preserves the labeling of T must satisfy ϕ(A_{O}) = A_{O} and ϕ(B_{O}) = B_{O}. When one vertex in an orbit of a tournament is fixed, therefore, the rest of the vertices in the orbit fall into 2 or more smaller orbits, each less than or equal to half the size of the original. We proceed inductively on the new, smaller orbits of T by choosing a vertex from each new orbit and labeling it so that it must be fixed. By the first paragraph, we can use each label twice. One extra color is needed for the remaining vertices.

It would suffice to prove the conjecture for vertex transitive tournaments (that is, tournaments with exactly one vertex orbit). Such tournaments have indegree equal to outdegree for every vertex. Our final remark concerns a special case of vertex transitive tournaments.

Let S be a subset of {1, 2, 3, …, n − 1} such for any 1 ≤ k ≤ n − 1, k ∈ S if and only if n − k ∉ S. We say that T is a cyclic tournament [9] on n vertices with edge set given by S if the vertices of T are {0, 1, 2, …, n−1} and the edges of T are given by i goes to j if j−i ∈ S. For example, if n = 7 and S = {1, 2, 4}, the out-neighbors of 0 are 1, 2, 4 and the in-neighbors of 0 are 3, 5, 6. If 0 is labeled 1 while 1, 2, 3, 4, 5, 6 are labeled 2, then the tournament still has an automorphism that sends 1 → 2 → 4 → 1 and 6 → 3 → 5 → 1. This tournament can be 2-distinguished by labeling 0, 1 both 1 and the rest 2; or by labeling 0, 1, 2 all 1 and the rest 2.

Conjecture 2.4. If T is a cyclic tournament on n = 2t + 1 vertices, then T can be 2-distinguished by labeling 0, 1, 2, …, t − 1 with 1 and t, t + 1, …, 2k with 2.

References

[1] M. O. Albertson and K. L. Collins, Symmetry Breaking in Graphs, The Electronic Journal of Combinatorics, 3 (1996) #R18.

[2] M. O. Albertson and K. L. Collins, An introduction to symmetry breaking in graphs, Graph Theory Notes of New York XXX, New York Academy of Sciences, November 4, 1996.

[3] L. Babai and W. Imrich, Tournaments with given regular group, Aequationes math. 19 (1979) 232-244.

[4] C. Chan, K. L. Collins and D. Kleitman, Breaking the Symmetries of S5 and S6, preprint.

[5] C. T. Cheng, Local distinguishing numbers of trees, Congressus Numerantium 133 (1998) 21-30.

[6] C. T. Cheng and L. J. Cowen, On the local distinguishing numbers of cycles, Discrete Math. 196 (1999) 97-108.

[7] W. Feit and J. G. Thompson, Solvability of groups of odd order, Pacific J. Math. 13 (1963) 775-1029.

[8] C. D. Godsil, Tournaments with prescribed regular automorphism group, Aequationes Math. 30 (1986) 55-64.

[9] N. Ito, On cyclic tournaments, Hokkaido Math. J. 21 (1992) 273-277.

[10] A. Russell and R. Sundaram, A note on the asymptotics and computational complexity of graph distinguishability, The Electronic Journal of Combinatorics, 5 (1998) #R23 .

[11] M. Saks, personal communication.