Revista de Matema´tica: Teor´ıa y Aplicaciones 2004 11(2) : 55–70
cimpa – ucr – ccss issn: 1409-2433
graph dominance by rook domains
for Znp and Zn3 × Zm2 graphs
Eduardo Piza–Volio∗
Received/Recibido: 16 Jan 2004
Abstract
Described within is the problem of finding near-minimum dominating subsets of a
given graph by rook domains. Specifically, we study the graphs of the kind Znp and
Zn3 ×Zm2 and introduce a simulated annealing algorithm to compute upper bounds of
the size of minimum dominating subsets.
We demonstrate the effectiveness of the algorithm by comparing the results with a
previously studied class of graphs, including the so-called “football pool” graphs and
others. We give some new upper bounds for graphs of the kind Znp , with p ≥ 4. The
codes of some dominating subsets are given in an appendix.
Keywords: Graph domination, simulated annealing, football pool problem, combina-
torics.
Resumen
En este art´ıculo se describe el problema de la dominacio´n de los grafos del tipo Znp
y mezclas del tipo Zn3×Zm2 a trave´s de subconjuntos dominantes de ve´rtices de taman˜o
mı´nimo. Se introduce un algoritmo del tipo de recocido simulado para calcular cotas
superiores de la cardinalidad de estos subconjuntos dominantes minimales.
Se demuestra la eficiencia del algoritmo al comparar los resultados obtenidos con
los ya conocidos correspondientes a algunas clases de grafos, entre ellos los llamados
grafos del “football pool problem”. Se establecen cotas superiores en algunos de los
grafos del tipo Znp , con p ≥ 4. Los co´digos de algunos subconjuntos dominantes se
incluyen en un ape´ndice.
Palabras clave: Dominacio´n de grafos, recocido simulado, problema de las apuestas en
fu´tbol, combinatoria.
AMS Subject Classification: 68R05, 68R10, 05C69, 90C27.
∗Centro de Investigacio´n en Matema´tica Pura y Aplicada, CIMPA, Universidad de Costa Rica, 2060,
San Jose´, Costa Rica. E-Mail: epiza@cariari.ucr.ac.cr.
55
56 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
1 Introduction
The theme of graph domination by rook domains has been deeply studied during the
last few years [3, 5, 7, 9, 11, 12, 13, 16], and a large variety of approximate solutions
(occasionally exact) has been found to the given problems. The most useful methods used
to find near-minimum dominating subsets seem to be the heuristic methods based on the
combinatorial optimization techniques, like tabu search, simulated annealing and genetic
algorithms. This paper precisely describes a simulated annealing algorithm [1, 10, 15] to
resolve these kinds of problems.
Throughout this article p will represent a natural number ≥ 2 and n and m will
represent natural numbers, with n+m ≥ 1. We will be working with the graphs F np and
F n,m3,2 , which are defined as follows:
• The sets of vertices of F np and F n,m3,2 are V = Znp and V = Zn3 × Zm2 , respectively.
• In both graphs F np and F n,m3,2 we stipulated that two given vertices are adjacent if
they have Hamming distance equal to 1, that is, if they differ only in one of their
corresponding coordinates.
The vertices are represented as vectors: of n coordinates for the graph F np and n+m
coordinates for the graph F n,m3,2 . Both graphs have been extensively studied in relation to
the theme of domination, particularly the F n3 graph, in which the problem of finding a
minimum dominating subset is named as the football pool problem.
The terminology “domination by rook domains” refers to the kind of metric used for
these graphs F np and F
n,m
3,2 (Hamming distance) and comes from the chess context. In fact,
the concept of domination by rook domains in the graph F 28 precisely coincides with the
movements of a rook on a chess board, as illustrated in Figure 1.
On the other hand, the terminology football pool problem comes from a system of
lottery existent in some countries (for example, “Lotto” in France and Italy, “Progol”
in Costa Rica), in which the gamblers have to bet on the results of n soccer games, each
one having three possible results: victory of the home team, defeat of the home team, or
equal score. In this context, a dominating subset of F n3 will correspond to a set of lottery
bills with the bets of the n games, in such a way that it is granted—under any eventuality
of the games’ results—that at least one of the bills contains at least n−1 correct bets; that
is to say that there will be one bill that contains at most one incorrect bet. In this case,
maybe the gambler is not going to become a millionaire by guessing all the n games, but
nevertheless he will win for sure the second prize (and sometimes the first prize), which is
also a sizable winning.
If the lottery under consideration additionally included m games of another sport in
which any of them has 2 possible results (winning or losing of the home team, for example),
then we are confronting an F n,m3,2 graph. A dominating subset of this graph will grant us—
under any eventuality of the games’ results—that there will be one bill with at most one
incorrect bet (maybe with all the bets correct), allowing certainty in winning the second
prize and occasionally the first one.
The problem of finding a minimum dominating subset of vertices for these graphs F np
and F n,m3,2 is a combinatorial optimization problem identified as difficult, not only due to
graph dominance by rook domains for Znp and Zn3 × Zm2 graphs 57
Figure 1: Two of the most popular objects of F np : the movements of the rooks on the
chess board in the graph F 28 = (Z28,H), and the Rubik cube F 33 = (Z33,H), where H is the
Hamming distance. In the case of a chess board, the figure shows one of the exact solutions
to the problem of domination by rook domains: 8 rooks are necessary and sufficient to
dominate all the squares of an 8×8 chess board. In the case of a Rubik cube it is necessary
and sufficient to have 5 specially chosen “vertices” (small cubes) to dominate the graph;
for example these: 012, 021, 100, 211, 222.
the monstrous size of the configuration space that it involves, but also because of the
intrinsic algorithmic complexity associated to it. A considerable effort has been dedicated
by various authors to the research of dominating subsets for these graphs, especially for the
graphs F n,m3,2 and F
n
3 . Some of this effort involves combinatorial constructions, or heuristics
searches, or a combination of both methods. Practically only a few exact solutions for
some small values of n, m and p are known. In the majority of the studied cases only
an upper bound for the size of the minimum dominating subset is known. A list of the
known solutions (exact and approximate upper bounds) can be looked up in the articles
of Ha¨ma¨la¨inen & Rankinen [7] and O¨sterg˚ard & Ha¨ma¨la¨inen [12].
Let’s write σn3 for the size of a minimum dominating subset of the “football pool
problem” with n games. The smallest of the problems for which the exact value of σn3 is
still unknown is the 729-vertex graph F 63 . In 1989 van Laarhoven, Aarts, van Lint and
Wille [11] found a dominating subset of F 63 with 73 vertices, using a simulated annealing
algorithm. Therefore, σ63 ≤ 73. Until now, that’s the official record, and even if suspected
that σ63 = 72 (see O¨sterg˚ard [14]) nobody has demonstrated yet this supposition and maybe
no one ever will. To better understand the magnitude of this problem, in the graph F 63
of 729 vertices there are (72972 ) ≈ 0.57 × 10101 different subsets of 72 vertices, a monster
quantity that makes it impossible to try an exhaustive search for an exact solution. In
Figure 2 we present a dominating subset for F 63 with 73 vertices (that is, equal to the
record) found by the author.
By the use of our simulated annealing algorithm, we have found upper bounds for the
size of the minimum dominating subset of F np , for some values of p ≥ 4. In addition, some
58 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
222
221
220
212
211
210
202
201
200
122
121
120
112
111
110
102
101
100
022
021
020
012
011
010
002
001
000
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
Figure 2: A dominating subset for Z63 graph by 73 vertices, found by the author. In this
graph the position of the vertices (6-tuples of Z63) are represented by taking the first 3
coordinates as the abscisse and the last 3 coordinates as the ordinate.
of the upper bounds could be equaled in the analog problem for F n,m3,2 , F
m
2 and F
n
3 graphs,
proving the effectiveness of the method. The codes of some dominating subsets are given
in an appendix.
2 Definitions, notations and basic results
In a graph G = (V,E) we say that a vertex v ∈ V dominates the vertices in the closed
neighborhood N [v] = {v} ∪ {u ∈ V : (u, v) ∈ E}. The vertices that are dominated by a
subset of the set of vertices V ′ ⊆ V , are those contained in the set
domV ′ :=
⋃
v∈V ′
N [v].
A dominating subset of the graph G is V ′ ⊆ V such that domV ′ = V . A minimum
dominating subset of the graph G is the one that has the least number of vertices. In
general, the problem of finding a minimum dominating subset of G and its cardinality has
been well identified as an NP-hard problem [6].
Each vertex of Znp can be viewed as a vector of n coordinates, each one taking values
in Zp = {0, 1, . . . , p− 1}. Then, the Hamming distance implies that in the graph F np two
vertices will be adjacent if they differ in exactly one of their corresponding coordinates.
Similarly, in the graph F n,m3,2 each element of V = Zn3 × Zm2 can be viewed as a vector of
n+m coordinates, where the first n coordinates are ternary (taking values in Z3) and the
graph dominance by rook domains for Znp and Zn3 × Zm2 graphs 59
last m are binary (taking values in Z2). Consequently, in the graph F n,m3,2 two vertices will
be adjacent if they differ in exactly one of their corresponding coordinates.
The graph F np is regular (all the closed neighborhoods N [v] has the same size) and
have valency n(p− 1) (number of vertices adjacent to each given vertex). We shall denote
the size of the minimum dominating subset of F np by σ
n
p . As a vertex v ∈ Znp dominates
n(p− 1) + 1 vertices, then the following inequalities are verified:
pn
n(p− 1) + 1 ≤ σ
n
p ≤ pn−1. (1)
The inequality on the right in (1) is justified by looking at the problem in terms of n games
with p different results, so pn−1 is a sufficient quantity of vertices to dominate a graph
with n− 1 games. The expression on the left in (1) gives us a lower bound for σnp , usually
referred to as the sphere-packing bound for F np . A subset of vertices that exactly satisfies
the sphere-packing bound is called a perfect code, and such a code dominates every vertex
precisely once.
Similarly, the graph F n,m3,2 is also regular and has valency 2n+m. We shall denote by
κ(n,m) the size of the minimum dominating subset of κ(n,m).1 As a vertex v ∈ Zn3 ×Zm2
dominates 2n+m+ 1 vertices, then we have the following inequalities:
3n 2m
2n+m+ 1
≤ κ(n,m) ≤ 3n−12m. (2)
The inequality on the right in (2) is justified by considering all the possible results
of n − 1 games in Z3 and m games in Z2, such that in total we guarantee a bill with
n+m− 1 right results. The expression of the left in (2) gives a lower bound for κ(n,m),
usually referred to as the sphere-packing bound for F n,m3,2 . A subset of vertices of F
n,m
3,2
that exactly satisfies the sphere-packing bound is called a perfect code and such a code
dominates every vertex exactly once.
The graphs Fm2 and F
n
3 are usually called hypercube graph and football pool graph
respectively. It is known that they contain perfect codes when n and m take certain
values (see [4]). In particular, if m = 2r − 1 then the hypercube graph Fm2 contains a
perfect code of size 22
r−r−1. Thus, σ32 = 2 and σ72 = 16. Similarly, when n = (3r − 1)/2
the football pool graph F n3 contains a perfect code of size 3
(3r−2r−1)/2. Therefore, we have
σ43 = 9 and σ
13
3 = 50049.
Another known property is that, for big values of n the quantity σnp tends toward the
sphere-packing bound (see [2, 4]), that is, for all p ≥ 2 we have
lim
n→∞
σnp
n(p− 1) + 1 = 1. (3)
In addition, from the formulation of the graph F n,m3,2 in terms of ternary and binary
games, it is evident the inequality 2κ(n+1,m) ≤ 3κ(n,m+1), that when rewriting it we
1This terminology is widely used. Notice that by definition we have κ(n, 0) = σn3 , while κ(0,m) = σ
m
2 .
60 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
obtain the next inequality, very useful to find rough upper bounds for κ(n,m) for certain
values of n and m:
κ(n,m) ≤ 3
2
κ(n− 1,m+ 1). (4)
Given any additive group G together with a generating subset H that satisfies H =
H−1, we define the Cayley graph of G with respect to H to be the graph X(G,H)
whose vertices are the elements of G, where by definition g is adjacent to gh, for all
g ∈ G and h ∈ H. In particular, if we regard Znp as the additive group G1 and select
H1 = {±e1,±e2, . . . ,±en}, where ei is the ith standard basis vector, then F np is actually
the Cayley graph of G1 with respect to H1. Similarly, if we take Zn3 × Zm2 as the additive
group G2 and select H2 = {±e1, . . . ,±en,±en+1, . . . ,±en+m}, where ei is the ith standard
basis vector, then F n,m3,2 is actually the Cayley graph of G2 with respect to H2. For more
on Cayley graphs, see Biggs [2].
3 Description of the algorithm
Our goal is to find exact values or minimal upper bounds for σnp and κ(n,m), as well as
the associated codes of the dominating subsets for the graphs F np and F
n,m
3,2 , respectively.
To simplify, we will focus on the explanation of the applied methodology used in the case
of the graph F np , because for the others graphs the ideas are completely similar.
Let V ′ be an arbitrary subset of the set of vertices V = Znp of the graph F np . It could
be that V ′ doesn’t dominate the graph F np , but the subset V ′ ∪ (V − domV ′) induced by
V ′ always dominates F np . So, we are looking for a subset V ? of the set of vertices V that
could be a solution for the following combinatorial optimization problem:
Minimize c(V ′) := |V ′|+ |V − domV ′|
subject to V ′ ⊆ V . (5)
Therefore, σnp = c(V ?), that is, the number of vertices of the solution V ? of (5). Our
simulated annealing algorithm uses adequate codification for each vertex in V , as well
as complete codification inside the computer memory of the closed neighborhoods N [v]
for each vertex. It is necessary to intensively use of codification-decodification algorithms
from decimal base to base p and base 3n × 2m, details that are explained later.
The algorithm starts selecting at random a subset V ′ of vertices, in such a way that
the inequality (1) is satisfied with c(V ′) := |V ′|+ |V − domV ′|. Next, the following step
sequence is repeated, using a parameter tk for a system “temperature”, which occasionally
decreases in order to make tk → 0 slowly, when k →∞:
1. Any vertex v ∈ V is chosen, which will give rise to a new subset of vertices V ′′ in
the following way: V ′′ = V ′ ∪ {v}, if v /∈ V ′, while V ′′ = V ′ − {v}, if v ∈ V ′.
2. Next, c(V ′′) is calculated, using the already-made calculation for c(V ′), updating it
according to the vertices dominated by the chosen vertex v. We keep the list of all
the neighbors of each vertex inside the computer memory, so this calculation is made
fast.
graph dominance by rook domains for Znp and Zn3 × Zm2 graphs 61
3. Next, we take the decision to accept or reject V ′′ according to probability equal to
min{1, e−∆c/tk}, where ∆c = c(V ′′)−c(V ′). This acceptance rule is called Metropolis
rule [1].
Here ∆c represents the change in the cost function produced by the inclusion or ex-
clusion of selected vertex v. The Metropolis rule for accepting or rejecting v states that,
if vertex v gives rise to a new subset V ′′ having less cost than V ′, then it is accepted with
probability 1. Otherwise, the new generated subset V ′′ has greater cost than V ′ and then
it is accepted only with probability e−∆c/tk , quantity which decreases to 0 when tk → 0.
The specific details of the cooling schedule are as follows:
(a) Decrease of temperature: every certain number of steps the system is cooled
down a little, decreasing the value of the temperature tk using the geometric cooling
scheme: tk+1 = λ · tk, where λ is a previously chosen constant between [0.92, 0.98]
(λ ≈ 0.95 was a good selection in almost all our experiments). This makes the
Metropolis rule become more strict each time, in the acceptance of vertices that
make the cost increase.
(b) Length of the temperature chains: the temperature parameter is updated each
nLimit steps, or when it has already accepted nOver new subsets V ′′ for which
c(V ′′) ≥ c(V ′). We successfully use values of nOver ∈ [105, 106] and nOver ∈
[5000, 50000], depending on the size of the problem.
(c) Initial temperature: the initial temperature t0 is selected at the beginning the
Metropolis rule in order to let it be more tolerant, accepting nearly χ× 100% of the
subsets V ′′ of which c(V ′′) ≥ c(V ′). Here χ is a previously chosen constant. With
this criteria, t0 = (n+1)/2 ln(1/χ). We’ve used generally χ = 0.7 with good results.
(d) Criteria to stop the algorithm: a maximum of 150 cycles of temperature are
completed, because in practice the quantity t150 = (t0)150 is almost null, although
independently of the initial value t0. Nevertheless, if for the last nCad temperature
steps a new good dominating subset V ′′ doesn’t appear, then the process is stopped.
We’re used nCad = 3 in our test with good results.
We use an additive algorithm for the generation of random numbers, proposed by
Knuth [8]. In spite that in theory, the method of simulated annealing converges to a
global minimum of the objective function c(V ) that is being minimized [1], in practice it
is necessary to run the algorithm several times to achieve good upper bounds of σnp and
κ(n,m). For example, σ63 ≤ 73 was obtained after 5 runs, and to find σ73 ≤ 186 about
200 runs were necessary. Besides, a good part of the success of these methods depends on
good calibration of the system’s parameters.
In Figure 3 the main results achieved are presented for the graph F np , and in Figure 4
we present the corresponding results for the graph F n,m3,2 . As shown in the tables of these
figures, only the cases corresponding to small values of p, n and m are studied.
3.1 Representation in base p and base 3n × 2m
A substantial part of the success of our algorithm is based on the fact we kept a complete
list of the neighbors of each vertex inside the computer main memory, coded in decimal
62 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
n Zn2 Zn3 Zn4 Zn5 Zn6 Zn7 Zn8 Zn9 Zn10
1 a1 a1 a1 a1 a1 a1 a1 a1 a1
2 a2 a3 a4 a5 a6 a7 a8 a9 a10
3 s,e2 e5 e8 e13 e18 e25 e32 e41 e50
4 e4 s,e9 e24 e52 b72 b123 b224 b390
5 e7 e27 e64 b200 b540
6 e12 b,c73 b334
7 s,e16 c186
8 e32 c486
9 c62 c1341
10 c120 c3645
11 c192 c9477
12 c380 c27702
13 c736 s59049
14 c177147
Figure 3: Best solutions for the problem of covering the graph Znp by rook domains. The
size of minimum dominating subset of Znp already known is reported in the table. The
superscripts to the left of each entry have the following meaning: “a” denotes a trivial
and exact solution; “e” denotes an exact solution found by the algorithm in 100% of the
runs; “b” denotes the best upper bound already known and also found by the author;
“c” denotes the best known upper bound, found by other authors; “s” denotes an exact
sphere-packing solution.
base. Thus, it is necessary to have efficient algorithms to run this process. Probably the
reader is familiar with the representation of natural numbers in base p, but not with the
representation of numbers in extended base 3n × 2m. Let’s make a brief summary of this
topic.
3.1.1 Representation in base p
Let s be a natural number. We shall write [s]np to denote the representation of s in base
p, using n digits p-adic d1, d2, . . . , dn. That is,
[s]np := (dn, . . . , d2, d1)p︸ ︷︷ ︸
base p
=
n∑
i=1
di p
i,
where each di ∈ {0, 1, . . . , p− 1}. The maximum natural number that can be represented
with this scheme is pn − 1. To find the p-adic digits di the efficient and classic algorithm
is the well known Euclidean division algorithm. The obtained p-adic representation is
graph dominance by rook domains for Znp and Zn3 × Zm2 graphs 63
compatible with the lexicographic order  of Znp , that is,
0 ≤ s ≤ s′ < pn =⇒ [s]np  [s′]np .
3.1.2 Representation in base 3n × 2m
Let s < 3n and s′ < 2m be two natural numbers. We shall write ([s]n3 , [s
′]m2 ) to denote the
representation of an integer a with n+m digits, from which the first n digits are ternary
(base 3) while the last m digits are binary (base 2). That is,
a = ([s]n3 , [s
′]m2 ) := (dn, . . . , d2, d1︸ ︷︷ ︸
base 3
, rm, . . . , r2, r1︸ ︷︷ ︸
base 2
) :=
m∑
i=1
ri 2i−1 +
n∑
i=1
di 3i−1 2m,
where each di ∈ Z3 and ri ∈ Z2. This definition is justified by the following result.
Proposition 1 (Base 3n× 2m) representation Every natural number a < 3n2m can be
represented as a vector of n+m coordinates as
a = ([qa]n3 , [ra]
m
2 ), (6)
where the first n coordinates correspond to the representation of a natural number qa < 3n
in base 3, while the last m coordinates correspond to the representation of a natural number
ra < 2m in base 2. The numbers qa and ra of this representation are unique.
Proof: Let’s consider the quotient qa and the remainder ra of the Euclidean division of
integer a by 2m. Therefore, we have that qa and ra are the only integers that satisfy
a = 2m qa+ ra, with 0 ≤ ra < 2m. Then, clearly ra admits a unique representation in base
2 using m digits, denoted by [ra]m2 . On the other hand,
0 ≤ 2m qa ≤ a < 3n 2m,
from which we deduce that 0 ≤ qa < 3n. Therefore, qa admits a unique representation in
base 3 using n digits, denoted by [qa]n3 .
The last representation in base 3n× 2m is also compatible with the ordinary lexicographic
order “” of Zn3 × Zm2 , in the next sense:
0 ≤ a ≤ a′ < 3n2m =⇒ ([qa]n3 , [ra]m2 )  ([qa′ ]n3 , [ra′ ]m2 ).
4 Combinatorial construction
The smallest known dominating subset of F 83 has size 486 and was found by Laarhoven et
al. [11] using simulated annealing algorithm in conjunction with a combinatorial construc-
tion, which reduces the problem to another one with less dimension. This combinatorial
construction was originally formulated by Blokhuis & Lam [3] and in theory can be applied
to any graph F np or F
n,m
3,2 , but only obtains good results in certain cases.
In this section we shall work with column vectors, instead of row vectors, because of
notation convenience.
64 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
Definition 2 Let A = [a1|a2| · · · |an] be a q × n matrix of rank q with entries from Zp.
The set S ⊆ Zqp is said to cover Zqp using A if
Zqp = {s+ αai : s ∈ S, α ∈ Zp, 1 ≤ i ≤ n}.
Note that according to this definition, when q = n and A is the identity matrix, then
S covers Zqp using A if and only if S is a dominating subset of F np . In general, we have the
next result.
Proposition 3 If S covers Zqp using A, then W = {w ∈ Znp : Aw ∈ S} is a dominating
subset of F np of size |W | = |S| pn−q.
Proof: Let w ∈ Znp . Then we shall have that Aw ∈ Zqp. By virtue of S covering Zqp using
A, there exist s ∈ S, α ∈ Zp and 1 ≤ i ≤ n such that Aw = s + α ai. Let ei be the ith
vector of the canonical base of Znp . Then, ai = Aei, from where
Aw = s+ αAei,
and therefore A(w−α ei) ∈ S. But by definition this means that w−α ei ∈W , and so w is
dominated by W in F np . Finally, by hypothesis A has rank q and therefore |W | = |S| pn−q,
because for each w ∈ S the inverse image A−1({w}) is a vector subspace of dimension
n− q and then has exactly pn−q different elements.
For example, in the graph F 83 of the football pool problem, the set S ⊆ Z43 of 6 vertices
S = {(2, 2, 2, 2)t , (2, 1, 2, 1)t , (2, 0, 1, 1)t , (0, 2, 1, 1)t , (2, 0, 1, 2)t , (1, 1, 2, 2)t}
covers Z43 using the following matrix A of size 4× 8:
A =

2 0 2 0 1 0 2 1
0 0 0 2 1 0 2 2
2 0 2 0 1 2 2 1
0 2 2 2 1 0 1 1
 .
Here q = 4. In this way Laarhoven et al. [11] found the upper bound σ83 ≤ |S| · 34 = 486.
In practice it is very difficult to find q < n and a set S ⊆ Zqp together with a matrix A of
size q×n, in such a way that S covers Zqp using A. This problem can also be formulated as
a combinatorial optimization problem, in the following way: for any given positive integer
k and a selection of r ∈ {1, . . . , n− 1}, find a subset S ⊆ Znp with k r-tuples and a matrix
r × n such that the size of the set
Zrp − {s+ α ai : s ∈ S, α ∈ Zp, 1 ≤ i ≤ n} (7)
be minimal.
Again we use a simulated annealing algorithm to solve this optimization problem: a
“move” now is either the replacement of one of the r-tuples from S (selected at random)
by other r-tuple not belonging to S, or the replacement of a column of A (selected at
graph dominance by rook domains for Znp and Zn3 × Zm2 graphs 65
random) by another column not belonging to A. If the algorithm finds a subset S and a
matrix A for which S covers Zrp using A, then the value of k is decreased by 1 and the
algorithm is executed again. The process stops when k is such that the algorithm is not
able to find a subset S and a matrix A for which the set in (7) be empty.
If we defineG = Znp andH = {±a1, . . . ,±an} then we see that S is simply a dominating
subset in the Cayley graph X = X(G,H). This graph X has the same number of vertices
than F np , but is denser. By standard results on automorphisms of Cayley graphs, we may
assume without loss of generality that ai = ei for 1 ≤ i ≤ n, so A consists of full rank
leading identity submatrices together with some additional columns. Then X is actually
equal to F np with some extra edges determined by these additional columns.
The benefits of this combinatorial construction reside in the fact that they can help
us to find dominating subsets in smaller denser graphs, where the simulated annealing
algorithm works better. Every dominating subset found in X induces another dominating
subset of F np . However, this procedure could not find all the dominating subset of F
n
p ,
because not all of them have this particular shape. So, even with this technique we could
fail to obtain the minimum dominating subset of F np or good upper bounds for their
cardinality σnp .
The algorithm just described simplifies itself a little bit if we already have the matrix A.
On the matter, Davies & Royle [5] have reported the following result, although without an
adequate theoretical justification: in order to find the matrix A the orbits of the projective
group PGL(q, p) are studied, extracting a set from it of n projective vectors a1, . . . , an of
q components. These vectors form the columns of matrix A. For these calculations they
use a computer package oriented to group theory, named Cayley.
For the graph F n,m3,2 we have a completely analog combinatorial construction, that is
described as follows.
Definition 4 Let A = [ a1|a2| . . . |an ] be a matrix of size q×n of rank q with entries from
Z3. Similarly, let B = [ b1|b2| . . . |bm ] be a matrix of size r×m of rank r with entries from
Z2. Then, S ⊆ Zq3 × Zr2 is said to cover Zq3 × Zr2 using A and B if
Zq3 × Zr2 =
{(
s1 + α ai
s2
)
:
(
s1
s2
)
∈ S, α ∈ Z3, 1 ≤ i ≤ n
}
∪
{(
s1
s2 + α bj
)
:
(
s1
s2
)
∈ S, α ∈ Z2, 1 ≤ j ≤ m
}
Proposition 5 If S covers Zq3 × Zr2 using A and B, then
W :=
{(
w1
w2
)
∈ Zn3 × Zm2 :
(
Aw1
Bw2
)
∈ S
}
is a dominating subset of F n,m3,2 of size |W | = |S| 3n−q 2m−r.
Proof: For any (x1x2 ) ∈ Zn3 × Zm2 we have (
Ax1
Bx2
) ∈ Zq3 × Zr2. So, we can find ( s1s2 ) ∈ S to
give either (
Ax1
Bx2
)
=
(
s1 + αai
s2
)
, α ∈ Z3, 1 ≤ i ≤ n,
66 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
or (
Ax1
Bx2
)
=
(
s1
s2 + α bj
)
, α ∈ Z2, 1 ≤ j ≤ m.
In the first case, taking ei the ith basis vector in Zn3 , we have(
A(x1 − α ei)
Bx2
)
∈ S,
and so (x1x2 )−α (
ei
0 ) ∈W , that means that (x1x2 ) is dominated by W in F
n,m
3,2 . In the second
case, taking ej the jth basis vector in Zm2 , we have(
Ax1
B(x2 − α ej)
)
∈ S,
and therefore (x1x2 )− α (
0
ej
) ∈ W , so (x1x2 ) is dominated by W in F
n,m
3,2 . Thus, putting the
two cases together, we see that W is a dominating subset of F n,m3,2 . Elementary linear
algebra yields that its size is |W | = |S| 3n−q 2m−r.
5 Some conclusions
In Figure 3 we present the list of upper bounds of σnp corresponding to the graph F
n
p , for
small values of p and n. Some of them are new and were obtained with our simulated
annealing algorithm. Other listed upper bounds for σnp are already known.
In Figure 4 the known results concerning upper bounds of κ(n,m) are listed. Some of
these upper bounds were also found by us in an independent way, through our simulated
annealing algorithm.
There’s still a lot of work to do, particularly on the graph F np with p ≥ 4, for which
all the upper bounds studied by us have been found directly by the simulated annealing
algorithm, without the use of combinatorial constructions described in the last section.
Actually, we are working on a more efficient program of the simulated annealing algorithm
that includes these combinatorial constructions, with the hope to find upper bounds of
σpn for other values of p and n greater than the ones already studied, and maybe improve
some of the actually known upper bounds.
Appendix: codes of some dominating subsets
Some of the codes of dominating subsets found by the author are presented here. With the
purpose of maintaining consistency with the terminology employed by other authors, we
use the compressed notation of O¨sterg˚ard & Ha¨ma¨la¨inen [12]. Let’s consider all the vectors
of Znp and Zn3 ×Zm2 , listed according to their lexicographic orders. Then, to specify a code
of dominating subsets we can simply enumerate the quantity of consecutive positions that
they have to skip in the listing.
For example, a code like “11, 0, 5, 2, . . . ” means that at the beginning we skip the
first 11 vectors before selecting the first vector, then we select the next vector, then we
graph dominance by rook domains for Znp and Zn3 × Zm2 graphs 67
Zm2 →
Zn3 ↓ 0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 e1 e2 e2 e4 e7 e12 e16 e32 e62 120 192 380 736
1 e1 e2 e,d3 e,d6 e8 e16 e,d24 e,d48 e84 160 284 548 1024
2 e,d3 e,d4 e6 e,d12 e20 e,d36 e64 124 232 408 768 1504
3 e5 e,d9 e16 e24 e48 92 171 312 576 1080 2016
4 e9 e18 e,d36 e,d72 128 238 432 d864 1296 2592
5 e,d27 e,d54 96 168 324 639 1188 d1944 d3888
6 73 132 d252 468 864 1620 d2916 d5832
7 186 333 648 d1296 2304 d4374 8586
8 486 d972 1728 d3456 6480 d12879
9 1341 d2592 4860 9639 17496
10 3645 7047 13122 25192
11 9477 18894 d37788
12 27702 52488
13 e59049
Figure 4: Better known solutions to the problem of domination of the graph Zn3 × Zm2 by
rook domains. In the table, the sizes of the known minimal subset that dominates the
graph are listed. The superscript on the left of each entry has the following meaning: “e”
indicates an exact solution found by the algorithm in 100% of the runs; “d” indicates an
upper bound of κ(n,m) derived from the inequality κ(n,m) ≤ 32κ(n− 1,m+ 1).
skip the next 5 vectors and select the next one, then we skip the next 2 vectors and select
the next one, etc.
There is an Internet site that contains the rest of the codes of dominating subsets
for the graph F n,m3,2 , that can be consulted using the “ftp” facility inside the directory
pub/graphs/pools of the Web site ftp.cs.uwa.edu.au.
6.1 σ310 = 50. Exact solution found by the algorithm in 100% of the runs.
1, 24, 11, 3, 44, 22, 43, 10, 7, 25, 13, 41, 13, 0, 23, 13, 18, 4, 13, 34, 20, 18, 15, 10, 37, 27, 44, 3, 11, 14, 28,
33, 6, 13, 20, 11, 20, 7, 4, 40, 32, 34, 13, 14, 13, 12, 15, 8, 15, 40.
6.2 σ39 = 41. Exact solution found by the algorithm in 100% of the runs.
7, 3, 25, 42, 21, 9, 19, 7, 3, 19, 7, 33, 34, 19, 14, 16, 7, 7, 37, 3, 21, 7, 11, 19, 7, 21, 34, 31, 7, 15, 5, 12, 14,
15, 25, 30, 28, 7, 14, 14, 7.
6.3 σ49 ≤ 390. Better upper bound known, found by the algorithm.
19, 8, 9, 6, 32, 5, 31, 0, 30, 9, 20, 23, 32, 30, 2, 18, 13, 24, 34, 21, 7, 7, 4, 12, 18, 46, 12, 31, 7, 2, 21, 25,
20, 3, 15, 2, 20, 13, 27, 9, 11, 23, 4, 23, 8, 21, 33, 3, 6, 12, 5, 30, 23, 14, 12, 24, 12, 3, 48, 1, 0, 3, 28, 19, 9,
0, 33, 19, 1, 1, 25, 23, 33, 6, 23, 0, 24, 27, 10, 28, 0, 4, 5, 14, 12, 36, 21, 27, 5, 11, 12, 22, 6, 5, 23, 22, 1, 2,
6, 3, 9, 29, 12, 29, 22, 42, 27, 6, 25, 4, 19, 24, 16, 1, 21, 12, 38, 16, 5, 37, 14, 5, 3, 12, 44, 9, 29, 3, 21, 27,
5, 15, 38, 42, 4, 9, 10, 21, 4, 16, 14, 26, 11, 11, 24, 21, 10, 27, 31, 32, 12, 16, 4, 10, 30, 6, 4, 19, 11, 14, 9,
5, 24, 9, 18, 8, 16, 15, 15, 24, 4, 9, 33, 11, 20, 7, 6, 22, 13, 4, 6, 42, 0, 4, 4, 6, 17, 20, 15, 0, 0, 3, 15, 34, 30,
15, 9, 33, 3, 29, 11, 13, 2, 11, 29, 6, 16, 7, 16, 24, 7, 4, 10, 27, 55, 0, 22, 7, 5, 12, 38, 15, 18, 5, 6, 54, 15, 16,
15, 9, 52, 24, 3, 30, 5, 8, 18, 18, 18, 12, 24, 2, 12, 5, 18, 36, 9, 1, 2, 25, 16, 9, 6, 3, 5, 33, 15, 17, 15, 21, 10,
7, 19, 7, 5, 48, 18, 13, 14, 13, 2, 41, 37, 13, 11, 36, 11, 7, 7, 18, 28, 5, 4, 20, 11, 22, 0, 15, 25, 16, 9, 6, 0,
10, 3, 20, 34, 28, 28, 20, 36, 6, 25, 9, 19, 5, 19, 11, 3, 42, 6, 21, 14, 28, 22, 15, 18, 1, 18, 10, 3, 9, 37, 10, 9,
68 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
31, 10, 9, 9, 43, 4, 14, 9, 8, 13, 23, 5, 33, 12, 20, 36, 2, 20, 9, 28, 3, 33, 10, 9, 1, 29, 1, 26, 31, 0, 4, 23, 28,
7, 28, 13, 6, 5, 31, 14, 4, 9, 26, 10, 13, 15, 32, 0, 19, 40, 22, 9, 41, 7, 4, 13, 24, 8, 12, 5, 21, 14, 6, 15, 40.
6.4 σ38 = 32. Exact solution found by the algorithm in 100% of the runs.
3, 5, 30, 22, 18, 11, 5, 16, 30, 8, 4, 19, 31, 3, 10, 14, 11, 14, 27, 13, 13, 3, 29, 14, 28, 6, 9, 11, 14, 6, 38, 11.
6.5 σ48 ≤ 226. Better upper bound known, found by the algorithm.
5, 34, 23, 18, 0, 24, 18, 16, 26, 8, 24, 8, 4, 5, 19, 2, 21, 6, 28, 23, 10, 32, 33, 7, 9, 14, 1, 29, 9, 20, 16, 6, 34,
20, 2, 5, 30, 24, 9, 28, 0, 19, 17, 18, 15, 33, 9, 16, 36, 2, 28, 9, 19, 18, 20, 18, 14, 9, 46, 8, 19, 8, 26, 6, 9, 1,
40, 7, 26, 0, 8, 14, 37, 3, 19, 20, 1, 21, 38, 10, 24, 2, 17, 14, 25, 4, 36, 10, 8, 35, 18, 42, 9, 4, 10, 6, 27, 45,
3, 6, 21, 23, 3, 4, 29, 23, 8, 27, 4, 17, 17, 7, 20, 31, 8, 25, 15, 5, 1, 28, 0, 23, 6, 34, 20, 8, 33, 18, 3, 34, 9,
36, 2, 28, 26, 12, 21, 7, 2, 40, 23, 35, 2, 44, 10, 24, 30, 4, 3, 22, 32, 6, 20, 6, 0, 17, 11, 10, 23, 36, 16, 6, 2,
37, 29, 12, 31, 23, 2, 31, 46, 3, 26, 28, 10, 24, 30, 8, 19, 8, 8, 2, 25, 10, 12, 34, 3, 18, 4, 42, 5, 25, 8, 26, 21,
1, 12, 33, 8, 44, 23, 34, 16, 6, 33, 10, 33, 6, 2, 10, 14, 23, 2, 8, 31, 23, 3, 34, 35, 6, 26, 31, 4, 24.
6.6 σ37 = 25. Exact solution found by the algorithm in 100% of the runs.
1, 9, 29, 2, 10, 2, 26, 9, 21, 1, 9, 31, 9, 8, 19, 3, 28, 10, 2, 10, 25, 3, 22, 8, 1.
6.7 σ47 ≤ 123. Better upper bound known, found by the algorithm.
1, 39, 13, 29, 31, 24, 0, 4, 39, 18, 9, 10, 32, 0, 29, 8, 17, 2, 26, 29, 13, 39, 23, 0, 29, 7, 29, 19, 17, 2, 39, 24,
0, 14, 9, 10, 30, 31, 16, 31, 10, 13, 11, 32, 23, 8, 0, 36, 21, 13, 1, 24, 31, 0, 20, 15, 3, 27, 14, 8, 19, 30, 25,
10, 7, 37, 22, 5, 38, 24, 32, 12, 10, 7, 27, 15, 3, 18, 38, 18, 14, 8, 30, 32, 4, 30, 33, 22, 23, 23, 24, 23, 19, 13,
1, 33, 31, 7, 31, 0, 18, 13, 11, 16, 0, 36, 17, 14, 8, 27, 10, 7, 21, 30, 23, 15, 3, 33, 32, 0, 38, 29, 22.
6.8 σ36 = 18. Exact solution found by the algorithm in 100% of the runs.
6, 9, 6, 15, 22, 4, 14, 6, 0, 28, 0, 9, 14, 25, 4, 5, 22, 7.
6.9 σ46 ≤ 72. Better upper bound known, found by the algorithm.
0, 10, 40, 8, 30, 12, 15, 14, 28, 10, 8, 0, 34, 0, 42, 14, 28, 10, 19, 8, 30, 12, 2, 10, 38, 12, 31, 6, 6, 8, 43, 16,
4, 2, 43, 10, 28, 14, 3, 6, 38, 16, 9, 4, 44, 6, 33, 8, 26, 8, 7, 4, 44, 6, 13, 6, 38, 16, 25, 14, 16, 10, 27, 16, 4,
2, 51, 6, 6, 8, 39, 12.
6.10 σ56 ≤ 540. Better upper bound known, found by the algorithm.
7, 18, 1, 9, 9, 27, 6, 11, 27, 8, 26, 7, 18, 24, 7, 15, 21, 0, 27, 15, 19, 23, 2, 9, 13, 13, 19, 2, 9, 37, 7, 5, 8, 31,
8, 35, 10, 2, 4, 15, 24, 14, 19, 6, 32, 14, 1, 26, 15, 2, 9, 9, 23, 13, 42, 1, 14, 6, 12, 14, 9, 18, 9, 16, 13, 31,
24, 3, 8, 21, 8, 34, 27, 7, 25, 11, 14, 4, 22, 21, 20, 4, 1, 31, 3, 10, 7, 15, 27, 18, 14, 7, 4, 19, 25, 4, 28, 32, 7,
7, 26, 6, 13, 16, 9, 21, 1, 12, 0, 2, 40, 5, 6, 2, 12, 14, 11, 26, 31, 10, 6, 2, 23, 16, 2, 38, 25, 9, 14, 18, 7, 5, 4,
13, 42, 20, 3, 7, 10, 3, 4, 7, 7, 17, 9, 3, 29, 13, 1, 15, 20, 9, 1, 10, 28, 15, 11, 19, 15, 6, 41, 9, 18, 16, 7, 24,
1, 6, 12, 9, 16, 16, 23, 8, 6, 6, 27, 12, 17, 6, 14, 22, 6, 4, 5, 18, 20, 6, 26, 20, 10, 0, 7, 29, 18, 10, 6, 13, 31,
8, 5, 17, 14, 18, 19, 3, 0, 22, 22, 16, 5, 4, 41, 10, 9, 13, 8, 1, 15, 21, 9, 14, 3, 48, 16, 7, 23, 8, 39, 0, 10, 11,
45, 21, 5, 12, 9, 23, 3, 10, 8, 4, 5, 16, 3, 22, 0, 21, 33, 6, 15, 4, 19, 8, 14, 14, 3, 9, 11, 21, 21, 12, 21, 27, 4,
8, 27, 5, 13, 25, 2, 7, 3, 21, 10, 4, 26, 12, 13, 0, 10, 11, 9, 3, 19, 12, 15, 9, 33, 2, 19, 20, 21, 7, 0, 24, 10, 9,
13, 19, 14, 7, 20, 22, 0, 13, 13, 10, 19, 14, 26, 18, 12, 5, 13, 16, 7, 2, 13, 17, 12, 3, 3, 33, 3, 12, 18, 24, 7,
15, 12, 14, 4, 11, 6, 3, 11, 34, 9, 5, 19, 11, 6, 9, 1, 2, 27, 7, 40, 8, 31, 8, 14, 12, 9, 1, 1, 17, 12, 15, 14, 18,
19, 6, 8, 9, 20, 8, 6, 19, 12, 9, 13, 27, 1, 21, 0, 9, 5, 15, 6, 24, 15, 16, 0, 25, 4, 31, 4, 15, 20, 14, 17, 10, 14,
7, 17, 5, 7, 15, 4, 5, 19, 1, 15, 5, 8, 10, 8, 9, 10, 3, 19, 6, 1, 16, 39, 2, 1, 14, 10, 29, 3, 27, 9, 10, 23, 6, 19, 4,
1, 10, 6, 10, 24, 1, 10, 29, 6, 13, 7, 4, 10, 29, 6, 7, 12, 33, 8, 27, 13, 10, 32, 9, 7, 26, 6, 14, 9, 17, 15, 21, 10,
9, 27, 26, 8, 18, 38, 8, 21, 14, 10, 19, 14, 2, 1, 2, 51, 9, 26, 1, 1, 18, 5, 4, 16, 15, 22, 24, 18, 18, 7, 29, 11, 9,
12, 9, 18, 4, 8, 28, 3, 10, 14, 14, 10, 21, 10, 10, 10, 3, 29, 18, 13, 13, 13, 11, 22, 33, 3, 18, 4, 2, 17, 15, 7, 4,
11, 15, 21, 6, 5, 13, 9, 28, 17, 10, 1, 12.
6.11 σ35 = 13. Exact solution found by the algorithm in 100% of the runs.
0, 7, 13, 13, 7, 7, 2, 17, 15, 1, 11, 3, 12.
6.12 σ45 = 52. Exact solution found by the algorithm in 100% of the runs.
15, 4, 8, 3, 19, 5, 26, 0, 23, 0, 14, 3, 0, 27, 24, 15, 16, 5, 19, 3, 14, 0, 27, 3, 19, 5, 2, 5, 22, 0, 32, 0, 13, 12,
5, 6, 12, 3, 8, 19, 5, 19, 5, 26, 0, 22, 1, 16, 16, 3, 19, 5.
6.13 σ55 ≤ 200. Better upper bound known, found by the algorithm.
graph dominance by rook domains for Znp and Zn3 × Zm2 graphs 69
18, 27, 3, 3, 41, 10, 4, 17, 3, 0, 3, 12, 45, 3, 38, 30, 17, 3, 11, 4, 28, 3, 8, 22, 31, 4, 28, 15, 4, 31, 3, 1, 32, 5,
32, 6, 13, 12, 4, 14, 43, 11, 4, 32, 18, 3, 10, 3, 0, 3, 28, 7, 41, 28, 18, 15, 4, 32, 3, 7, 4, 15, 44, 1, 3, 37, 7, 3,
26, 4, 14, 15, 20, 5, 7, 13, 13, 14, 7, 10, 16, 4, 16, 43, 5, 36, 3, 22, 27, 3, 1, 43, 3, 8, 4, 11, 3, 27, 4, 30, 13,
4, 33, 26, 17, 13, 3, 0, 3, 26, 10, 39, 10, 30, 0, 3, 13, 1, 40, 5, 27, 3, 0, 3, 26, 17, 0, 3, 33, 22, 21, 13, 4, 30,
6, 3, 6, 21, 4, 12, 43, 3, 1, 40, 22, 3, 27, 5, 7, 35, 8, 7, 18, 4, 33, 18, 13, 16, 2, 3, 40, 3, 17, 15, 4, 28, 8, 26,
27, 4, 28, 3, 5, 5, 4, 35, 18, 31, 3, 45, 6, 3, 0, 3, 17, 4, 12, 3, 41, 7, 0, 37, 26, 3, 6, 4, 15, 27, 5, 31.
6.14 σ34 = 8. Exact solution found by the algorithm in 100% of the runs.
0, 4, 20, 4, 11, 2, 2, 2.
6.15 σ44 = 24. Exact solution found by the algorithm in 100% of the runs.
12, 4, 1, 18, 3, 17, 5, 17, 3, 20, 1, 2, 18, 5, 18, 1, 22, 1, 13, 1, 20, 1, 20, 5.
6.16 σ54 = 64. Exact solution found by the algorithm in 100% of the runs.
7, 21, 4, 21, 21, 5, 22, 5, 14, 25, 10, 25, 9, 9, 24, 9, 19, 5, 30, 5, 13, 21, 12, 21, 16, 9, 16, 9, 17, 25, 2, 25, 5,
25, 8, 25, 9, 9, 26, 9, 14, 21, 6, 21, 21, 5, 20, 5, 27, 9, 18, 9, 17, 25, 0, 25, 16, 5, 28, 5, 13, 21, 14, 21.
6.17 σ63 ≤ 73. Better upper bound known. This is another different solution to the one already presented
in Figure 2.
8, 1, 23, 6, 3, 2, 17, 10, 18, 6, 18, 0, 10, 0, 0, 0, 27, 16, 7, 2, 9, 28, 0, 6, 0, 5, 9, 2, 6, 4, 13, 16, 12, 14, 3, 6,
2, 8, 22, 13, 12, 7, 1, 10, 15, 12, 9, 3, 17, 24, 13, 10, 7, 2, 3, 2, 6, 10, 9, 12, 8, 8, 22, 5, 4, 13, 6, 12, 1, 8, 6,
3, 19.
References
[1] Aarts, E.; Korst, J. (1990) Simulated Annealing and Boltzmann Machines. A Stochas-
tic Approach to Combinatorial Optimization and Neural Computing . John Wiley &
Sons, Chichester.
[2] Biggs, N. (1974) Algebraic Graph Theory . Cambridge University Press.
[3] Blokhuis, A.; Lam, C.W.H. (1984) “More coverings by rook domains”, Journal of
Combinatorial Theory, Series A 36: 240–244.
[4] Cameron, P.J.; van Lint, J.H. (1991) Designs, Graphs, Codes and their Links. London
Mathematical Society Student Texts, 22, Cambridge University Press.
[5] Davies, R.; Royle, G.F. (1997) “Graph domination, tabu search and the football pool
problem”, Discrete Applied Mathematics 74(3): 217–228.
[6] Garey, M.; Johnson, D. (1979) Computers and Intractability: a Guide to the Theory
of NP-Completeness. W.H. Freeman, San Francisco.
[7] Ha¨ma¨la¨inen, H.O.; Rankinen, S. (1991) “Upper bounds for football pool problem and
mixed covering codes”, Journal of Combinatorial Theory, Series A, 56: 84–95.
[8] Knuth, D.E. (1981) Seminumerical Algorithms. Second edition, volume 2 of the book
The Art of Computer Programming . Addison-Wesley, Reading, Mass.
[9] Koschnick, K.U. (1993) “A new upper bound for the football pool problem for nine
matches”, Journal of Combinatorial Theory, Series A, 62: 162–167.
70 E. Piza Rev.Mate.Teor.Aplic. (2004) 11(2)
[10] van Laarhoven, P.J.M. (1988) “Theoretical and computational aspects of simulated
annealing”, Centrum voor Wiskunde in Informatica, Tract 57.
[11] van Laarhoven, P.J.M.; Aarts, E.J.L.; van Lint, J.H.; Wille, L.T. (1989) “New upper
bounds for the football pool problem for 6, 7 and 8 matches”, Journal of Combina-
torial Theory, Series A, 52: 304–312.
[12] O¨sterg˚ard, P.R.J.; Ha¨ma¨la¨inen, H.O. (s.f.) “A new table of binary/ternary mixed
covering codes”, Preprint.
[13] O¨sterg˚ard, P.R.J. (1994) “New upper bound for the football pool problem for 11 and
12 matches”, Journal of Combinatorial Theory, Series A, 67: 161–168.
[14] O¨sterg˚ard, P.R.J. (1995) “A combinatorial proof for the football pool problem for six
matches”, Journal of Combinatorial Theory, Series A: 160–163.
[15] Piza, E.; Trejos, J.; Murillo, A. (1998) “Global stochastic optimization techniques
applied to partitioning”, in A. Rizzi et al. (Eds.) Advances in Data Science and
Classification, Springer Verlag, Berlin: 185–191.
[16] Wille, L.T. (1987) “The football pool problem for 6 matches: A new upper bound
obtained by simulated annealing”, Journal of Combinatorial Theory, Series A, 45:
171–177.