Also available at http://amc.imfm.si
ISSN 1855-3966 (printed ed.), ISSN 1855-3974 (electronic ed.)
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 154–164
Small Label Classes in 2-Distinguishing Labelings
Debra L. Boutin
Hamilton College, Clinton, NY 13323, USA
Received 11 September 2007, accepted 25 November 2008, published online 29 November 2008
Abstract
A graph G is said to be 2-distinguishable if there is a labeling of the vertices with two
labels so that only the trivial automorphism preserves the labels. Call the minimum size of
a label class in such a labeling of G the cost of 2-distinguishing G and denote it by ρ(G).
This paper shows that for n ≥ 5, dlog2 ne + 1 ≤ ρ(Qn) ≤ 2dlog2 ne − 1, where Qn is the
hypercube of dimension n.
Keywords: Graph, distinguishing labeling, automorphism group.
Math. Subj. Class.: 05C15, 05C25
1 Introduction
A labeling of the vertices of a graph G with the integers 1, . . . , d is called a d-distinguishing
labeling if no nontrivial automorphism of G preserves the labels. A graph is called d-
distinguishable if it has a d-distinguishing labeling. Albertson and Collins introduced dis-
tinguishing in [2]. Recent work shows that large members of many infinite families of graphs
are 2-distinguishable. These graph families include hypercubes Qn with n ≥ 4 [3], non-
trivial Cartesian powers of a connected graph G 6= K2,K3 [8], Kneser graphs Kn:k with
n ≥ 6, k ≥ 2 [1], and (with seven small exceptions) 3-connected planar graphs [6]. Recently
Wilfried Imrich posed the following question: “What is the minimum number of vertices
in a label class of a 2-distinguishing labeling for the hypercube Qn?” This question can be
extended to any family of 2-distinguishable graphs.
LetG be a 2-distinguishable graph. Call a label class in a 2-distinguishing labeling ofG a
distinguishing class. Call the minimum size of such a class inG the cost of 2-distinguishingG
and denote it by ρ(G). The labeling provided forQn by Bogstad and Cowan in [3] shows that
for n ≥ 4, ρ(Qn) ≤ n+2. The best result known when Imrich posed the question mentioned
above was ρ(Qn) ≈
√
n [7]. For n ≥ 5, this paper shows that ρ(Qn) ≤ 2dlog2 ne − 1 and
that this is within a factor of two of a natural lower bound (discussed below). To give a sense
E-mail address: dboutin@hamilton.edu (Debra L. Boutin)
Copyright c© 2008 DMFA – založništvo
D. L. Boutin: Small Label Classes in 2-Distinguishing Labelings 155
of this result, note that though Q16 has 216 vertices and 16! × 216 automorphisms, it can be
distinguished, effectively eliminating all symmetry, by coloring just seven vertices red and
all others blue.
A significant tool used in this work is the determining set [4], a set of vertices whose
pointwise stabilizer is trivial. Albertson and Boutin showed that a graph is d-distinguishable
if and only if it has a determining set that is (d − 1)-distinguishable [1]. When d = 2 this
translates as: a graph is 2-distinguishable if and only if it has a determining set with the
property that any automorphism that preserves the set must fix it pointwise. This shows that
ρ(G) is bounded below by the size of a smallest determining set for G. For Qn this bound
is dlog2 ne+ 1 [5]. We will use the connection between determining sets and distinguishing
labelings, along with particular determining sets found in [5], to create a distinguishing class
for Qn that is smaller than twice this lower bound.
The paper is organized as follows. Definitions and facts about determining sets, Cartesian
products, and distinguishing labelings are given in Section 2. This section also sets out the
key idea tying together determining sets and distinguishing labelings. For n ≥ 5, Section 3
gives a set of 2dlog2 ne−1 vertices of Qn and proves that it is a distinguishing class. Section
4 lists some open questions.
2 Background
2.1 Determining Sets
Let G be a graph. A subset U ⊆ V (G) is said to be a determining set for G if whenever
g, h ∈ Aut(G) and g(x) = h(x) for all x ∈ U , then g = h. Thus every automorphism of
G is uniquely determined by its action on a determining set. Every graph has a determining
set since any set containing all but one vertex is determining. There are graphs, e.g. Kn
and K1,n, for which such a determining set is optimal or within one of being optimal. The
determining number of G, denoted here by Det(G), is the minimum r such that G has a
determining set of cardinality r.
Recall that the set stabilizer of U ⊆ V (G) is the set of all φ ∈ Aut(G) for which
φ(x) ∈ U for all x ∈ U . In this case we say that φ(U) = U . The pointwise stabilizer of U is
the set of all φ ∈ Aut(G) for which φ(x) = x for all x ∈ U . It is easy to see that U ⊆ V (G)
is a determining set for G if and only if the pointwise stabilizer of U is trivial.
2.2 Cartesian Products
Recall that the Cartesian product of graphs G and H , denoted by GH , has vertex set
V (G)× V (H) with an edge between vertices (x, u) and (y, v) if either x is adjacent to y in
G and u = v, or u is adjacent to v in H and x = y. The Cartesian power Hk is the Cartesian
product of H with itself k times.
A good reference for Cartesian products is [9]. Recall that H is prime with respect to
the Cartesian product if it cannot be written as the Cartesian product of two smaller graphs.
Further, every connected graph can be written uniquely (up to order) as the Cartesian product
of prime factors, G = G1  · · ·Gm.
Let U = {V1, . . . , Vr} be an ordered subset of vertices of G = G1  · · ·Gm. Let
M = MU be the r ×m matrix whose ith row contains the coordinates for Vi with respect
156 Ars Mathematica Contemporanea 1 (2008) 154–164
to the prime factor decomposition of G. Call this the characteristic matrix for U . Note
that the jth column of M consists of the jth coordinates of V1, . . . , Vr and can be denoted
[V1,j . . . Vr,j ]T . We say the jth and kth columns ofM , [V1,j . . . Vr,j ]T and [V1,k . . . Vr,k]T ,
are isomorphic images of each other if there exists an isomorphism ϕ : Gj → Gk so that
ϕ(Vi,j) = Vi,k for all i. These definitions allow us to state criteria for a set to be a determining
set as follows.
Lemma 1. [5] Let G be a connected graph and G = G1 · · ·Gm the prime factor decom-
position for G with respect to the Cartesian product. A set of vertices U is a determining set
for G if and only if each column of the characteristic matrix M for U contains a determining
set for the appropriate factor of G and no two columns of M are isomorphic images of each
other.
2.3 Distinguishing Labelings
A labeling f : V (G) → {1, . . . , d} is said to be d-distinguishing if φ ∈ Aut(G) and
f(φ(x)) = f(x) for all x ∈ V (G) implies that φ = id. Every graph has a distinguish-
ing labeling since each vertex can be assigned a distinct label. Furthermore, there are graphs,
e.g. Kn and K1,n, for which such a labeling is optimal or within one of being optimal. A
graph is called d-distinguishable if it has a d-distinguishing labeling.
We will also need to know what it means for a subset of vertices to be d-distinguishable.
Let U ⊆ V (G). A labeling f : U → {1, . . . , d} is called d-distinguishing if whenever
φ ∈ Aut(G) so that φ(U) = U and f(φ(x)) = f(x) for all x ∈ U then φ(x) = x for
all x ∈ U . Note that though such a φ fixes U pointwise, it is not necessarily trivial; it may
permute vertices in the complement of U . Then by definition, U is 1-distinguishable if every
automorphism that preserves U fixes it pointwise.
The following theorem ties together determining sets and distinguishing labelings and
facilitates the work in this paper.
Theorem 2. [1] A graph is d-distinguishable if and only if it has a determining set that is
(d− 1)-distinguishable.
In particular, suppose U is a 1-distinguishable determining set. The fact that it is 1-
distinguishable means that any automorphism that preserves U as a set also fixes it pointwise.
The fact that it is a determining set means that the only automorphism that fixes it pointwise
is the trivial automorphism. Thus if we label the vertices of U with ones and the vertices of
its complement with twos, only the trivial automorphism preserves the label classes. There-
fore U is a distinguishing class of a 2-distinguishing labeling. Thus to find a distinguishing
class, we will look for a (small) determining set for which no nontrivial automorphism both
preserves the set and permutes vertices within the set. One can think of such a set as having
no “internal symmetry.”
3 The Hypercubes
Recall that the n-cube, or hypercube of dimension n, is the Cartesian product of K2 with
itself n times. That is, Qn = Kn2 . Thus we can represent the vertices of Qn as strings of n
zeros and ones. For n ≥ 5 we will construct a distinguishing class of size 2dlog2 ne − 1 for
Qn. We will start by defining a set Ur ⊆ V (Q2r ) for r ≥ 3. In Theorem 5 we will show that
D. L. Boutin: Small Label Classes in 2-Distinguishing Labelings 157
Ur is indeed a distinguishing class for Q2r . In Theorem 6 we will show that if r = dlog2 ne
the same is true for the projection of Ur into Qn obtained by projecting each vertex onto its
first n coordinates.
First let us define Ur. For 0 ≤ k ≤ r, we call each of the 2r−k consecutive sequences of
2k coordinates in a vertex of Q2r a block of length 2k. For i = 1, . . . , r, let Vi be the vertex
of Q2r consisting of blocks of 2i−1 ones alternating with blocks of 2i−1 zeros. Let V0 be
the vertex with one in its second coordinate and zeros in all others. For i = 1, . . . , r − 2,
let Xi be the vertex of Q2r that agrees with Vi and Vi+1 on the coordinates in which they
agree and that has a one in every other coordinate. We can think of Xi as the “OR” of Vi and
Vi+1; it has a one in a coordinate if either Vi or Vi+1 has a one there, and a zero otherwise.
Alternately, Xi can be described as having the repeating pattern: three blocks of 2i−1 ones
followed by one block of 2i−1 zeros. Let U = Ur = {V0, . . . , Vr, X1, . . . , Xr−2}
Example 3. U4 contains the following vertices.
V0 = 0100000000000000
V1 = 1010101010101010
V2 = 1100110011001100
V3 = 1111000011110000
V4 = 1111111100000000
X1 = 1110111011101110
X2 = 1111110011111100
The proofs of Theorems 5 and 6 make extensive use of distances between elements of U .
Due to the repeating nature of the coordinates of our vertices, these distances are reasonable
to compute. The details are given below and are summarized in Table 1.
Consider d(Vi, Vj) where 1 ≤ i < j ≤ r. Each block of length 2j−1 in Vj (which con-
tains only zeros or only ones) corresponds to 2j−i blocks of length 2i−1 in Vi (which alternate
between ones blocks and zeros blocks). Thus Vi and Vj disagree in half their coordinates.
Therefore d(Vi, Vj) = 2r−1 for 1 ≤ i < j ≤ r.
Consider d(Xi, Vi) and d(Xi, Vi+1) where 1 ≤ i ≤ r−2. Note that since i ≥ 1, precisely
half the coordinates of Vi that disagree with Vi+1 are zeros and thus disagree with Xi also.
The same statement holds for Vi+1. Thus d(Xi, Vi) = d(Xi, Vi+1) = 12d(Vi, Vi+1) = 2
r−2
for 1 ≤ i ≤ r − 2.
Consider d(Xi, Xi+1) where 1 ≤ i ≤ r − 3. There are eight blocks of length 2i−1 in
Xi to every four blocks of length 2i of Xi+1. By comparing the repeating patterns of these
blocks we see that Xi and Xi+1 disagree on the 4th and 7th of these eight blocks. Thus
d(Xi, Xi+1) = 282
r = 2r−2 for 1 ≤ i ≤ r − 3.
Consider d(Xi, Xj) where 1 ≤ i ≤ j−2 ≤ r−4. Since i ≤ j−2, an integer multiple of
four blocks of Xi correspond to a single block of zeros or ones in Xj . The four block pattern
of Xi disagrees 14 of the time with a ones block of Xj and
3
4 of the time with a zeros block
of Xj . Since 34 of the blocks of Xj are ones and
1
4 are zeros, we get that Xi and Xj disagree
3
4 ·
1
4 +
1
4 ·
3
4 =
3
8 of the time. Thus d(Xi, Xj) = 3 · 2
r−3 for 1 ≤ i ≤ j − 2 ≤ r − 4.
Consider d(Xi, Vj) where 1 ≤ i ≤ j − 2 ≤ r − 2. Again since i ≤ j − 2, an integer
multiple of four blocks of Xi corresponds to a single block of Vj . The four block pattern of
158 Ars Mathematica Contemporanea 1 (2008) 154–164
Xi disagrees with ones blocks and zeros blocks as described above. However, Vj has half
its blocks ones and half zeros. Thus Xi and Vj disagree 12 ·
1
4 +
1
2 ·
3
4 =
1
2 the time. Thus
d(Xi, Vj) = 12 · 2
r = 2r−1 for 1 ≤ i ≤ j − 2 ≤ r − 2.
Consider d(Vi, Xj) where 1 ≤ i ≤ j− 1 ≤ r− 3. Since i ≤ j− 1, an integer multiple of
two blocks of Vi correspond to a single block of Xj . Such a pair of blocks disagrees with a
single block ofXj precisely half the time. Thus d(Xi, Vj) = 2r−1 for 1 ≤ i ≤ j−1 ≤ r−3.
Consider d(V0, Vi) where 1 ≤ i ≤ r. Since for i ≥ 1, Vi has exactly half of its coordinates
zero, if V0 consisted of all zeros we would have d(V0, Vi) = 2r−1. However since the second
coordinate of V0 is one, which disagrees with the second coordinate of V1 and agrees with all
other Vi we have that d(V0, V1) = 2r−1 + 1, and d(V0, Vi) = 2r−1 − 1 for 2 ≤ i ≤ r.
Consider d(V0, Xi) where 1 ≤ i ≤ r − 2. Because Xi has three blocks of ones followed
by one block of zeros, Xi has three quarters of its coordinates ones. Adjusting for the one in
the second coordinate of V0 yields d(V0, Xi) = 342
r − 1 = 3 · 2r−2 − 1 for 1 ≤ i ≤ r − 2.
Note that the only pairs of vertices of U at distance 2r−2 are {Xi, Vi}, {Xi, Vi+1}, and
{Xi, Xi+1}. We will call these related pairs because they have the distance relationship we
will use to show thatU is 1-distinguishable. Other pairs of vertices inU are called non-related
pairs.
Related Pairs
d(Xi, Vi) 2r−2 for 1 ≤ i ≤ r − 2
d(Xi, Vi+1) 2r−2 for 1 ≤ i ≤ r − 2
d(Xi, Xi+1) 2r−2 for 1 ≤ i ≤ r − 3
Non-Related Pairs
d(V0, Xi) 3 · 2r−2 − 1 for 1 ≤ i ≤ r − 2
d(V0, V1) 2r−1 + 1
d(Vi, Vj) 2r−1 for 1 ≤ i < j ≤ r
d(Xi, Vj) 2r−1 for 1 ≤ i ≤ r − 2, 1 ≤ j ≤ r,
j 6= i, i+ 1
d(V0, Vi) 2r−1 − 1 for 2 ≤ i ≤ r
d(Xi, Xj) 3 · 2r−3 for 1 ≤ i ≤ j − 2 ≤ r − 4
Table 1: Distances in Q2r
Before stating and proving Theorem 5, we will prove that U is a determining set for Q2r .
By Lemma 1, U is a determining set for Q2r if and only if each column of the characteristic
matrix for U contains a determining set for its associated prime factor and no two columns
are isomorphic images of each other. Since any single vertex is a determining set for K2,
here we need only show that no two columns of MU are isomorphic images of each other.
Let MU be the characteristic matrix for U = {V0, . . . , Vr, X1, . . . , Xr−2} and MT the
D. L. Boutin: Small Label Classes in 2-Distinguishing Labelings 159
characteristic matrix for T = {V0, . . . , Vr}. Note that the matrix MT is given by the first
r + 1 rows of MU . See Example 4 for MU in the case r = 4.
Example 4. The characteristic matrix for U4.
V0
V1
V2
V3
V4
X1
X2

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0
1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0

By the proof of [5, Theorem 3], if we take T and replace V0 with the vertex of all zeros, we
get a determining set for Q2r . This means that if we change the entry in the first row second
column of MT to a zero, we would have a characteristic matrix in which no pair of columns
are isomorphic images of each other. Thus in MT the only pairs of columns that might be
isomorphic images of each other are pairs involving the second column. Note that the second
column, [1 0 1 1 · · · 1]T , and the (2r−1)st column, [0 1 0 0 · · · 0]T , are isomorphic images
of each other under the isomorphism (0 1) of K2. (Thus T is not a determining set.) If there
was another column of MT isomorphic to the second, it would also be isomorphic to the
(2r − 1)st, which we argued cannot happen. Thus the second and (2r − 1)st columns are the
only pair of columns of MT that are isomorphic images of each other.
Since the first r+1 rows of MU form MT , if two columns of MU are isomorphic images
of each other, then so are the corresponding columns in MT . Thus we only need to check the
second and (2r − 1)st columns of MU . We have seen that the first r+ 1 entries in the second
and (2r − 1)st of these columns are isomorphic images of each other under the isomorphism
(0 1). However, since r ≥ 3, X1 exists, provides the (r + 2)nd row of MU , and has one in
each of its second and (2r−1)st coordinates. Thus the isomorphism does not continue to the
(r + 2)nd entries of these columns. Thus no two columns of MU are isomorphic images of
each other and therefore U is a determining set for Q2r .
We now have the machinery in place to prove that Ur is a distinguishing class for Q2r .
Theorem 5. If r ≥ 3, then Q2r has a distinguishing class of size 2r − 1.
Proof. Define U = Ur ⊂ Q2r as above. Define the distance relationship graph on U , de-
noted GU , to be the graph with vertex set U and with edges between two vertices if their
distance in Q2r is 2r−2. The related pairs, {Xi, Vi}, {Xi, Vi+1}, and {Xi, Xi+1}, are pre-
cisely those that are adjacent in the distance relationship graph. In particular, in this distance
relationship graph V0 and Vr are isolated vertices, V1 and Vr−1 have degree one, V2, . . . , Vr−2
have degree two, X1, . . . , Xr−2 have degree greater than two, and there is a connected com-
ponent induced by V1, . . . , Vr−1, X1, . . . , Xr−2 that has Z2 symmetry. See Figure 1 for an
illustration when r = 6.
Since automorphisms necessarily preserve distance, any automorphism in the set stabi-
lizer ofU induces an automorphism of the distance relationship graph. But the only nontrivial
actions on GU either transpose V0 and Vr, or reflect the nontrivial connected component and
therefore transpose V1 and Vr−1, or both. Thus any automorphism that preserves U setwise
either transposes V0 and Vr, or V1 and Vr−1, (or both).
160 Ars Mathematica Contemporanea 1 (2008) 154–164
tV1
tV2
tV3
tV4
tV5tX1
t
X2
t
X3 tX4
t
V0
t
V6

L
L
L
L aa
aa










A
A
A
A
!!
!!




@
@PPP
Figure 1: Distance Relationship Graph for U6
However, for any i, 1 ≤ i ≤ r − 2, d(V0, Xi) = 3 · 2r−2 − 1 while the distance
between Vr and any vertex of U −{V0, Vr} is 2r−1. Thus V0 achieves distances with vertices
of U − {V0, Vr} that are strictly greater than those achieved by Vr. Since automorphisms
preserve distance, no automorphism that preserves U can transpose V0 and Vr. Thus V0 is
distinguished from Vr within U . Further, d(V0, V1) = 2r−1 +1 and d(V0, Vr−1) = 2r−1−1.
Again, since automorphisms preserve distance, no automorphism in the set stabilizer of U
can transpose V1 and Vr−1. Thus V1 and Vr−1 are distinguished within U .
Thus any automorphism that preserves U must fix U pointwise. Thus U is 1-distinguish-
able. Recall that before beginning Theorem 5 we proved that U is a determining set. Thus U
is a 1-distinguishable determining set, i.e. a distinguishing class, of size 2r − 1 for Q2r .
If 2r−1 < n < 2r we will find the desired distinguishing class by projecting Ur into Qn.
The proof that the result is a distinguishing class for Qn is similar to, but more complex than,
the proof for Q2r .
Theorem 6. If n ≥ 5, then Qn has a distinguishing class of size 2dlog2 ne − 1.
Proof. By Theorem 5, we get the desired result when n = 2r for r ≥ 3. For n ≥ 5 and not
a power of two, there is some r ≥ 3 for which 2r−1 < n < 2r. For such an n, let pn be the
projection ofQ2r ontoQn by projecting each vertex onto its first n coordinates. Let U = Ur.
Here our goal is to show that pn(U) is a 1-distinguishable determining set for Qn. Note that
the characteristic matrix for pn(U) is formed from the first n columns of the characteristic
matrix for U . Since we showed that no two columns in MU are isomorphic images of each
other, no two columns in Mpn(U) are isomorphic images of each other. Thus pn(U) is a
determining set for Qn.
Consider the possible distances between vertex pairs in Qn. When we project vertices,
sayX and Y , fromQ2r intoQn (or fromQn intoQ2r−1 ) by dropping the appropriate number
of rightmost coordinates, we are dropping coordinates in which these vertices may disagree.
Thus the distances between projected vertices can only get smaller. In particular the projec-
tion of each related pair ofU has distance less than or equal to 2r−2 inQn. Moreover, we con-
clude that the distance d(pn(X), pn(Y )) falls between the distance d(p2r−1(X), p2r−1(Y ))
and the distance d(X,Y ) (in Q2r ). Again distances in Q2r−1 are not hard to find due to the
repeating nature of the coordinates of our vertices. They are contained in Table 2.
D. L. Boutin: Small Label Classes in 2-Distinguishing Labelings 161
Projection of Related Pairs
d(pn(Xi), pn(Vi)) 2r−3 for 1 ≤ i ≤ r − 2
d(pn(Xi), pn(Vi+1)) 2r−3 for 1 ≤ i ≤ r − 2
d(pn(Xi), pn(Xi+1)) 2r−3 for 1 ≤ i ≤ r − 3
Projection of Non-Related Pairs
d(pn(V0), pn(Vr)) 2r−1 − 1
d(pn(V0), pn(Xi)) 3 · 2r−3 − 1 for 1 ≤ i ≤ r − 2
d(pn(V0), pn(V1)) 2r−2 + 1
d(pn(Vi), pn(Vj)) 2r−2 for 1 ≤ i < j ≤ r
d(pn(Xi), pn(Vj)) 2r−2 for 1 ≤ i ≤ r − 2,
1 ≤ j ≤ r − 1,
j 6= i, i+ 1
d(pn(V0), pn(Vi)) 2r−2 − 1 for 2 ≤ i ≤ r − 1
d(pn(Xi), pn(Xj)) 3 · 2r−4 for 1 ≤ i ≤ j − 2 ≤ r − 4
d(pn(Vr), pn(Xi)) 2r−3 for 1 ≤ i ≤ r − 2
Table 2: Distances of projections into Qn, where n = 2r−1
Suppose that the projection of some related pair has distance 2r−2 in Qn. Since this
was also their distance in Q2r this means that the original pair agreed in each of their final
2r−n coordinates. Examining the final blocks of the related pairs we find that the maximum
agreement is 2r−2 coordinates and occurs only for {Xr−2, Vr−2}. In particular if n < 3·2r−2
then every related pair is at distance less than 2r−2.
We will break this proof into two cases: Case 1: 3 · 2r−2 ≤ n < 2r and Case 2: 2r−1 <
n < 3·2r−2. In each case we will define a distance relationship graph on the vertex set pn(U)
similar to the one defined in the proof of Theorem 5. In Case 1 the distance relationship will
be “less than or equal to 2r−2 ” while in Case 2 the distance relationship will be “strictly less
than 2r−2.” These definitions will ensure that related pairs will be adjacent in each distance
relationship graph.
By Table 2, the non-related vertices that cannot possibly have distance less than or equal
to 2r−2 in Qn where 2r−1 < n < 2r are the pairs {pn(V0), pn(Vr)}, {pn(V0), pn(Xi)}
where 1 ≤ i ≤ r − 2, and {pn(V0), pn(V1)}. We will analyze the distances between the
projections of all other non-related pairs using their distances when projected into Q3·2r−2 .
These are given in Table 3.
Case 1: 3 · 2r−2 ≤ n < 2r.
When 3 · 2r−2 ≤ n < 2r, define the distance relationship graph Gpn(U) on pn(U) so
that there is an edge between a pair of vertices when their distance is less than or equal to
2r−2. Since all related pairs fit this distance criterion, Gpn(U) contains GU (from the proof
of Theorem 5) as a subgraph. The distance information from Table 3 allows us to conclude
that since n ≥ 3 · 2r−2 the only edges that might be in Gpn(U) but are not in GU would be
162 Ars Mathematica Contemporanea 1 (2008) 154–164
Projection of Some Non-Related Pairs
d(pn(Vr−1), pn(Vr)) 2r−1
d(pn(V0), pn(Vr−1)) 2r−1 − 1
d(pn(Vi), pn(Vj)) 3 · 2r−3 for 1 ≤ i < j ≤ r, i 6= r − 1
d(pn(Xi), pn(Vj)) 3 · 2r−3 for 1 ≤ i ≤ r − 2,
1 ≤ j ≤ r − 2,
j 6= i, i+ 1
d(pn(Vr), pn(Xr−2)) 3 · 2r−3
d(pn(V0), pn(Vi)) 3 · 2r−3 − 1 for 2 ≤ i ≤ r − 2
d(pn(Xi), pn(Vr−1)) 5 · 2r−4 for 1 ≤ i ≤ r − 3,
d(pn(Vr), pn(Xi)) 5 · 2r−4 for 1 ≤ i ≤ r − 3
d(pn(Xi), pn(Xj)) 9 · 2r−5 for 1 ≤ i ≤ j − 2 ≤ r − 5
d(pn(Xi), pn(Xr−2)) 2r−2 for 1 ≤ i ≤ r − 4
Table 3: Some distances of projections into Qn, where n = 3 · 2r−2
between the pairs of the form {pn(Xr−2), pn(Xi)} where 1 ≤ i ≤ r − 4. Thus in Gpn(U)
the only vertices of degree zero are pn(V0) and pn(Vr), the only vertices of degree one are
pn(V1) and pn(Vr−1), and the vertices of degree two are precisely the vertices pn(Vi) where
2 ≤ i ≤ r − 2.
Recall that since Gpn(U) is defined by distances in Qn, to prove that pn(G) is 1-dis-
tinguishable in Qn we can use information from Qn itself and information from Gpn(U).
Notice that in both V0 and Vr the second 2r−1 coordinates are zeros. In particular, their
second 2r−1 coordinates are the same. Thus distances involving V0 and Vr are reduced by the
same amount in the projection toQn. Thus pn(V0) still attains greater distances with vertices
of pn(U)−{pn(V0), pn(Vr)} than pn(Vr) can attain. Since automorphisms preserve distance,
pn(V0) and pn(Vr) cannot be transposed by any automorphism that preserves pn(U). (Note
that this is true for any 2r−1 < n < 2r; it will be used again in Case 2.) Thus we can
distinguish pn(V0) and pn(Vr) in pn(U).
If pn(V1) and pn(Vr−1) have different distances from pn(V0) then they are distinguished
from each other. However, if pn(V1) and pn(Vr−1) have the same distance from pn(V0), we
can replace V0 (and pn(V0)) with the vertex of all zeros. This does not change any argument
given so far. (The only possible concern is the distance between pn(V0) and pn(V1). With the
change to V0, when n = 2r−1 the distance between pn(V0) and pn(V1) drops to 2r−2, which
gives pn(V0) a neighbor in the distance relationship graph. However, since V0 and V1 differ
in their (2r−1 +1)st coordinate, when n > 2r−1 their distance is still greater than 2r−2.) The
change in V0 will decrease the distance between pn(V0) and pn(V1) by one and increase the
distance between pn(V0) and pn(Vr−1) by one, thereby distinguishing pn(V1) and pn(Vr−1).
Again, since the only requirement is that n > 2r−1, this argument will still be valid in Case
2.
The vertex pn(X1) (resp. pn(Xr−2)) is the only one adjacent to the vertex pn(V1) (resp.
pn(Vr−1)) in Gpn(U). Thus pn(X1) and pn(Xr−2) are distinguished. The vertex pn(V2)
(resp. pn(Vr−2)) is the only vertex of degree 2 at distance 2 from pn(V1) (resp. pn(Vr−1))
in Gpn(U). Thus these are also distinguished.
D. L. Boutin: Small Label Classes in 2-Distinguishing Labelings 163
The vertex pn(X2) (resp. pn(Xr−3)) is the only one adjacent to both pn(X1) and pn(V2)
(resp. pn(Xr−2)) and pn(Vr−2)) in Gpn(U); thus they are distinguished. Continue in this
manner to see that all vertices inGpn(U) are distinguished. Thus pn(U) is a 1-distinguishable
determining set.
Note that in the argument above we distinguished all of pn(U)−{pn(Vr)} without using
the fact that pn(Vr) was itself distinguished. Once pn(V0) was distinguished, the remainder
of pn(U) − {pn(V0), pn(Vr)} could be distinguished. This results in the distinguishing of
pn(Vr) by elimination. This argument will be used again in Case 2 below.
Case 2: 2r−1 < n < 3 · 2r−2.
When 2r−1 < n < 3·2r−2 define the distance relationship graphGpn(U) on pn(U) so that
there is an edge between a pair of vertices when their distance is strictly less than 2r−2. Recall
that the distances between related pairs have dropped strictly below 2r−2 since n < 3 · 2r−2.
Table 2 indicates that the distance between a pair of the form {p2r−1(V0), p2r−1(Vi)} for
2 ≤ i ≤ r − 2 is 2r−2 − 1 in Q2r−1 . However, V0 and Vi differ in their (2r−1 + 1)st
coordinate. Thus the distance between their projections in Qn is at least 2r−2. From Table 2
we see that the only other non-related pairs of vertices that might have distance smaller than
2r−2 in Qn are the pairs {pn(Xi), pn(Xj)} where 1 ≤ i ≤ j − 2 ≤ r − 4 and the pairs
{pn(Vr), pn(Xi)} where 1 ≤ i ≤ r − 2. Thus we see that in Gpn(U), pn(V0) still has degree
zero, pn(V1) and pn(Vr−1) still have degree one, and pn(Vi) with 2 ≤ i ≤ r − 2 still have
degree two. Further pn(Xi) with 1 ≤ i ≤ r − 2 still have degree greater than two. However,
the degree of pn(Vr) varies depending on the value of n.
If the degree of pn(Vr) in Gpn(U) is greater than zero, then pn(V0) is the only vertex of
degree zero and is thus distinguished.
Suppose the degree of pn(Vr) in Gpn(U) is zero. Then pn(V0) and pn(Vr) are the only
vertices of degree zero in Gpn(U). Thus any automorphism that preserves pn(U) either fixes
them both or transposes them. However, the argument given in Case 1 shows that when
2r−1 < n < 2r, we can distinguish pn(V0) and pn(Vr) by the distances they attain.
Thus in either case, pn(V0) is distinguished and we can use the arguments of Case 1 to
distinguish the remaining vertices of pn(U).
Thus we have found a 1-distinguishable determining set, i.e. a distinguishing class, of
size 2r − 1 = 2dlog2 ne − 1 for Qn.
Corollary 7. For n ≥ 5, dlog2 ne+ 1 ≤ ρ(Qn) ≤ 2dlog2 ne − 1.
Proof. By the remarks following Theorem 2, every distinguishing class for Qn, n ≥ 4, is
also a determining set. By [5] a smallest such set for Qn has size dlog2 ne+1. This provides
the lower bound.
The only 2-distinguishable case for Qn that is not covered in Theorem 6 is Q4. The proof
technique fails in this case because the given set U has no Xi when n < 5. If the results of
Theorem 6 held for Q4, it would have a distinguishing class of size three. Since three is also
the determining number for Qn, such a distinguishing class would also be a minimum size
determining set. It is not hard to show that there is a single isomorphism class of minimum
size determining sets for Q4, and that one of its members, U = {0000, 1010, 1100}, has a
164 Ars Mathematica Contemporanea 1 (2008) 154–164
nontrivial set stabilizer. Thus every minimum size determining set for Q4 has a nontrivial
stabilizer and therefore cannot be a distinguishing class.
Thus the result of Theorem 6 does not hold for n < 5.
4 Open Questions
Question 8. For n ≥ 5 is there a distinguishing class for Qn that is smaller than 2dlog2 ne−
1?
Question 9. For n ≥ 5 we saw that ρ(Qn) is no bigger than a constant multiple of Det(Qn).
That is, ρ(Qn) = O(Det(Qn)) in this case. For what other infinite families of graphs is this
true?
5 Acknowledgments
The author thanks Wilfried Imrich for useful conversations about determining sets and dis-
tinguishing labelings of Cartesian products. The author also thanks the referees for finding
a computational error in the original proof of Theorem 6 and for a careful reading of the
manuscript.
References
[1] M. O. Albertson and D. L. Boutin, Using determining sets to distinguish Kneser graphs, Electron.
J. Combin. 14 (2007), #R20.
[2] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996),
#R18.
[3] B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube, Discrete Math. 283
(2004), 29–35.
[4] D. L. Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin. 13
(2006), #R78.
[5] D. L. Boutin, The determining number of Cartesian products, J. Graph Theory, forthcoming.
[6] T. Fukuda, S. Negami and T. Tucker, 3-connected planar graphs are 2-distinguishable with few
exceptions, preprint, 2006.
[7] W. Imrich, personal communication.
[8] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006),
250–260.
[9] W. Imrich and S. Klavžar, Product graphs, Wiley-Interscience Series in Discrete Mathematics and
Optimization, Wiley-Interscience, New York, 2000.