Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 159–173
Distinguishing numbers of Cartesian products of
multiple complete graphs
Michael J. Fisher ∗
West Chester University, Department of Mathematics, West Chester, PA 19383, USA
Garth Isaak
Lehigh University, Department of Mathematics, Bethlehem, PA 18015, USA
Received 1 July 2010, accepted 3 October 2011, published online 1 February 2012
Abstract
We examine the distinguishing number of the Cartesian product of an arbitrary number
of complete graphs. We show that for u1 ≤ · · · ≤ ud the distinguishing number of the
Cartesian product of complete graphs of these sizes is either du1/sd e or du
1/s
d e + 1 where
s = Πd−1i=1 ui. In most cases, which of these values it is can be explicitly determined.
Keywords: Cartesian product, complete graph, distinguishing number.
Math. Subj. Class.: 05C78, 20B25, 68R10
1 Introduction
The distinguishing number of a graph is the minimum number of labels needed so that
the only label preserving automorphism is the identity automorphism. The distinguishing
number was introduced by Albertson and Collins in [2]. Albertson [1] observed that the
distinguishing number of powers (with respect to Cartesian product) of complete graphs
provides an upper bound on the distinguishing number of powers of prime graphs. (Formal
definitions will be given in the next section.)
Building on results [3] that the hypercube has distinguishing number 2, Albertson [1]
showed that that distinguishing number of the dth power of a complete graph is 2 when
d ≥ 4. This result was extended in [10] and [9] showing that Cartesian powers of complete
graphs have distinguishing number 2 except for squares and cubes of K2 and the square
of K3 all of which have distinguishing number 3. We will look more generally at the
distinguishing number of Cartesian products of complete graphs of different sizes.
∗Corresponding author.
E-mail addresses: mfisher@wcupa.edu (Michael J. Fisher), gisaak@lehigh.edu (Garth Isaak)
Copyright c© 2012 DMFA Slovenije
160 Ars Math. Contemp. 5 (2012) 159–173
For products of graphs of different sizes, the distinguishing number of the Cartesian
product of complete graphs on u1 and u2 vertices for u1 ≤ u2 was examined in [5] and
[7]. It is either du1/u12 e or du
1/u1
2 e+ 1. In ‘most’ cases which value it is can be determined
explicitly and in a few cases it can be determined using a recursion.
More generally one can talk about the distinguishing number of a group acting on a set
as the minimum number of labels needed so that the only label preserving group element
is the identity. When the group is the group of automorphisms of a graph and the set is
the vertex set this is the distinguishing number of the graph. Chan [4] examined Sm × Sn
acting on [m]×[n]. Whenm 6= n this is the distinguishing number of the Cartesian product
of complete graphs of size m and n hence the results in the previous paragraph apply.
In this paper, we examine the distinguishing number of the Cartesian product of com-
plete graphs of sizes u1 ≤ u2 ≤ · · · ≤ ud. As a tool we will use the closely related distin-
guishing number of the group Su1 × Su2 × · · · × Sud acting on [u1] × [u2] × · · · × [ud].
These are identical problems when the ui are distinct. We will show the following. Except
for d = 2 with u1 = u2 = 2 or u1 = u2 = 3 and d = 3 with u1 = u2 = u3 = 2 these
two distinguishing numbers are the same. This distinguishing number is either du1/sd e or
du1/sd e + 1 where s = Π
d−1
i=1 ui. As with the case d = 2, in ‘most’ cases which value it is
can be determined explicitly and in a few cases it is can be determined using a recursion.
Our proof uses induction via two basic reduction lemmas. The switching lemma extends a
version for the Cartesian product of 2 complete graphs and reduces the sizes of the ui. The
collapsing lemma reduces the ‘dimension’, the number d of factors.
A relatively simple argument for the lower bound, du1/sd e, is the following. For a c-
coloring f of GKu let fv be a coloring of G given by fv = f(x, v). If u > cs there
must be two vertices v, v′ in Kn with fv = fv′ . Then the automorphism that is constant
on G coordinates and transposing v and v′ is label preserving. Hence, the distinguishing
number is at least u1/s and, since it is integral, at least du1/se. Then apply this with
G = Ku1 · · ·Kud−1 . This approach is found in our Lemma 4.3 as well as earlier papers
on distinguishing numbers of Cartesian products. The nice description above is suggested
by an anonymous referee.
The upper bound du1/se + 1 for Cartesian powers of general graphs follows from the
upper bound observation noted above on powers of complete graphs (see also Observation
2.5 below and the comments surrounding it) and our upper bound in Corollary 5.1. When
s < ud we do not need our Corollary 5.1 as it follows from the upper bound on Cartesian
products of two complete graphs upper bound found independently in [5] and [7].
Hence, the main work in our proof covers the cases ud ≤ s. As du1/sd e ≤ 2 for
0 ≤ ud ≤ s, we are establishing an upper bound of 3 on the distinguishing number in these
cases. We work with general c rather than c = 2 needed for ud ≤ s since, in addition,
our proof establishes exactly which of the two bounds holds for ‘most’ cases of Cartesian
products of complete graphs. It is also interesting to note that the determination of the exact
value of the distinguishing number depends only on ud, ud−1 and the product Πd−2j=1uj .
2 Definitions and background
We begin with basic definitions.
Definition 2.1 (Distinguishing Labeling). Given a set V and a group H acting on V , a
labeling ` : X → {1, 2, . . . , c} is c-distinguishing if only the identity preserves the labels.
M. J. Fisher and G. Isaak: Distinguishing numbers of Cartesian products. . . 161
When the set V is the vertex set of a graph and the group is the automorphisms of the graph
we will call this a distinguishing labeling of the graph.
Definition 2.2 (Distinguishing Number). Given a set V and a group H acting on V , the
distinguishing number DH(V ) is the smallest c such that there is a c-distinguishing label-
ing. For graph automorphisms, Aut(G) acting on a graphG with vertex set V we will write
D(G) instead of DAut(G)(V ) and refer to the distinguishing number of the graph.
Definition 2.3. The Cartesian product of graphs G1 and G2 on vertex sets V1 and V2
respectively, denoted G1G2, is the graph with vertex set V1 × V2 and an edge between
(u1, u2) and (v1, v2) if and only if either u1 = v1 and u2v2 is an edge of G2 or u2 = v2
and u1v1 is an edge of G1. Multiple powers are defined inductively G1G2 · · ·Gd =
(G1 · · ·Gd−1)Gd.
The dth Cartesian power of a graph is the product of d copies of the graph. That is,
Gd = GGd−1 with G2 = GG. A graph G is prime with respect to Cartesian product if
whenever G = G1G2, then either G1 or G2 is the trivial graph with a single vertex.
The operation  is associative and commutative. Graphs have unique prime factor-
izations G = G1 · · ·Gd where each Gi is prime. Graphs G1 and G2 are said to be
relatively prime if they do not share a common factor.
In order to simplify notation, we will use the following terminology to distinguish the
two closely related distinguishing labeling problems that we will examine.
For a Cartesian product Ku1Ku2 · · ·Kud of complete graphs, we can identify
the vertices with d-tuples from [u1] × [u2] × · · · × [ud] with two vertices adjacent if
and only if they agree on exactly d − 1 coordinates. We can think of a c-labeling as
an array of size u1, u2, . . . , ud with entries from [c]. By the Imrich and Miller result
noted below, automorphisms correspond to permutations of entries within each dimen-
sion along with ‘transposes’ of same size dimensions. For simplicity in notation, we will
refer to this set and group of automorphisms as an array of size u1, u2, . . . , ud and write
D(Array(u1, u2, . . . , ud)) for the distinguishing number.
For distinguishing labelings of Su1 × Su2 × · · · × Sud acting on [u1] × [u2] × · · · ×
[ud], we can think of the elements as d-tuples from [u1] × [u2] × · · · × [ud]. The group
actions correspond to permutations of entries within each dimension. Unlike the previous
paragraph, ‘transposes’ of same size dimensions do not occur. For simplicity in notation
we will refer to this set and group of automorphisms as a grid of size u1, u2, . . . , ud and
write D(Grid(u1, u2, . . . , ud)) for the distinguishing number.
For completeness, we make the following trivial observations which follow from the
fact that the group acting on the grids is a subgroup of that acting on the arrays.
Observation 2.4. If the array of size u1, u2, . . . , ud has a distinguishing c-coloring, then
the grid of size u1, u2, . . . , ud has a distinguishing c-coloring. The distinguishing number
of the grid of size u1, u2, . . . , ud is at most the distinguishing number of the array of size
u1, u2, . . . , ud. That is, D(Grid(u1, u2, . . . , ud)) ≤ D(Array(u1, u2, . . . , ud)).
As noted above, the distinguishing numbers of arrays and grids of the same size will
be shown to be equal except in the following three cases: d = 2 with u1 = u2 = 2
or with u1 = u2 = 3 and d = 3 with u1 = u2 = u3 = 2. In each of these small
cases, it is straightforward to check that the grid distinguishing number is 2 and the array
distinguishing number is 3. For arrays, the first two are noted in [3] and the third in [9].
162 Ars Math. Contemp. 5 (2012) 159–173
For grids, the first two are noted in [4] and for the third, observe that the [2] × [2] × [2]
grid with with entries ai,j,1 given by
[
1 2
2 2
]
and entries ai,j,2 given by
[
1 1
1 1
]
is
2-distinguishing.
A result shown independently by Imrich and Miller (see [8]) is that if G is connected and
G = G1 · · ·Gd is its prime decomposition, then every automorphism of G is generated
by the automorphisms of the factors and the transpositions of isomorphic factors. Using
this we make the following observation which extends those of Albertson [1] and Imrich,
Jerebic, and Klavžar [7]. As with the Observation 2.4, it follows as the group acting on the
vertex set of the graph is a subgroup of that acting on the array.
Observation 2.5. If G = G1G2 · · ·Gd with the Gi relatively prime and |V (Gi)| =
ui, then D(G1G2 · · ·Gd) ≤ D(Array(u1, u2, . . . , ud)).
As a consequence of our results, we will see that D(Array(u1, . . . , ui−2, ui−1, ui,
ui+1, . . . , us)) ≤ D(Array(u1, . . . , ui−2, (ui−1ui), ui+1, . . . , us)). Thus, if the sizes
of the factors in the prime factorization of G1G2 · · ·Gd are u1, u2, . . . , ud′ , then
D(G1G2 · · ·Gd) ≤ D(Array(u1, u2, . . . , ud′)). Hence, we can drop the relatively
prime assumption in Observation 2.5.
We will also use the following definitions and notation. Examples of switching and
collapsing in 2 dimensions are described in the next section.
For automorphisms of grids we will write (π1, π2, . . . , πd) where πi is a permutation
of [ui]. For arrays we will write automorphisms as (σ;π1, . . . , πd) where the πi are as
for grids and σ is a permutation of [d] (such that only positions with equal sizes can be
permuted). We will apply the πi first and then permute the dimensions.
Definition 2.6 (Switching). For a c-labeling A with entries a(i1, i2, . . . , id) of an array
(grid) of size u1, u2, . . . , ud, the dimension i subarrays are the (d − 1) dimensional ar-
rays Ak of size (u1, . . . , ui−1, ui+1, . . . , ud) given by ak(j1, . . . , ji−1, ji+1, . . . , jd) =
a(j1, . . . , ji−1, k, ji+1, . . . , jd) for k = 1, 2, . . . , ui.
If A is a c-labeling of an array of size u1, u2, . . . , ud and the dimension i subarrays are
distinct, then the dimension i complementA∗i is the size u1, . . . , ui−1, c
p−ui, ui+1, . . . , ud
array where p = u1 · · ·ui−1ui+1 · · ·ud, whose set of dimension i subarrays is the set of all
c labelings of arrays of size (u1, . . . , ui−1, ui+1, . . . , ut) that do not appear as dimension i
subarrays of A.
For example, in two dimensions the dimension 1 subarrays are the rows and the dimen-
sion 2 subarrays are the columns. Also, in two dimensions, the dimension 2 complement
A∗2 is the size (u1, c
u1 −u2) array consisting of all ‘possible’ columns (size u1 strings with
entries from [c]) that do not appear in A.
Technically, the complement would depend on the ordering of the complementary sub-
arrays but as this will not affect what we do we will assume some fixed ordering and refer
to ‘the’ complement.
Definition 2.7 (Collapsing). For a c-labeling A with entries a(i1, i2, . . . , id) of an array
of size u1, u2, . . . , ud and S = {k + 1, . . . , d} the array AS obtained by collapsing the
dimensions in S has d − |S| + 1 dimensions with sizes (u1, u2, . . . , uk, q) where q =
uk+1 · · ·ud. It is defined as follows: Let g be any bijection from [uk+1] × · · · × [ud] to
[uk+1 · · ·ud]. The entries of AS are then aS(j1 . . . , jk, g) = a(j1, . . . , jk, jk+1, . . . , jd)
where g = g(jk+1, . . . , jd).
M. J. Fisher and G. Isaak: Distinguishing numbers of Cartesian products. . . 163
For any subset S ⊂ [d] of indices, the array AS obtained by collapsing the dimensions
in S is defined in a similar manner and has d− |S|+ 1 dimensions with sizes ui for i 6∈ S
and one dimension of size Πi∈Sui.
Technically, the collapse would depend on the choice of g but as this will not affect
what we do we will assume some fixed g and refer to ‘the’ collapse.
3 Reduction lemmas
We will make use of two basic lemmas to relate distinguishing labelings of one size to
another. This will allow for induction to determine values of c for which arrays and grids
of given sizes have distinguishing c-labelings.
Consider a c-labeling A of the size u1, u2 grid with distinct columns. The dimension 2
complement A∗2 has size u1, c
u1 −u2 and consists of all cu1 −u2 possible columns that do
not appear in A. An automorphism (π1, π2) of A that preserves labels maps the columns
of A to columns of A under π1. Hence, applying π1 to A∗2 must map columns of A
∗
2 to
columns ofA∗2. So we can find a permutation π
′
2 of [c
u1−u2] so that (π1, π′2) is a automor-
phism of A∗2 that preserves labels. So, we observe that there is a distinguishing labeling of
the size u1, u2 grid if and only if there is a distinguishing labeling of the size u1, cu1 − u2
grid. For arrays, we get the same result except that when u1 = u2 there is the possibility
of an automorphism that transposes rows and columns of A that does not correspond to an
automorphism of A∗2. So, in this case, we get only that if there is a distinguishing labeling
of the size u1, cu1 − u2 array and u1 6= u2, then there is a distinguishing labeling of the
size u1, u2 array. This idea will be presented as the switching lemma below.
The idea in the switching lemma (in two dimensions) below has appeared in a number
of earlier papers on distinguishing number. It appears in some form (at least) in [4], [5], [7]
[9] and [6]. We use the name switching lemma given in [7].
For simplicity in notation, we state the following lemma for switching in dimension d.
By permuting the labels on the dimensions, a similar statement holds for switching on any
dimension. We state versions for both grids and arrays. The proofs are essentially the same
as in the two dimensional case. For completeness, we give a proof for the grid version.
Lemma 3.1 (Grid Switching Lemma). Let u1 ≤ u2 ≤ · · · ≤ ud with ud < cp where
p = u1u2 · · ·ud−1. There is a c-distinguishing labeling of a grid of size u1, u2, . . . , ud if
and only if there is a c-distinguishing labeling of a grid of size u1, u2, . . . , ud−1, cp − ud.
Proof. Consider a c-labeling A of the size u1, u2, . . . , ud grid with distinct (d − 1)-di-
mensional subgrids. The dimension d complement A∗d has size u1, u2, . . . , c
p − ud and
consists of all cp − ud possible (d − 1)-dimensional subgrids that do not appear in A. An
automorphism (π1, π2, . . . , πm) of A that preserves labels maps the (d − 1)-dimensional
subgrids of A to the (d− 1)-dimensional subgrids of A under πsub = (π1, π2, . . . , πd−1).
Hence, applying πsub to A∗d must map the (d − 1)-dimensional subgrids of A∗d to the
(d− 1)-dimensional subgrids of A∗d. So, we can find a permutation π′d of [cp − ud] so that
(π1, π2, . . . , πd−1, π
′
d) is an automorphism of A
∗
d that preserves labels.
We state the following without proof as it is identical to the grid switching lemma.
Lemma 3.2 (Array Switching Lemma). If there is a c-distinguishing labeling of an array
of size u1, u2, . . . , um−1, cp − um where p = u1u2 · · ·um−1 and um 6= uk for all k =
1, 2, . . . ,m−1, then there is a c-distinguishing labeling of an array of size u1, u2, . . . , um.
164 Ars Math. Contemp. 5 (2012) 159–173
Our second reduction lemma, which we will call the collapsing lemma, allows a reduc-
tion in the number of dimensions. It is based on the following simple observation. Consider
a c-labeling A of the size u1, u2 array. We can write the rows one after another in a string
of length u1u2 (i.e., 1-dimensional array A{1,2} of size u1u2). An automorphism (π1, π2)
of A permutes entries of A and hence there is a corresponding permutation π1,2 of the en-
tries of A{1,2}. Thus, if A{1,2} is a distinguishing c-labeling then so is A. Note that the
converse does not hold (indeed in two dimensions the entries need to be distinct for A{1,2}
to be distinguishing).
For higher dimensions, we need to be a little careful with equal sizes. For example,
consider a c-labeling A of size (u1, u2, u3) with u1 = u2. An automorphism of A that
transposes dimensions 1 and 2 does not necessarily correspond to an automorphism of
A{2,3}, obtained by collapsing dimensions 2 and 3. So, if ui = uj , then we must either
include both in the dimension we collapse or exclude both.
As with the switching lemma, for simplicity in notation we state the collapsing lemma
for collapsing dimensions k + 1, . . . , d. By permuting labels of the dimensions, a similar
statement holds for collapsing any set S as long as ui = uj implies either i, j ∈ S or
i, j 6∈ S.
Lemma 3.3 (Collapsing Lemma). If there is a distinguishing c-labeling of the (k + 1)
dimensional array of size (u1, u2, . . . , uk, (uk+1 · · ·ud)) and for i ≤ k and j > k we
have ui 6= uj , then there is a distinguishing c-labeling of the d dimensional array of size
(u1, u2, . . . , uk, uk+1, . . . , ud).
Proof. We prove the contrapositive. LetA be a c-labeling of the d-dimensional array of size
(u1, u2, . . . , uk, uk+1, . . . , ud) and define AS as in definition 2.7 with S = {k+1, . . . , d}.
LetAS be a distinguishing c-labeling of (u1, u2, . . . , uk, (uk+1 · · ·ud)) and letA be the
associated c-labeling of (u1, u2, . . . , uk, uk+1, . . . , ud). An automorphism (σ;π1, π2, . . . ,
πd) of A can be used to define an automorphism (σ′;π1, . . . , πk, πk+1) of AS in the ‘obvi-
ous’ way. We have σ′ the same as σ on {1, 2, . . . , k} with k + 1 fixed. The automorphism
produces some permutation of the entries in dimensions k + 1, . . . , d which we call π′k+1.
It is straightforward to see that we get an automorphism of AS . Hence, if A is not a dis-
tinguishing c-labeling of (u1, u2, . . . , uk, uk+1, . . . , ut), then AS is not a distinguishing
c-labeling of (u1, u2, . . . , uk, (uk+1 · · ·ut)).
We observe that there is a corresponding collapsing lemma for grids without the size
conditions. We do not need this in what follows so we will not formally state it.
4 Distinguishing labelings
In this section we state a theorem describing those values of c for which there are distin-
guishing labelings of arrays and grids of a given size. We first give lemmas providing upper
and lower bounds.
The following lemma will be used several times in the proof of Lemma 4.2.
Lemma 4.1. Let d be an integer greater than 3. If the array (u1, u2, . . . , ud−1) has a
distinguishing 2-labeling and if ud ≤ u1u2 · · ·ud−1 + 1, then (u1, u2, . . . , ud−1, ud) also
has a distinguishing 2-labeling.
M. J. Fisher and G. Isaak: Distinguishing numbers of Cartesian products. . . 165
Proof. Suppose that (u1, u2, . . . , ud−1) has a distinguishing 2-labeling; call it `. We define
the weight of a generic 2-labeling to be the total number of times the label one is used in
the labeling. Because there are u1u2 · · ·ud−1 + 1 2-labelings of (u1, u2, . . . , ud−1) with
different weights, we can construct a distinguishing 2-labeling of (u1, u2, . . . , ud−1, ud)
by taking ` together with any ud − 1 of the other remaining u1u2 · · ·ud−1 2-labelings of
(u1, u2, . . . , ud−1) with different weights.
Lemma 4.2. For integers c ≥ 2, d ≥ 3 and 1 ≤ u1 ≤ u2 ≤ · · · ≤ ud with ud ≤
cu1u2···ud−1 − d logc ud−1u1u2···ud−2 e − 1 there is a distinguishing c-labeling of the (u1, u2, . . . , ud)
array.
Proof. The proof will proceed by induction on the number d of dimensions and by in-
duction on ud. We will use the case d = 2 as the basis. For d = 2 and u1 ≤ u2, if
u2 ≤ cu1 − dlogc u1e − 1, then the (u1, u2) array has a distinguishing c-labeling ([5], [7]).
This corresponds to the formula above if we interpret the product u1 · · ·ud−2 as an empty
product equal to 1 when d = 2.
We will establish the result for d = 3 and d = 4 separately and then proceed to the case
d ≥ 5. For each d, several cases are needed to determine where collapsing can occur.
d = 3: We first establish base cases for induction on u3. Note that the collapsing lemma
implies that (2, 2, 3) has a distinguishing 2-labeling (collapsing the first two terms we have
a size (4, 3) array which has a distinguishing 2-labeling). It is easy to verify that the two
2-labelings of (3, 3)  2 2 21 2 1
1 2 2
 and
 1 1 22 1 1
2 2 1

provide us with an explicit distinguishing 2-labeling of (2, 3, 3). The first array giving the
a1,j,k entries and the second the a2,j,k entries. Finally, a result of Klavžar and Zhu [10]
tells us that (3, 3, 3) has a distinguishing 2-labeling.
Case 1: (u1 < u2 < u3)
(i) If u1u2 < u3, then ((u1u2), u3) has a distinguishing c-labeling if u3 ≤ cu1u2 −
dlogc u1u2e − 1. By the collapsing lemma, (u1, u2, u3) also has a distinguishing
c-labeling.
If cu1u2 − dlogc u1u2e − 1 < u3 ≤ cu1u2 − d
logc u2
u1
e − 1, then switch in dimension
3 and consider (u1, u2, z) where d logc u2u1 e+ 1 ≤ z ≤ dlogc u1u2e < u3.
(a) If 2 ≤ u1 < u2 ≤ z, then, as z < u3 ≤ cu1u2 − d logc u2u1 e − 1, (u1, u2, z) has
a distinguishing c-labeling by induction on u3. Thus, by the switching lemma,
(u1, u2, u3) also has a distinguishing c-labeling.
(b) If u1 < z < u2, then it is always true that u2 ≤ czu1 − d logc zu1 e − 1. [z ≥
logc u2
u1
+ 1 implies that czu1 ≥ u2cu1 . Thus, czu1 ≥ u2cu1 and z < u2 imply
that u2 ≤ u2cu1 −u2− 1 ≤ czu1 −d logc zu1 e− 1.] Hence, by induction on u3 and
the switching lemma, (u1, u2, u3) has a distinguishing c-labeling.
166 Ars Math. Contemp. 5 (2012) 159–173
(c) If z < u1 < u2, then it is always true that u2 ≤ czu1 − d logc u1z e − 1. [z ≥
logc u2
u1
+ 1 implies that czu1 ≥ u2cu1 . Thus, czu1 ≥ u2cu1 implies that u2 ≤
u2c
u1 − u2 − 1 ≤ u2cu1 − u1 − 1 ≤ czu1 − d logc u1z e − 1.] Hence, by induction
on u3 and the switching lemma, (u1, u2, u3) has a distinguishing c-labeling.
(d) If u1 = z < u2 and u21 < u2, then it is always true that u2 ≤ czu1−d
logc z
z e−1 =
czu1−2. [z ≥ logc u2u1 +1 implies that c
zu1 ≥ u2cu1 . Thus, czu1 ≥ u2cu1 implies
that u2 ≤ u2cu1 − 2 ≤ czu1 − 2.] It follows that (u21, u2) has a distinguishing
c-labeling. Thus, by the collapsing lemma, so does (u1, z, u2).
(e) If u1 = z < u2 and u21 = u2, then (u2, u2) has a distinguishing 2-labeling via the
d = 2 result. Thus, by the collapsing lemma, (u1, z, u2) also has a distinguishing
2-labeling. Hence, (u1, z, u2) also has a distinguishing c-labeling.
(f) Finally, if u1 = z < u2 and u2 < u21, then it is always true that u
2
1 ≤ 2u2 −
dlog2 u2e − 1. [It is easy to check that this inequality holds for u2 = 3, 4. For
u2 ≥ 5, a simple inductive argument implies that u22 ≤ 2u2−u2−1. The desired
inequality now follows.] It follows that (u2, u21) has a distinguishing 2-labeling.
Thus, by the collapsing lemma, so does (u1, z, u2). Therefore, (u1, z, u2) also
has a distinguishing c-labeling.
Thus, in any case, (u1, u2, u3) also has a distinguishing c-labeling by the switching
lemma.
(ii) If u3 ≤ u1u2, then since u1u2 ≤ 2u1u2−d log2 u2u1 e−1 always holds, (u1, u2, u3) has
a distinguishing 2-labeling by induction on dimension and by the collapsing lemma.
[u1 < u2 implies that u2 = u1 + m for some m ≥ 1. Using first semester calculus,
one can show that the function f(x) = 2x
2+mx − 1− x2 − (m+ 1)x−m is strictly
increasing for x ≥ 2 (and m fixed). Since f(2) > 0, the desired inequality now
follows.]
Case 2: (u1 < u2 = u3)
First note that it has already been shown that (2, 3, 3) has a distinguishing 2-labeling.
Next, recall that it is known (by the d = 2 case) that if 4 ≤ u2 = u3, then (u2, u3) has
a distinguishing 2-labeling. Thus, Lemma 4.1 implies that (u1 < u2 = u3) also has a
distinguishing 2-labeling.
Case 3: (u1 = u2 = u3)
This case follows from results in [9].
Case 4: (u1 = u2 < u3), where u2 + 1 ≤ u3 ≤ cu
2
2 − d logc u2u1 e − 1
(i) For (u1 = u2 < u2 + ε), 1 ≤ ε ≤ u22 − u2, we collapse and consider (u2 + ε, u22).
As we will show, u22 ≤ 2u2+ε − dlog2(u2 + ε)e − 1 holds for all u2 ≥ 2. Thus,
(u2 + ε, u
2
2) has a distinguishing 2-labeling by induction on dimension and hence
(u1 = u2 < u2 + ε) has a distinguishing 2-labeling by the collapsing lemma.
[u22 ≤ 2u2+ε − dlog2(u2 + ε)e − 1 can be verified by hand for the cases u2 = 2, 3, 4.
For u2 ≥ 5, one can prove by induction that u22 ≤ 2u2+1 − u22 − 1. Our result then
follows.]
M. J. Fisher and G. Isaak: Distinguishing numbers of Cartesian products. . . 167
(ii) For (u1 = u2 < u22 + 1) through (u1 = u2 < c
u22 − dlogc u22e − 1), we collapse
and look at (u22, z), u
2
2 + 1 ≤ z ≤ cu
2
2 − dlogc u22e − 1. By induction on dimension,
(u22, z) has a distinguishing c-labeling.
(iii) Finally, we see by the switching lemma that (u1 = u2 < cu
2
2 − dlogc u22e) through
(u1 = u2 < c
u22 − d logc u2u2 e − 1) all have a distinguishing c-labeling. Note that one
case not covered here is (2, 2, 14) ((2, 2, 2) does not have a distinguishing 2-labeling).
However, since (4, 14) has a distinguishing 2-labeling, the collapsing lemma shows
that (2, 2, 14) does too.
d = 4: The case (2, 2, 2, 2) will serve as the basis step for induction on u4.
Case 1: (u1 < u2 < u3 < u4)
(i) If u1u2 ≤ u3, then, by induction on dimension, (u1u2, u3, u4) has a distinguishing
c-labeling if u4 ≤ cu1u2u3 − d logc u3u1u2 e − 1.
(ii) If u3 < u1u2 = u4, then we use Lemma 4.1 to build a distinguishing 2-labeling for
(u3, u1u2, u4) from a distinguishing 2-labeling of (u1u2, u4).
(iii) If u3 < u1u2 < u4, then (u3, u1u2, u4) has a distinguishing c-labeling if u4 ≤
cu1u2u3−d logc u1u2u3 e−1. If c
u1u2u3−d logc u1u2u3 e−1 < u4 ≤ c
u1u2u3−d logc u3u1u2 e−1,
then we switch in the last dimension and look at d logc u3u1u2 e+ 1 ≤ z < d
logc u1u2
u3
e+ 1.
Note that the last string of inequalities is equivalent to 2 ≤ z < 3. Thus, the only
value of z that we need to check is z = 2.
To decide whether or not (2, u3, u1u2) has a distinguishing c-labeling, we switch in
the second dimension and look at (2, c2u1u2 − u3, u1u2). Since u3 < u1u2, we have
u1u2 ≤ c2u1u2 − u3. Now, since u3 ≥ dlogc u2e + 1 ≥ d
logc u1u2
2 e + 1, it follows
that c2u1u2 − u3 ≤ c2u1u2 − d logc u1u22 e − 1. Hence, (2, u1u2, c
2u1u2 − u3) has a
distinguishing c-labeling. Therefore, (2, u3, u1u2) does too.
(iv) If u4 < u1u2, then it is easily seen that u1u2 ≤ 2u3u4 − d log2 u4u3 e − 1. [u1u2 <
u3u4 and u4 < u1u2 imply the desired inequality.] Hence, (u3, u4, u1u2) has a
distinguishing 2-labeling.
Case 2: (u1 ≤ u2 < u3 = u4)
(i) If u1u2 < u3, then u4 ≤ 2u1u2u3 − d log2 u3u1u2 e − 1 always holds. [One can show by
induction on u4 that 2u4 ≤ 2u1u2u4 − 1. The desired inequality follows from the
last statement.] Hence, by the collapsing lemma, (u1, u2, u3, u4) has a distinguishing
2-labeling.
(ii) Similarly, if u3 ≤ u1u2, then u4 = u3 ≤ u1u2 < u24 ≤ 2u
2
4−2 always holds. Hence,
by the collapsing lemma, (u1, u2, u3, u4) has a distinguishing 2-labeling.
Case 3: (u1 < u2 = u3 < u4)
168 Ars Math. Contemp. 5 (2012) 159–173
(i) If u22 < u4, then (u1, u2, u3, u4) has a distinguishing c-labeling, by the collapsing
lemma, if u4 ≤ cu1u
2
2 − d logc u
2
2
u1
e − 1. If cu1u22 − d logc u
2
2
u1
e − 1 < u4 ≤ cu1u
2
2 −
d logc u3u1u2 e − 1, then we switch in the last dimension and look at d
logc u3
u1u2
e + 1 ≤ z <
d logc u
2
2
u1
e+ 1. The last string of inequalities implies that 2 ≤ z < 2u2.
(a) If 2 ≤ z ≤ u2, then (u1, z, u2, u3) (or (z, u1, u2, u3)) has a distinguishing 2-
labeling as long as u3 ≤ 2zu1u2 − d log2 u2zu1 e − 1. [u3 ≤ 2
zu1u3 − u3 − 1 is
always true by induction, since zu1 ≥ 4 and u2 = u3. The desired inequality
now follows.]
(b) If u2 < z < 2u2, then (u1, u2, u3, z) has a distinguishing 2-labeling as long as
z < 2u2 ≤ 2u1u
2
2 − d log2 u3u1u2 e − 1. [Since u2 = u3, one can prove via induction
that 2u2 ≤ 2u1u
2
2−u2−1 holds for u2 ≥ 3. The desired inequality now follows.]
(ii) If u4 ≤ u22, then it is always true that u4 ≤ 2u
2
2 − d log2 u2u2 e − 1 = 2
u22 − 2.
Hence, (u2, u2, u4) has a distinguishing 2-labeling. Therefore, Lemma 4.1 implies
that (u1, u2, u3, u4) has a distinguishing 2-labeling.
Case 4: (u1 = u2 < u3 ≤ u4)
(i) If u22 ≤ u3, then u4 ≤ cu3u
2
2 − d logc u3
u22
e − 1 implies that (u22, u3, u4) has a distin-
guishing c-labeling.
(ii) If u3 < u22 ≤ u4, then u4 ≤ cu3u
2
2 − d logc u
2
2
u3
e − 1 implies that (u3, u22, u4) has a
distinguishing c-labeling. If cu3u
2
2 −d logc u
2
2
u3
e−1 < u4 ≤ cu3u
2
2 −d logc u3
u22
e−1, then
switch in the last dimension and look at d logc u3
u22
e+ 1 ≤ z < d logc u
2
2
u3
e+ 1. Note that
the last string of inequalities implies that 2 ≤ z < 3. Thus the only value of z that we
need to consider is z = 2.
Hence, we consider (2, u1, u2, u3). By induction on u4, (2, u1, u2, u3) has a distin-
guishing c-labeling as u3 < u22 ≤ c2u
2
2 − d logc u22u2 e − 1 = c
2u22 − 2.
(iii) If u3 ≤ u4 < u22, then (u3, u4, u22) has a distinguishing 2-labeling as u22 ≤ 2u3u4 −
d log2 u4u3 e−1. [The inequality we want follows from the inequality u
2
2 < 2
u22−u22−1.]
Case 5: (u1 ≤ u2 = u3 = u4) and (u1 = u2 = u3 < u4)
(i) For (u1 < u2 = u3 = u4), we note that (u2, u3, u4) has a distinguishing 2-labeling.
Hence, by Lemma 4.1, (u1, u2, u3, u4) has one too.
(ii) The case (u1 = u2 = u3 = u4) is already known.
(iii) For (u1 = u2 = u3 < u3 + 1), we note that (u2, u3, u3 + 1) has a distinguishing
2-labeling. Hence, by Lemma 4.1, (u1, u2, u3, u3 + 1) has one too.
(iv) For (u1 = u2 = u3 < u3 + ε), 2 ≤ ε ≤ u33 − u3, we collapse and consider
(u3 + ε, u
3
3). As we will show, u
3
3 ≤ 2u3+ε − dlog2(u3 + ε)e − 1 holds for all
u3 ≥ 2, except for (u3, ε) = (4, 2) and (u3, ε) = (5, 2). By Lemma 4.1, (4, 4, 4, 6)
and (5, 5, 5, 7) both have distinguishing 2-labelings. For all other cases, we observe
M. J. Fisher and G. Isaak: Distinguishing numbers of Cartesian products. . . 169
that (u3 +ε, u33) has a distinguishing 2-labeling by induction on dimension and hence
(u1 = u2 = u3 < u3 + ε) has a distinguishing 2-labeling by the collapsing lemma.
[u3 ≤ 2u3+ε − dlog2(u3 + ε)e − 1 can be verified by hand for the cases 2 ≤ u3 ≤ 9.
For u3 ≥ 10, one can prove by induction that u33 ≤ 2u3+1 − u33 − 1. Our result then
follows.]
(v) For (u1 = u2 = u3 < u33 + 1) through (u1 = u2 = u3 < c
u33 − dlogc u33e − 1), we
look at (u33, z), u
3
3 + 1 ≤ z ≤ cu
3
3 − dlogc u33e − 1.
(vi) The switching lemma takes care of (u1 = u2 = u3 < cu
3
3 − dlogc u33e) through
(u1 = u2 = u3 < c
u33 − d logc u3u1u2 e − 1).
d ≥ 5: The case (2, 2, 2, 2, . . . , 2) will serve as the basis step for induction on ud.
Case 1: (u1 ≤ u2 < u3 ≤ u4 ≤ · · · ≤ ud−1 ≤ ud)
(i) If u1u2 ≤ ud−1, then (u3, u4, . . . , u1u2, . . . , ud−1, ud) has a distinguishing c-labe-
ling if ud ≤ cu1u2···ud−1 − d logc ud−1u1u2···ud−2 e − 1.
(ii) If ud−1 < u1u2 ≤ ud, then (u3, u4, . . . , ud−1, u1u2, ud) has a distinguishing c-
labeling if ud ≤ cu1u2···ud−1−d logc u1u2u3u4···ud−1 e−1. Since d
logc u1u2
u3u4···ud−1 e = d
logc ud−1
u1u2···ud−2 e
= 1, we never have to worry about the case cu1u2···ud−1 − d logc u1u2u3u4···ud−1 e − 1 < ud.
(iii) If ud < u1u2, then (u3, u4, . . . , ud−1, ud, u1u2) has a distinguishing c-labeling as
u1u2 ≤ cu3u4···ud − d logc udu3u4···ud−1 e − 1 = c
u3u4···ud − 2. Because ud < u1u2, we do
not have to worry about the case cu3u4···ud − d logc udu3u4···ud−1 e − 1 ≤ ud.
Case 2: (u1 = u2 = · · · = uk < uk+1 ≤ · · · ≤ ud−1 ≤ ud), where 2 ≤ k ≤ d− 2
(i) If uk1 ≤ ud−1, then (uk+1, . . . , uk1 , . . . , ud−1, ud) has a distinguishing c-labeling if
ud ≤ cu
k
1 ···ud−1 − d logc ud−1
uk1 ···ud−2
e − 1.
(ii) If ud−1 < uk1 ≤ ud, then (uk+1, . . . , ud−1, uk1 , ud) has a distinguishing c-labeling
if ud ≤ cu
k
1 ···ud−1 − d logc u
k
1
uk+1···ud−1 e − 1. If c
uk1 ···ud−1 − d logc u
k
1
uk+1···ud−1 e − 1 < ud ≤
cu
k
1 ···ud−1 − d logc ud−1u1u2···ud−2 e − 1 = c
uk1 ···ud−1 − 2, then switch and look at
2 = d logc ud−1
u1u2 · · ·ud−2
e+ 1 ≤ z < d logc u
k
1
uk+1 · · ·ud−1
e+ 1 = k + 1 < uk1 .
(a) If z < ud−1, then look at (u1, u2, . . . , z, . . . , ud−1). Note that (u1, u2, . . . , z,
. . . , ud−1) has a distinguishing c-labeling if ud−1 ≤ cu
k
1uk+1···z − d logc δε e − 1,
where ε = u1u2 · · ·ud−2 if δ = z and ε = u1u2 · · ·ud−3z if δ = ud−2. Since,
in either case, d logc δε e ≤ ud−1, it follows that ud−1 ≤ c
uk1uk+1···z − d logc δε e − 1
always holds.
(b) If ud−1 ≤ z < uk1 , then we consider (u1, u2, . . . , uk, uk+1, . . . , ud−1, z). Since
it is always true that z ≤ cuk1uk+1···ud−1 − d logc ud−1
uk1 ···ud−2
e − 1 = cuk1uk+1···ud−1 − 2,
(u1, u2, . . . , uk, uk+1, . . . , ud−1, z) has a distinguishing c-labeling.
170 Ars Math. Contemp. 5 (2012) 159–173
(iii) If ud < uk1 , then ud ≤ 2u
k
1uk+1···ud−2 − 2. Thus, (u1, u2, . . . , ud−2, ud) has a dis-
tinguishing 2-labeling and so, by Lemma 4.1, (u1, u2, . . . , ud−2, ud−1, ud) has one
too.
Case 3: (u1 < u2 = · · · = uk < uk+1 ≤ · · · ≤ ud−1 ≤ ud), where 3 ≤ k ≤ d− 1
(i) If uk−12 ≤ ud−1, then (u1, uk+1, . . . , u
k−1
2 , . . . , ud−1, ud) has a distinguishing c-
labeling if ud ≤ cu1u
k−1
2 ···ud−1 − d logc ud−1
u1u
k−1
2 ···ud−2
e − 1.
(ii) If ud−1 < uk−12 ≤ ud, then (u1, uk+1, . . . , ud−1, u
k−1
2 , ud) has a distinguishing
c-labeling if ud ≤ cu1u
k−1
2 ···ud−1 − d logc u
k−1
2
uk+1···ud−1 e − 1.
If cu1u
k−1
2 ···ud−1−d logc u
k−1
2
uk+1···ud−1 e−1 < ud ≤ c
u1u
k−1
2 ···ud−1−d logc ud−1u1u2···ud−2 e−1, then
switch and look at 2 = d logc ud−1u1u2···ud−2 e+ 1 ≤ z < d
logc u
k−1
2
uk+1···ud−1 e+ 1 ≤ k < u
k−1
2 .
(a) If z < ud−1, then consider (u1, u2, . . . , uk, uk+1, . . . , z, . . . , ud−1). Note that
(u1, u2, . . . , uk, uk+1, . . . , z, . . . , ud−1) has a distinguishing c-labeling if ud−1≤
cu1u
k−1
2 ···ud−2z − d logc δε e − 1, where ε = u1u2 · · ·ud−2 if δ = z and ε =
u1u2 · · ·ud−3z if δ = ud−2. Since, in either case, d logc δε e ≤ ud−1, it follows
that ud−1 ≤ cu1u
k−1
2 ···ud−2z − d logc δε e − 1 always holds.
(b) If ud−1 ≤ z < uk−12 , then look at (u1, u2, . . . , uk, uk+1, . . . , ud−1, z). Since
z ≤ cu1u
k−1
2 ···ud−1 − d logc ud−1
u1u
k−1
2 ···ud−2
e − 1 = cu1u
k−1
2 ···ud−1 − 2 always holds,
(u1, u2, . . . , uk, uk+1, . . . , ud−1, z) has a distinguishing c-labeling by induction
on ud.
(iii) If ud < uk−12 , then ud ≤ 2u
k−1
2 uk+1···ud−1 − 2. Thus (u2, u3, . . . , ud) has a distin-
guishing 2-labeling and so, by Lemma 4.1, (u1, u2, . . . , ud) has one too.
Case 4: (u1 ≤ u2 = · · · = ud−1 = ud) and (u1 = u2 = · · · = ud−1 < ud)
(i) For (u1 ≤ u2 = u3 = · · · = ud−1 = ud), we note that (u2, u3, . . . , ud) has a
distinguishing 2-labeling and so, by Lemma 4.1, (u1, u2, . . . , ud) has one too.
(ii) For (u1 = u2 = · · · = ud−1 < ud), u1 < ud < ud−21 , we note that ud < u
d−1
1 .
Therefore, since (u1, u2, . . . , ud−1) has a distinguishing 2-labeling, Lemma 4.1 im-
plies that (u1, u2, . . . , ud−1, ud) also has a distinguishing 2-labeling.
(iii) If ud−21 ≤ ud < u
d−1
1 , then (ud, u
d−1
1 ) has a distinguishing 2-labeling since u
d−1
1 ≤
2u
d−2
1 − ud−11 − 1 ≤ 2ud − ud − 1.
(iv) If ud−11 ≤ ud ≤ cu
d−1
1 − dlogc ud−11 e − 1, then (u
d−1
1 , ud) has a distinguishing
c-labeling (since ud ≤ cu
d−1
1 − dlogc ud−11 e − 1).
(v) Lastly, if cu
d−1
1 − dlogc ud−11 e ≤ ud ≤ cu
d−1
1 − d logc ud−1
ud−21
e − 1 = cu
d−1
1 − 2, then
we switch and look at (z, u1, u2, . . . , ud−1) or (u1, u2, . . . , ud−1, z), where 2 ≤ z ≤
dlogc ud−11 e < u
d−1
1 . In either case, it follows that (u1, u2, . . . , ud−1, ud) has a
distinguishing c-labeling. 
M. J. Fisher and G. Isaak: Distinguishing numbers of Cartesian products. . . 171
Lemma 4.3. For integers c ≥ 2, d ≥ 3 and 1 ≤ u1 ≤ u2 ≤ · · · ≤ ud with ud ≥
cu1u2···ud−1−d logc ud−1u1u2···ud−2 e+1, there is no distinguishing c-labeling of the (u1, u2, . . . , ud)
grid.
Proof. If ud > cu1u2···ud−1 , then since the dimension d subgrids have size (u1, u2, . . . ,
ud−1) and there are greater than cu1u2···ud−1 such subgrids, at least two of them must be
identical. An automorphism switching two such positions in dimension d preserves labels.
So, there is no distinguishing c-labeling in this case.
If ud = cu1u2···ud−1 and two dimension d subgrids are identical, apply the same auto-
morphism as the previous paragraph. Otherwise, the set of dimension d subgrids is exactly
the set of possible subgrids. Then, take any nontrivial automorphisms π1, . . . , πd−1 in
the other dimensions. This induces a permutation πd of the dimension d subgrids. Then,
(π1, . . . , πd) preserves labels. So, there is no distinguishing c-labeling in this case.
If cu1u2···ud−1 − d logc ud−1u1u2···ud−2 e + 1 ≤ ud < c
u1u2···ud−1 , by the grid switching lemma
there is a distinguishing c-labeling only if there is a distinguishing c-labeling of the grid of
size (u1, u2, . . . , ud−1, cud − z), where 1 ≤ z ≤ d logc ud−1u1u2···ud−2 e − 1. Note that ud−1 ≥ z
and that z · (u1 · · ·ud−2) < ( logc ud−1u1u2···ud−2 ) · (u1 · · ·ud−2) = logc ud−1. So, c
z·(u1···ud−2) <
clogc ud−1 = ud−1. Hence, by the first paragraph, there is no distinguishing c-labeling.
Theorem 4.4. For integers d ≥ 2 and 1 ≤ u1 ≤ · · · ≤ ud let s = u1u2 · · ·ud−1 and
c = du1/sd e. Except for d = 2 with u1 = u2 ∈ {2, 3} and for d = 3 with u1 = u2 =
u3 = 2 we have that the grid and array of size (u1, u2, . . . , ud) have a distinguishing c-
labeling if ud ≤ cu1u2···ud−1 − d logc ud−1u1u2···ud−2 e − 1. They have no distinguishing c-labeling
if ud ≥ cu1u2···ud−1 − d logc ud−1u1u2···ud−2 e+ 1.
Proof. If the array has a distinguishing c-labeling, so does the grid. If the grid has no
distinguishing c-labeling, neither does the array. The result then follows immediately from
Lemmas 4.2 and 4.3.
In the remaining case, ud ≥ cu1u2···ud−1 − d logc ud−1u1u2···ud−2 e, the theorem gives no infor-
mation. However, in these cases, we can apply the switching lemma to check. We again
may need to recursively check the new sizes. However, the number of such steps will be at
most the iterated logarithm (base c) of ud.
5 Distinguishing numbers
In this section, we take the results of the previous section in order to determine (up to two
possible values) the distinguishing numbers for arrays and grids.
Theorem 4.4 was stated from the perspective of whether or not a distinguishing c-
labeling exists for given c and (u1, u2, . . . , ud). For given (u1, u2, . . . , ud), the distinguish-
ing number (for a grid or array) is the smallest c such that the condition for a distinguishing
labeling in Theorem 4.4 is satisfied. Determining this c we get the following result for
distinguishing numbers.
Corollary 5.1. For integers d ≥ 2 and 1 ≤ u1 ≤ · · · ≤ ud, let s = u1u2 · · ·ud−1 and
c = du1/sd e. Except for d = 2 with u1 = u2 ∈ {2, 3} and for d = 3 with u1 = u2 =
u3 = 2, we have D(Grid(u1, u2, . . . , ud)) = D(Array(u1, u2, . . . , ud)) ∈ {c, c + 1}.
172 Ars Math. Contemp. 5 (2012) 159–173
It is c if ud ≤ cs − d logc ud−1u1u2···ud−2 e − 1 and c + 1 if c
s − d logc ud−1u1u2···ud−2 e + 1 ≤ ud. When
ud = c
s−d logc ud−1u1u2···ud−2 e, it is c if the grid of size (u1, u2, . . . , c
s−ud) has a distinguishing
c-labeling and c+ 1 otherwise. Hence, we can recursively determine the value in this case.
Proof. It is easy to check that for k < c, ud ≥ ks − d logk ud−1u1u2···ud−2 e + 1 and that ud ≤
(c + 1)s − d logc+1 ud−1u1u2···ud−2 e − 1. Hence, the smallest c such that there is a distinguishing
c-labeling is c or c + 1. The exact values follow immediately from Theorem 4.4. The
comment about the recursion follows from the switching lemma.
We finish with a few comments and examples. The distinguishing numbers for the
exceptional cases in the corollary are 2 for grids and 3 for arrays as noted earlier. For
the special cases when we use recursion, it is possible that the smaller grid/array has a
distinguishing number smaller than c. However, what matters is whether or not the reduced
case has a distinguishing c-labeling. Consider the following sizes for examples with d = 3:
(3, 56 − 2, 53·(56−2) − 2), (3, 56 − 1, 53·(56−1) − 2), (3, 56, 53·56 − 2). In each case, c = 5
and we are on the boundary where we need to apply recursion. By the switching lemma, we
look at (respectively) 5-labelings for sizes (2, 3, 56−2), (2, 3, 56−1), (2, 3, 56). In the first
case, the conditions give a 5-labeling and in the last case they do not. So D(Grid(3, 56 −
2, 53·(5
6−2) − 2) = 5 and D(Grid(3, 56, 53·56 − 2) = 6. In the middle case we again
are on a boundary and apply the switching lemma one more time, looking at size (1, 2, 3).
Here, there is a distinguishing 5-labeling so we get D(Grid(3, 56 − 1, 53·(56−1) − 2) = 5.
It happens also that D(Grid(2, 3, 56 − 1) = 5, but it could have been lower. Note that
D(Grid(1, 2, 3) = 2, but the fact that there is a distinguishing 2-labeling does not help for
size (2, 3, 56 − 1) as we need at least 5 labels for this size.
Acknowledgements We would like to thank the anonymous referees who made useful
comments that improved the paper. In particular, one referee suggested the comments in
the last three paragraphs of section 1. In addition, we would also like to posthumously
acknowledge Mike Albertson who gave very useful advice during the preparation of our
paper [5] giving a 2-dimensional result, as well as preliminary discussions on the results in
this paper.
References
[1] M. O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005),
Note #17.
[2] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3
(1996), Research Paper #18.
[3] B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube, Discrete Math. 283
(2004), 29–35.
[4] M. Chan, The distinguishing number of the direct product and wreath product action, J. Alge-
braic Combin. 24 (2006), 331–345.
[5] M. J. Fisher and G. Isaak, Distinguishing colorings of Cartesian products of complete graphs,
Discrete Math. 308 (2008), 2240–2246.
[6] F. Harary and D. Ranjan, Identity orientations of complete bipartite graphs, Discrete Math. 290
(2005), 173–182.
M. J. Fisher and G. Isaak: Distinguishing numbers of Cartesian products. . . 173
[7] W. Imrich, J. Jerebic and S. Klavžar, The distinguishing number of Cartesian products of com-
plete graphs, European J. Combin. 29 (2008), 922–929.
[8] W. Imrich and S. Klavžar, Product Graphs, John Wiley & Sons, Inc., New York, 2000.
[9] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, Distinguishing Cartesian
powers of graphs, J. Graph Theory 53 (2006), 250–260.
[10] S. Klavžar and X. Zhu, Cartesian powers of graphs can be distinguished with two labels, Euro-
pean J. Combin. 28 (2007), 303–310.