Citation
Independence domination numbers of complete grid graphs

Material Information

Title:
Independence domination numbers of complete grid graphs
Creator:
Cortés, Margaret
Publication Date:
Language:
English
Physical Description:
v, 22 leaves : illustrations ; 29 cm

Subjects

Subjects / Keywords:
Graph theory ( lcsh )
Dynamic programming ( lcsh )
Combinatorial analysis ( lcsh )
Combinatorial analysis ( fast )
Dynamic programming ( fast )
Graph theory ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaf 22).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Applied Mathematics.
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Margaret Cortés.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
31250677 ( OCLC )
ocm31250677
Classification:
LD1190.L62 1994m .C67 ( lcc )

Downloads

This item has the following downloads:


Full Text
INDEPENDENCE DOMINATION NUMBERS
OF COMPLETE GRID GRAPHS
by
Margaret Cortes
B.S., University of Colorado, Denver, 1991
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1994


This thesis for the Master of Science
degree by
Margaret A. Cortes
has been approved for the
Department of
Mathematics
by
David C. Fisher


Cortes, Margaret A. (M.S., Applied Mathematics)
Independence Domination Numbers of Complete Grid Graphs
Thesis directed by Associate Professor David C. Fisher
Abstract
Let pmyn be the minimal number of nodes in a maximal independent subset
of the m x n grid so that each node which is not an element of the subset is a
neighbor of a node in the subset. Using dynamic programming techniques this
paper finds formulas for pm that for m > 1 there are integers p, q and no such that Pm,n+P = q + pm,n fr all
n > 71q.
This abstract accurately represents the content of the candidates thesis. I rec-
ommend its publication.
Signed
David C. Fisher


To my husband Ken
for his love and support
and
To Louis, our son,
for the joy he has
brought to our lives


ACKNOWLEDGEMENTS
I would like to thank Dr. Fisher for his patience, support and encouragement,
without which this would not be possible. I would also like to thank my extended
family for always being there to help, and especially for babysitting so that I could
study. In addition I want to thank my university Professors for their time, help,
and understanding.
IV


Contents
1 Introduction 1
2 An Algorithm for Finding pm>n 2
3 Detecting Periodicity 6
4 Minimal Dominations 8
5 Results 11
5.1 Formulas for the Independence Domination Number........ . 12
5.2 Proof of Theorem 4...................................... 13
5.3 A Conjecture............................................ 20
6 References 24
v


1 Introduction
Let Pn (the line graph on n nodes) be the graph with node i adjacent to
node k if and only if [i k\ = 1. Then Pm x Pn (the complete grid graph on
m,n nodes) has mn nodes with node (i,j) adjacent to node (k,l) if and only if
\i +1 j 1\ = 1. An independent set of nodes is a subset of the nodes of G such
that any two nodes in the subset are not adjacent. A domination set, D, of a
graph, G, is a subset of nodes so that each node of G is either in D or adjacent to
a node in D. An independence domination set is a set of nodes which dominates
G and is independent. (See Farber [3].) The independence domination set is a
subset of the domination set. An independence domination set is also a maximal
independent set in the sense that if any other node were added to the set it would
no longer be independent.
Let p(G) (the independence domination number of (?) be the minimal size of
a independent dominating set of G. Then pm%n = p{Pm x Pn) is the minimum
number of stones (this nomenclature is from Chang and Clark [2]) that can
be placed on an m x n grid so each node either has a stone on it or next to
it, but two stones are not next to each other. (See Figure 1.) Let 7(G) be the
domination number, the minimal number of stones that are needed to dominate
1


G, then since any independence domination is a domination of G, 7(G) < p(G).
Figure 1 Minimum Independence Domination of a 5 X 7 grid.
The graph on the left is a independence domination of a 5 x 7 grid with 10
stones. Since Theorem 3 shows that p$j = 10, no independence domination
can have fewer stones. However, the graph on the right shows that a 5 X 7
grid can be dominated with 9 nodes though no domination with 9 nodes
form an independent set.
This paper finds formulas for pm for periodicity in an algorithm for finding pm induction gives pmiTl for a given m and for all to. Thus pm,n is calculated for an
infinite number of values in a finite amount of time.
2 An Algorithm for Finding pm^n
This section describes a dynamic programming algorithm for finding pm,. Since
finding the independence domination number of a grid graph is closely related to
finding domination numbers of complete mxn grid we considered algorithms for
domination numbers as a basis for an independence domination algorithm.
Hare, Hedetniemi and Hare [5] give a dynamic programming algorithm that
finds the domination number of a complete grid graph. Using a similar algorithm,
2


the independence domination numbers can be determined. This section presents
their algorithm revised for independence domination. A columns state is coded
by an m-vector s whose elements represent the nodes within the columns. A node
which is not dominated is coded 0; a stoneless node dominated by an adjacent
stone is coded 1; and a node with a stone is coded 2. Since a stone dominates
any adjacent node to it, the set of states for a column of m nodes is the set of all
m-digit trinary numbers that do not contain 02 nor 20. Since we are interested
in dominating every node in column n 1 by placing stones in column n, if in
column n 1 the string has a 00 combination in order to dominate the grid it
is necessary to put a 22 in the next column. 22 also can not exist by definition
of the problem. Therefore, strings containing a 00 combination are not possible.
States of all ls or states with 11 which are not preceded by a 2 cannot exist. For
example, in a 6 x n grid the state 111101 in column n could not exist because the
only way to get this string is to have 222212 in column n 1. For the algorithm
presented, here states containing 11, not preceded by a 2, are allowed to exist.
Theorem 1. The number of trinary strings of m elements which do not
include 00, 02, 20 or 22 is
_ (2)m+2 (~l)m
Proof. For m = 1, the possible states are 0, 1 or 2. So ci = 3 and the
3


equation holds. For m = 2, the possible states are 01,10,11,21 and 12 so c2 = 5
and the equation holds.
We will prove this inductively for m > 3. We first show that cm = cm_x +
2cm_2. All of the states for a column of m nodes end with 0, 1 or a 2. For the
states that end with 1, we can remove the 1 and obtain all possible states on
m 1 nodes. So the number of states ending with a 1 on m nodes is equal to the
number of states onm-1 nodes. Similarly, the strings of length m ending in 0
or 2 must be preceded by a 1, taking away the 10 or 12 would give any string of
length m 2. Therefore, cm = cm_i + 2cm_2
Now assume that
_ (2)m+1 (-l)7"-1
^m1 -
and
Cm2
(2)-(1)J
3
Then by induction we have
(2)m+1 (-1)"-1 (2) (-1)
3 : + i 3
2
(2)m+i _ 2(2)m + 2(l)m-2
3 + 3
_ (2)m+2 (~l)m n
3
For all states s, let an s-domination of Pm x Pn be a set of stones that inde-
pendently dominate the first n 1 columns and leaves column n in state s. Let
4


Pm,n(s) be the minimum size of an s-domination of Pm X Pn. Then there are 3
stages of the algorithm given by Hare, Hedetniemi, and Hare.
1. Initialization. It is simplest to initialize a fictitious column 0. Since
column 0 has neither stones nor undominated nodes, all nodes may be
coded 1. Let 1 be the state of all ones. Then /?m,o(l) = 0. Since no other
states are possible, let /9m,o(s) = oo for all s 1.
2. Iteration. Let |s| be the number of twos in a state s (i.e., the number of
stones in the column). Given a state t, suppose the stones of s are added
in column n to a t-domination of Pm x Pn-i If column n 1 is dominated,
let u(t,s') be the state formed in column n. The s' vector is a binary
representation of nodes in column n with a zero symbolizing no stone and a
one representing a stone. Together with t this binary vector gives the state
in column n (e.g., u(1210112,0001000) = 0112101). Then for all n > 1, we
have:
pm,(s) = |s|+ min (t).
u(t,S')=B
3. The domination number. A state s' beats state s (notated s' > s) if
each element of s' is greater than or equal to the corresponding element of
s. Then the set of states with s > 1 is the set of all possible final columns
in a domination of Pm x P. Therefore,
pm,n : nunpm,n(s).
5


Table 1 illustrates the algorithm for m = 3 and n < 7. There are 11 states.
The interior shows p3,n(s) for each state s and for each column n. States that
cannot be achieved are indicated by oo. Then p3 is the minimum of p3n(s) for
states s which beat 111 (shown by *). Thus p3)1 = 1, p3]2 = 2, p3)3 = 3, p314 = 4,
P3,5 - 4, p3t6 = 6, p3j = 6.
Table 1. The Algorithm for m = 3.
s 0 1 2 3 4 5 6 7
010 oo oo 1 3 3 4 4 6
Oil oo oo oo oo oo oo oo oo
101 oo oo 2 3 3 5 5 6
110 oo oo oo oo oo OO' oo oo
210 oo 1 2 4 4 5 5 7
012 oo 1 2 4 4 5 5 7
111 1 oo oo oo oo oo oo oo
112* oo oo 2 3 4 5 5 6
211* oo oo 2 3 4 5 5 6
121* oo 1 3 3 4 4 6 6
212* oo 2 3 3 5 5 6 6
How quickly can the algorithm find pmi ? For independence domination there
is a Fibbonacci number of possible binary combinations to produce state n which
will maintain an independent set. Thus, it takes 0((1~^v^)m) computations to
find u(t,s'). For each state s, there are up to 2m states t with u(t,s') = s.
Since there are 0(2m) states and n iterations, the computational complexity is
0(2m(14^I)mn)= +
6


3 Detecting Periodicity
Notice that in Table 1 the values in columns 3 and 7 differ by 3. Since the values
in column n only depend on the values in column n 1, the values in columns 4
and 8 will also differ by 3. Continuing this argument, the values in columns n 4
and n differ by 3 for all n > 7. Thus p3i = p3i_4 + 3 for all n > 7. This together
with the values of p3] for n < 9 gives an induction proof that p3) = [(3n + l)/4]
for all n.
Theorem 2. If for some p, q and nQ we have pm)0+p( s) pm,n0(s) = ? for all
states s, then />m,n+P(s) pm,n(s) = q for all states s and for all n > no.
Proof. The result is true for n = no.
For n > n0, assume for sake of induction that
/,m,n-l+p(s) = Pm,n-l(s) h 9
for all states s. Then
Pm,n+p(s) ~
= mia (|s| + q + minpm,n_i(s/)J
= q + nun ^|s| + msinpm,n_i(s')^ = q + pm,n{s).
Corollary. If for some p, q and n0 we have that pm,no+p( s) Pm.no (s) = 9 for a^
states s, then pm,n+P = Pm.n + 9 for oil n>nQ.
Ms| + nunpm,n_i+p(s,)J
7


Proof.
Pm,n+p = minpm,n+p(s) = min(g + pm,n(s))
= q + min /om,(s) = q + pm,n D
4 Minimal Dominations
Even with Theorem 2, it is difficult to find a minimal independence domination
of an m x n grid for all n.
The program in this paper modifies the algorithm to store backtracking in-
formation to give minimal dominations of grids for all n up to a certain point.
We recursively expand on these results to find a minimal independence domina-
tion for m x n grids for a given m and for all n. (This is actually quite difficult
because we generate only one of what is usually many minimal independence
dominations).
For m,ra > 8, Chang [1] gives a construction which dominates an m x n
grid with [(m + 2)(n + 2)/5j 4 stones. We also prove that this is a bound for
independence domination numbers.
Theorem 3.
(m + 2 )(n + 2)
Pm,n _ ^ ^
for m,n> 12.
8


Proof. Changs proof holds for all but two cases for independence domination.
The proof given here uses the same method as Chang.
Given a grid graph of size m x n, consider the (m + 2) x (n + 2) board. We
will label the rows from top to bottom starting with 0, and the columns from left
to right starting with 0. Thus the upper left corner of the graph is (0,0).
Consider a five coloring of the graph. The nodes which are colored the same
can be used to form an independence set of nodes. Since the argument is the same
for all corners of the grid it is necessary to look at only one corner. The idea is to
select the set of nodes whose magnitude is the smallest of the five possibilities on
the (m + 2) X (n + 2) graph, and then adjust the outer row and columns in order
to dominate the mxn graph. It will be necessary to remove one stone from each
side of the graph for the independence domination. The pictures below show how
the independence domination set is constructed for each coloring:
9


10


The last step is to push in any remaining side stones from the perimeter.
Thus you have the given equation as the bound for the independence domination
number.
5 Results
A program was written implementing the algorithm described in Section 3. It
found pmyn for all m < 14 in approximately 92 cpu hours on the Vax 8800. These
results are summarized in Theorem 4.
11


5.1 Formulas for the Independence Domination Number
Theorem 4 gives the independence domination number of m x n grid graphs for
all m and n with m < 14. Since pn min(m,n) < 14.
Theorem 4. For all m < n with m < 14, we have
Pm,n
fl
^1
3n+l
4
3n+l
4
n
n + 1
6n+4
+ 1
41!
15n+9~|
8 I
16
21n+12
5 I
10n+6
7
10n+4
- 1
10
21n+12
10
21n+12
10
7n+2
+ 1
- 1
7n+2
+ 1
28n-f-15
11
28n+15
11
36r+16
13
3n + 2
3n + 1
+ 1
ifm = 1
if m = 2
if m 3 and n mod 4^2
ifm = 3 and n mod 4 = 2
if m = 4 and n ^ 5,6,9
if m = 4 and n = 5,6,9
ifm = 5
if m = 6 and n mod 7^1 and n / 7
if m = 6 and n mod 7 = 1 and n = 7
ifm = 7
if m = 8 and n ^ 8
zf m 8 and n 8
ifm = 9 and n mod 10 ^ 1,7
ifm = 9 and n mod 10 = 7
ifm = 9 and n'mod 10 = 1
ifm = 10 and n mod 9^3 and n 7^ 18
ifm = 10 and n mod 9 = 3 and n = 18
ifm = 11 and n mod 11/3
if m 11 and n mod 11 = 3
if m~ 12
if m = 13 and n mod 3/1
if m = 13 and n mod 3 = 1
ifm = 14.
12


5.2 Proof of Theorem 4
Since the results of the program are being offered as a proof, the program re-
quires the same scrutiny normally reserved for other constructions used to prove
mathematical results. Because the program is quite short, the easiest way to do
this is to present an annotated version of the program (see Table 2).
Table 2. The Program for Theorem 4
program inddom(input, output);
const inmax =50; maxstate =43890; nmax=300;
type vector=array[-l.,mmax] of integer;
states=array[-l..maxstate,-1..nmax] of integer;
var a,back:states; b,c,d,nextstate,fib:vector;
diff,upper,n,stone,domnum,numst ates,i,m,sum,binary
j,k,count:integer; flag,flag2,pat:boolean;
procedure encode(var a:states; var b,c:vector;
var m,sum:integer);
var j,k,temp:integer;
begin
sum:=0; j:=m;
while j>0 do begin
temp:=l;
if c[j]=i then begin sum:=sum+b[j-2]; j:=j-l; end
else if c[j]=2 then begin
for k:=i to j do temp:=temp*2;
sum:=sum+temp;
j:=j-2;
end
else j:=j-2;
end;
a[sum,-l] :=sum;
end;
procedure decode(var c,b:vector; m,sum:integer);
var temp, j:integer;
begin
k:=m;
while k>0 do begin
temp:=l;
for j:=l to k do temp:=temp*2;
if temp<=sum then begin
13


c [k] : =2; c[k-l]:=l;
k:=k-2; sum:=sum-temp;
end
else if b[k-2]<=sum then begin
c[k]:=i; sum:=sum-b[k-2]; k:=k-i;
end
else begin c[k]:=0; c[k-1]:=1; k:=k-2; end;
end;
end;
The procedures encode and decode allow the states to be stored as integers.
Encode changes each possible state of length m into an integer value and stores
that integer until to program needs to use that state. As the program needs to
work with a particular state, it decodes the integer. It was desirable to encode
the state in such a way that the smallest number, that with no 2, and the least
number of ones to be 0. For m = 3 that would be 010. The encoding procedure
starts from position m, the far right, and moves left. The encoded number is
determined by the following algorithm:
1. Initialization Let encode = 0 and k = m .
2. The Encoding Step This step is repeated until k < 0. If the A;th position
is 2 then encode = encode -1- 2k and k = k 2. If the fcth position is 1
then, encode = encode + cm_2 and k = k 1. If the fcth position is 0 then,
encode = encode+0 and k = k 2.
2 is subtracted from k for 0 and 2 because the k 1 position must be 1, but
for the case when it is 1 then the k 1 position could be either 0, 1 or 2. For
14


example, suppose the string is 1121012 and m = 7.
1. encode = 0 and k = 7
2. 2 is in the seventh position, so encode = 0 + 27 = 128, k = 7 2 = 5. 0
is in the fifth position, so encode = 128 + 0 = 128, k = 5 2 = 3. In the
third position is a 2 so encode = 128 + 23 = 136, k = 3 2 = 1. 1 is in the
first position, so encode = 136 + C\ = 136 + 3 = 139, k 1 1 = 0.
The encoded version of this string is 139. To decode the string:
1. Initialization Let k = m and a; = 0 for all i = l,...,m.
2. The Decoding Step This is repeated until k < 0. Is 2k < encode? If yes,
then a,k = 2, a*-i = 1 and k = k 2. If not then, is cm < encode? If yes,
then dk = 1 and k = k 1. Otherwise a* = 0, dk-\ = 1 and k = k 2.
begin
Writeln (Enter the length of the string);
readln (m);
b[-i] :=1; b[0] :-l;
for i:=l to m do begin
if i mod 2=0 then b[i]:=b[i-l]*2-l
else b[i] :=b[i-l]*2+l;
end;
numstates:=b[m]; n:=0;
nextstate[0]:=1;
fib[0] :=1; fib[l] :=1;
for j:=2 to m+1 do
fib[j] :=fib[j-l]+fib[j-2] ;
upper:=f ib[m+1]-1;
for i:=0 to numstates-1 do a[i,-l]:=i;
for i:=0 to numstates-1 do
for k:=0 to nmax do a[i,k]:=9999;
for i:=i to m do c[i]:=l;
15


encode(a,b,c,m,sum);
a[sum,0]:=0;
This section of the program receives input and initializes the arrays and vec-
tors used. Vector b stores the possible number of states for m. The vector fib
stores the number possible binary combinations which do not have two ls, which
are stones, next to each other i.e., for 2 x n the states are 00, 10, 01). Array a
stores the minimum number of stones needed to independent dominate, so it is
initialized to 99999.
repeat
n:=n+l;
for i:=0 to numstates-1 do begin
for k:=0 to m+1 do d[k]:=0;
decode(c,b,m,i);
for count:=0 to upper do begin
binary:=count;
flag:=true; stone:=0;
stone:=stone+a[i,n-l] ;
for j:=l to i do begin
If binary>=fib[m+i-j] then begin
d [j]:=1; binary:=binary-fib[m+1-j];
end
else d[j]:=0;
end;
The above program section first decodes the state and stores it in c. It then
initializes a binary vector, d, to all 0s. It will test the binary string as a possible
state for n and then update the binary number by putting 1 in the first position.
Each pass through the loop will create a new binary string to test. It repeats the
loop until all possible binary strings have been tried.
16


for k:=l to m do begin
if (c[k]=2) and (d[k]=l) then flag:=false;
if (c[k]=0) and (d[k]=0) then flag:=false;
if flag then begin
if d[k]=l then
begin
nextstate[k]:=2;
stone:=stone+i;
end;
if d[k]=0 then
if (c[k]=2) or (d[k+i]=l) or (d[k-l]=i) then
nextstate[k]:=1
else nextstate[k] :=0;
if (nextstate[k]=0) and (nextstate[k-i] =0) then
flag:=false;
end; -[if flag}
end;
It is necessary to determine if there are two stones next to each other and to
make sure that all undominated nodes in n 1 will be dominated by the state
in n. If the binary string fails to dominate the nodes in n 1 then the program
abandons the binary string. In order to check the independent condition the
program checks to make sure that c, and <£, do not have a 2 and a 1 respectively.
If independence has not been violated, then the program determines the trinary
state which has been produced in n. Any d, which has a 1 will produce a 2 in
nextstatei. Otherwise, if there there is a 2 in the previous state or a 1 above or
below the position the that program is looking at, the position is a 1, otherwise
0 is placed in the position.
if flag then begin
encode(a,b.nextstate,m,sum);
if stone begin
a[sum,n] :=stone;
17


back[sum,n] :=i;
end;
end;
end; {while loop}
end; {outside for loop}
If the number of stones is less than what is currently stored in a then update
a with the smaller number of stones. The array back stores the state which leads
to the number of stones placed in a. For example suppose the program started
with 121 and then found a possible next state, 212, a stores the value 3 for the
number of stones. If later, the program discovers that 010 is also a possible next
state, the value in a is changed to 1 and in back the encoded value for 121 is
stored.
domnum:=9999;
for i:=0 to numstates-1 do begin
flag2:=true;
decode(c,b,m,i);
for k:=i to m do if c[k]=0 then flag2:=false;
if flag2 and (a[i,n] domnum:=a[i,n]; sum:=i;
end;
end;
Once the program updates the matrix for n, it finds the minimum indepen-
dence domination number for the m x n grid by comparing the end states. Flag2
requires that the program only consider s > 1, which are the ending states.
for i:=l to n do begin
decode(c,b,m,sum);
for j:=l to m do begin
If c[j]=2 then write(* 1)
else write(- );
end;
18


sum:=back[sum,n-i+l] ;
writeln
end;
Using back the program determines the patterns used to create the final
state and thus the pattern which produced the lowest domination number. For
example suppose that 3 x n is size of the grid and the program perceives 212 as
the ending state. What state produced 212 can be determined by checking what
is stored in back. Suppose that back had a 010, then the program looks to see
where the 010 is from etc.
i:=n-l;
pat:=false;
while (not pat) and (i>0) do begin
diff:=a[0,n]-a[0,i];
j:=0;
repeat
if aCj ,n]-a[j ,i]=diff then pat:=true
else if (a[j ,i]=9999) and (a[j ,n]=9999)
then pat:=true
else pat:=false;
j:=j+l;
until (not pat) or (j >numstates-l);
i:=i-l;
end;
write(The domination number for an ,m:0,ac*,n:0, is ');
writeln(domnum:0);
until pat;
writeln(The ,n:0,' and ,i+l:0, differ by diff:0)
The final section of the program checks to see if the pattern has repeated for
every possible state by the same amount; if so, it stops the program and records
the recursion relation.
19


Table 3 gives the results of this program. To save space, the independence
domination numbers have been put into rows of 20. So for example, p81 = 3,
P&,2 5, ^8,3 = 7, ^8,4 = 8, ..., ps,2o = 39, ps,2i = 41, Ps,22 43 and ps,23 = 45.
Following this is the first instance where pm n + q = pm,n+p-
Table 3. The Output of the Program.
1 1 1 2 - 2 2
p(l, n +; 3) = p(l> n) + 1 for n > 3
1 2 2 3
p( 2, n + : 2) = p(2, n) + 1 for n > 2
1 2 3 4 4 6 6
p(3, n + *) = p(3, n) + 3 for n > 3
2 3 4 4 6 7 7 8 10 10 11 12
p(4, n +: 0 = p(4, n) + 1 for n > 11
2 3 4 6 7 8 10 11 12 13 14 16 17 18 19 20 22 23
p( 5, n + 1 5) = P(5. n) + 6 for n > 13
2 4 6 7 8 10 11 12 14 16 17 18 20 22 22 24
P(6, n + ' ?) = P(6, n) + 10 for n > 9
3 4 6 7 10 11 12 14 16 17 19 21 22
P(r, n +; 3) = p( 7, n) + 5 for Tl > 10
3 5 7 8 11 12 14 16 18 20 22 24 26 28 30 32 33 35 37 39
41 43 45 47
p(8, n + l 3) = p(8, n) + 15 for n > 16
3 5 7 10 12 14 16 18 21 23 24 27 29 31 33 35 38 39 42 44
45 48 50 52 54 56 59 60 63 65
p( 9, n +: io) = = p(9 , n) + 21 for n > 20
4 6 9 10 13 16 17 20 23 24 27 30 31 34 36 38 41 44 45 48
51 52 55 57 59 62 64 66 69 72 73 76 78 80 83 85 87 90 92 94
97 99 101 104 106 108
p(l0 l,n + 9) - = p(l0, n) + 21 fro n > 37
4 6 9 11 14 17 19 22 24 27 30 32 35 38 40 43 45 48 50 53
55 58 60 63 66 68 71 73 76 78 81 83 86 88 91 . 94 96 99 101 104
106 109 111 114 116 119 122 124 127 129 132
p(ll ,n + 11) = P(ll," ) + 28 for n > 40
4 7 10 12 16 18 21 24 27 30 32 35 38. 40 43 46 49 52 54 57
60 63 65 68 71 74 76 79 82 85 88 90 93 96 99 101 104 107
p(12 !,n + 13) = R(l2,n) + 36 for n > 25
5 7 10 13 17 20 22 26 29 31 35 38 40 44 47 49 53 56 58 62
65 67 71 74 76 80 83 85 89 92 94 98 101 103 107 110 112 116 119 121
125 128 130 134 137 139 143 146 148 152 155 157 161 164 166 170 173 175 179 182
184 188 191 193 197 200 202 206 209 211 215 218 220
p(13 l,n + 12) = p(13,n ) + 36 for 71 > 61
5 8 12 14 18 22 24 28 31 34 38 40 44 47 50 53 56 60 63 66
69 72 76 79 82 85 88 92 95 98 101 104 108 111 114 117 120 124 127 130
133 136 140 143 146 149 152 156 159 162 165 168 172 175 178 181 184 188 191 194
197 200 204 207 210 213 216 220 223 226 229 232 236 239 242 245 248 252 255 258
261 264 268 271 274 277 280 284
p(14,n + 5) = p(14,n) + 16 for n > 83
20


5.3 A Conjecture
Fisher[4] showed that the minimum domination number of a grid graph for n
16,17,18,19 is
(m+2)(n+2)
5
4. This leads to the following theorem:
Theorem 4. The independence domination number of ah m x n grid graph
is
Pm,n
(m + 2)(ra + 2)
-4
for m = 16,17,18,19 and m < n.
Proof. Since the set of independence dominations is a subset of the domina-
(m+2)(n+2)
5
-4,
tion set we know that 7m <
and Fisher showed that 7m,n = |^m-2Xn+2) j 4 or m = 16,17,18,19 so pm,n =
4/orm=16, 17, 18, 19.
(m+2)(n+2)
5
The fact that the bound is the minimum for m = 14 and m = 16,17,18,19
leads us to believe for m = 15 and for m > 20 that the upper bound will be the
minimum independence domination number. We state this belief in the following
conjecture. This is similar to a conjecture given by Fisher[4].
Conjecture 1. For all m,n> 14,
Pm,n
(m + 2)(n + 2)
5
-4.
21


6
References
1. Chang, T.Y., Domination Numbers of Grid Graphs, Ph.D. Thesis, Depart-
ment of Mathematics, University of South Florida, 1992.
2. Chang, T.Y., W.E. Clark h E.O. Hare, Domination Numbers of Complete
Grid Graphs I, Ars Combinatoria (to appear).
3. Farber, M. Domination, Independent Domination and Duality in strongly
Chordal Graphs, Discrete Appl. Math. 7 (1984) 115-1130.
4. Fisher, D.C. The Domination Number of Complete Grid Graphs, submitted
to Journal of Graph Theory.
5. Hare E.O., S.T. Hedetniemi and W.R. Hare, Algorithms for Computing the
Domination Number of K x N Complete Grid Graphs, Congressus Numer-
atium 55 (1986) 81-92.
22


Full Text

PAGE 1

INDEPENDENCE DOMINATION NUMBERS OF COMPLETE GRID GRAPHS by Margaret Cortes B.S., University of Colorado, Denver, 1991 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1994

PAGE 2

This thesis for the Master of Science degree by Margaret A. Cortes has been approved for the Department of Mathematics by David C. Fisher Richard Lundgren

PAGE 3

Cortes, Margaret A. (M.S., Applied Mathematics) Independence Domination Numbers of Complete Grid Graphs Thesis directed by Associate Professor David C. Fisher Abstract Let Pm,n be the minimal number of nodes in a maximal independent subset of the m x n grid so that each node which is not an element of the subset is a neighbor of a node in the subset. Using dynamic programming techniques this paper finds formulas for Pm,n for all m :::; 14. This is done by recursively proving that for m ?: 1 there are integers p, q and n0 such that Pm,n+p = q + Pm,n for all This abstract accurately represents the content of the candidate's thesis. I rec-ommend its publication. David C. Fisher 11

PAGE 4

To my husband Ken for his love and support and To Louis, our son, for the joy he has brought to our lives

PAGE 5

ACKNOWLEDGEMENTS I would like to thank Dr. Fisher for his patience, support and encouragement, without which this would not be possible. I would also like to thank my extended family for always being there to help, and especially for babysitting so that I could study. In addition I want to thank my university Professors for their time, help, and understanding. IV

PAGE 6

Contents 1 Introduction 2 An Algorithm for Finding Pm,n 3 Detecting Periodicity 4 Minimal Dominations 5 Results 5.1 5.2 5.3 Formulas for the Independence Domination Number Proof of Theorem 4 A Conjecture , 6 References v 1 2 6 8 11 12 13 20 24

PAGE 7

1 Introduction Let Pn (the "line graph" on n nodes) be the graph with node i adjacent to node k if and only if li-kl = 1. Then Pm x Pn (the complete grid graph on m,n nodes) has mn nodes with node (i,j) adjacent to node (k,l) if and only if li-kl + lj -II = 1. An independent set of nodes is a subset of the nodes of G such that any two nodes in the subset are not adjacent. A domination set, D, of a graph, G, is a subset of nodes so that each node of G is either in D or adjacent to a node in D. An independence domination set is a set of nodes which dominates G and is independent. (See Farber [3].) The independence domination set is a subset of the domination set. An independence domination set is also a maximal independent set in the sense that if any other node were added to the set it would no longer be independent. Let p( G) (the independence domination number of G) be the minimal size of a independent dominating set of G. Then Pm,n = p(Pm x Pn) is the minimum number of "stones" (this nomenclature is from Chang and Clark [2]) that can be placed on an m x n grid so each node either has a stone on it or next to it, but two stones are not next to each other. (See Figure 1.) Let ((G) be the domination number, the minimal number of stones that are needed to dominate 1

PAGE 8

G, then since any independence domination is a domination of G, !(G) :S p(G). Figure 1 -Minimum Independence Domination of a 5 X 7 grid. The graph on the left is a independence domination of a 5 x 7 grid with 10 stones. Since Theorem 3 shows that p5 ,7 = 10, no independence domination can have fewer stones. However, the graph on the right shows that a 5 X 7 grid can be dominated with 9 nodes though no domination with 9 nodes form an independent set. This paper finds formulas for Pm,n for all m :S 14. This is done by looking for periodicity in an algorithm for finding Pm,n. When periodicity is detected, induction gives Pm,n for a given m and for all n. Thus Pm.n is calculated for an infinite number of values in a finite amount of time. 2 An Algorithm for Finding Pm,n This section describes a dynamic programming algorithm for finding Pm,n. Since finding the independence domination number of a grid graph is closely related to finding domination numbers of complete m x n grid we considered algorithms for domination numbers as a basis for an independence domination algorithm. Hare, Hedetniemi and Hare [5] give a dynamic programming algorithm that finds the domination number of a complete grid graph. Using a similar algorithm, 2

PAGE 9

the independence domination numbers can be determined. This section presents their algorithm revised for independence domination. A column's state is coded by an m-vector s whose elements represent the nodes within the columns. A node which is not dominated is coded 0; a stoneless node dominated by an adjacent stone is coded 1; and a node with a stone is coded 2. Since a stone dominates any adjacent node to it, the set of states for a column of m nodes is the set of all m-digit trinary numbers that do not contain 02 nor 20. Since we are interested in dominating every node in column n 1 by placing stones in column n, if in column n 1 the string has a 00 combination in order to dominate the grid it is necessary to put a 22 in the next column. 22 also can not exist by definition of the problem. Therefore, strings containing a 00 combination are not possible. States of all 1 's or states with 11 which are not preceded by a 2 cannot exist. For example, in a 6 x n grid the state 111101 in column n could not exist because the only way to get this string is to have 222212 in column n 1. For the algorithm presented, here states containing 11, not preceded by a 2, are allowed to exist. Theorem 1. The number of trinary strings of m elements which do not include 00, 02, 20 or 22 is Proof. Form 1, the possible states are 0, 1 or 2. So c1 = 3 and the 3

PAGE 10

equation holds. For m = 2, the possible states are 01, 10, 11,21 and 12 so c2 = 5 and the equation holds. We will prove this inductively for m ::0: 3. We first show that em = Cm-l + 2cm-Z. All of the states for a column of m nodes end with 0, 1 or a 2. For the states that end with 1, we can remove the 1 and obtain all possible states on m-1 nodes. So the number of states ending with a 1 on m nodes is equal to the number of states on m -1 nodes. Similarly, the strings of length m ending in 0 or 2 must be preceded by a 1, taking away the 10 or 12 would give any string of length m-2. Therefore, Cm = Cm-1 + 2cm-2 Now assume that and (2)'" ( -l)m-2 Cm-2 = 2 3 Then by induction we have (2)m+1 ( -1)m-1 (2)m ( -1)m-2 Cm= 3 +2 3 (2)m+I( -1)'"-1 2(2)m + 2( -1)'"-2 = 3 + 3 (2)'"+2 -( -1 )m 0 -3 For all states s, let an s-domination of Pm x Pn be a set of stones that inde-pendently dominate the first n -1 columns and leaves column n in state s. Let 4

PAGE 11

Pm,n ( s) be the minimum size of an s-domination of P m x Pn. Then there are 3 stages of the algorithm given by Hare, Hedetniemi, and Hare. 1. Initialization. It is simplest to initialize a fictitious column 0. Since column 0 has neither stones nor undominated nodes, all nodes may be coded 1. Let 1 be the state of all ones. Then Pm.o(l) = 0. Since no other states are possible, let Pm,o(s) = oo for all s fo 1. 2. Iteration. Let lsi be the number of twos in a states (i.e., the number of stones in the column). Given a state t, suppose the stones of s are added in column n to at-domination of Pm x Pn-l If column n -1 is dominated, let u( t, s') be the state formed in column n. The s' vector is a binary representation of nodes in column n with a zero symbolizing no stone and a one representing a stone. Together with t this binary vector gives the state in column n (e.g., u(1210112,0001000) = 0112101). Then for all n > 1, we have: Pm,n(s) =lsi+ min Pm,n-l(t). u(t,s');s 3. The domination number. A state s' beats state s (notated s' 2: s) if each element of s' is greater than or equal to the corresponding element of s. Then the set of states with s 2: 1 is the set of all possible final columns in a domination of Pm X Pn. Therefore, Pm n = min Pm n(s). ' 5

PAGE 12

Table 1 illustrates the algorithm for m = 3 and n ::; 7. There are 11 states. The interior shows p 3 ,n(s) for each states and for each column n. States that cannot be achieved are indicated by oo. Then p3,n is the minimum of P3,n(s) for states s which beat 111 (shown by*). Thus P3,l = 1, P3,2 = 2, P3,3 = 3, P3,4 = 4, P3,5 = 4, P3,6 = 6, P3,7 = 6. Table 1. The Algorithm for m = 3. s 0 1 2 3 4 5 6 7 010 oo1oo 1 I 3 3 4 4 6 011 \oo 00 00 00 00 00 1! 00 00' 101 loo 00 2 3 3 5 5 6 i 110 00 00 00 00 00 00 oo1oo ' 210 1 I 2 4 4 5 5 7 00 012 oo 1 1 2 i 4 4 I 5 5 7 i 111 1 00 00 00 00 00 00 00 112* oo]oo\ 2 3 4 5 5 6 21h 00 00 2 3 4 I 5 5 6 12h 00 1 3 3 4 4 6 6 I I 212* 1 oo 2 3 3 i 5 5 I 6 6 How quickly can the algorithm find Pm,n? For independence domination there is a Fibbonacci number of possible binary combinations to produce staten which will maintain an independent set. Thus, it takes 0( ( 1+2v'5)m) computations to find u(t,s'). For each states, there are up to 2'" states t with u(t,s') = s. Since there are 0(2m) states and n iterations, the computational complexity is 6

PAGE 13

3 Detecting Periodicity Notice that in Table 1 the values in columns 3 and 7 differ by 3. Since the values in column n only depend on the values in column n-1, the values in columns 4 and 8 will also differ by 3. Continuing this argument, the values in columns n-4 and n differ by 3 for all n 7. Thus p3,n = p3,n_4 + 3 for all n 7. This together with the values of P3,n for n < 9 gives an induction proof that P3,n = f(3n + 1)/41 for all n. Theorem 2. If for some p, q and no we have Pm,no+P(s)Pm,n0(s) = q for all states s, then Pm,n+p(s)Pm,n(s) = q for all states s and for all n Pro of. The result is true for n = n0 For n > n0 assume for sake of induction that Pm,n-J+p(s) = Pm,n-l(s) + q for all states s. Then Pm,n+p(s) = mjn (lsi+ mjnPm,n-Hp(s')) = mjn (lsi+ q + mjnPm,n-J(s'J) = q + mjn (lsi+ rnjnPm,n-!(s'J) = q + Pm,n(s). D Corollary. If for some p, q and no we have that Pm,no+P(s)Pm,n0(s) = q for all states s 1 then Pm,n+p = Pm,n + q for all n no. 7

PAGE 14

Proof. Pm n+p =min Pm n+p(s) = min(q + Pm n(s)) ' s2::1 4 Minimal Dominations Even with Theorem 2, it is difficult to find a minimal independence domination of an m x n grid for all n. The program in this paper modifies the algorithm to store backtracking information to give minimal dominations of grids for all n up to a certain point. We recursively expand on these results to find a minimal independence domination for m x n grids for a given m and for all n. (This is actually quite difficult because we generate only one of what is usually many minimal independence dominations). For m, n ?: 8, Chang [1] giVes a construction which dominates an m x n grid with l(m + 2)(n + 2)/5J -4 stones. We also prove that this is a bound for independence domination numbers. Theorem 3. < l(m+2)(n+2)j _4 Pm,n S form, n ?: 12. 8

PAGE 15

Proof. Chang's proof holds for all hut two cases for independence domination. The proof given here uses the same method as Chang. Given a grid graph of size m x n, consider the ( m + 2) x ( n + 2) board. We will label the rows from top to bottom starting with 0, and the columns from left to right starting with 0. Thus the upper left corner of the graph is (0,0). Consider a five coloring of the graph. The nodes which are colored the same can be used to form an independence set of nodes. Since the argument is the same for all corners of the grid it is necessary to look at only one corner. The idea is to select the set of nodes whose magnitude is the smallest of the five possibilities on the ( m + 2) x ( n + 2) graph, and then adjust the outer row and columns in order to dominate the m x n graph. It will be necessary to remove one stone from each side of the graph for the independence domination. The pictures below show how the independence domination set is constructed for each coloring: It l 9

PAGE 16

' -- i i I 4 -- 10

PAGE 17

L -.. 4 The last step is to push in any remaining side stones from the perimeter. Thus you have the given equation as the bound for the independence domination number. 0 5 Results A program was written implementing the algorithm described in Section 3. It found Pm,n for all m :':: 14 in approximately 92 cpu hours on the Vax 8800. These results are summarized in Theorem 4. 11

PAGE 18

5.1 Formulas for the Independence Domination Number Theorem 4 gives the independence domination number of m x n grid graphs for all m and n with m :S:: 14. Since Pn,m = Pm,n, this gives Pm,n for all m and n with min( m, n) :S:: 14. Theorem 4. For all m ::; n with m ::; 14, we have ifm = 1 r "t1 1 ifm = 2 f3"t 1 if m = 3 and n mod 4 f 2 r3ntl1 + 1 if m = 3 and n mod 4 = 2 n if m = 4 and n f 5, 6, 9 n+1 if m = 4 and n = 5, 6, 9 r Bnt"1 ifm = 5 r10r;+6l if m = 6 and n mod 7 f 1 and n f 7 r 1 if m = 6 and n mod 7 = 1 and n = 7 r Sn3+11 ifm = 7 r if m = 8 and n f 8 Pm,n = 16 if m = 8 and n = 8 if m = 9 and n mod 10 f 1, 7 + 1 if m = 9 and n mod 10 = 7 1 ifm = 9 and n-mod 10 = 1 f 7"i'1 if m = 10 and n mod 9 f 3 and n f 18 r7n3+21 + 1 if m = 10 and n mod 9 = 3 and n = 18 if m = 11 and n mod 11 f 3 f'8':i151 + 1 if m = 11 and n mod 11 = 3 ifm = 12 3n + 2 if m = 13 and n mod 3 f 1 3n + 1 if m = 13 and n mod 3 = 1 r ifm = 14. 12

PAGE 19

5.2 Proof of Theorem 4 Since the results of the program are being offered as a proof, the program requires the same scrutiny normally reserved for other constructions used to prove mathematical results. Because the program is quite short, the easiest way to do this is to present an annotated version of the program (see Table 2). Table 2. The Program for Theorem 4 program inddom(input, output); const mmax =50; maxstate =43890; nmax=300; type vector=array[-1 .. mmax] of integer; states=array[-1 .. maxstate,-1 .. nmax] of integer; var a,back:states; b,c,d,nextstate,fib:vector; diff,upper,n,stone,domnum,numstates,i,m,sum,binary j,k,count:integer; flag,flag2,pat:boolean; procedure encode(var a:states; var b,c:vector; var m,sum:integer); var j,k,temp:integer; begin sum:=O; j:=m; while j>O do begin temp:=1; if c[j]=1 then begin sum:=sum+b[j-2]; j:=j-1; end else if c[j]=2 then begin for k:=1 to j do temp:=temp*2; sum:=sum+temp; j :=j-2; end else j:=j-2; end; a[sum,-1] :=sum; end; procedure decode(var c,b:vector; m,sum:integer); var temp, j:integer; begin k:=m; while k>O do begin temp:=1; for j:=1 to k do temp:=temp*2; if temp<=sum then begin 13

PAGE 20

c[k] :=2; c[k-1] :=1; k:=k-2; sum:=sum-temp; end else if b[k-2]<=sum then begin c[k] :=1; sum:=sum-b[k-2]; k:=k-1; end else begin c[k) :=0; c[k-1] :=1; k:=k-2; end; end; end; The procedures encode and decode allow the states to be stored as integers. Encode changes each possible state of length m into an integer value and stores that integer until to program needs to use that state. As the program needs to work with a particular state, it decodes the integer. It was desirable to encode the state in such a way that the smallest number, that with no 2, and the least number of ones to be 0. For m = 3 that would be 010. The encoding procedure starts from position m, the far right, and moves left. The encoded number is determined by the following algorithm: 1. Initialization Let encode = 0 and k = m 2. The Encoding Step This step is repeated until k S 0. If the kth position is 2 then e;,code = encode + 2k and k = k 2. If the kth position is 1 then, encode = encode + Cm-2 and k = k 1. If the kth position is 0 then, encode = encode+O and k = k 2. 2 is subtracted from k for 0 and 2 because the k 1 position must be 1, but for the case when it is 1 then the k 1 position could be either 0, 1 or 2. For 14

PAGE 21

example, suppose the string is 1121012 and m = 7. 1. encode = 0 and k = 7 2. 2 is in the seventh position, so encode = 0 + 27 = 128, k = 7 2 = 5. 0 is in the fifth position, so encode = 128 + 0 = 128, k = 5 2 = 3. In the third position is a 2 so encode = 128 + 23 = 136, k = 3 2 = 1. 1 is in the first position, so encode = 136 + c1 = 136 + 3 = 139, k = 1 1 = 0. The encoded version of this string is 139. To decode the string: 1. Initialization Let k = m and a; = 0 for all i = 1, ... m. 2. The Decoding Step This is repeated until k :S 0. Is 2k :S encode? If yes, then ak = 2, ak_1 = 1 and k = k 2. If not then, is Cm :S encode? If yes, then ak = 1 and k = k 1. Otherwise ak = 0, ak-1 = 1 and k = k 2. begin Writeln ('Enter the length of the string'); readln (m); b(-1] :=1; b[O] :=1; for i:=1 tom do begin it i mod 2=0 then b[i] :=b[i-1]-1 else b(i] :=b[i-1]+1; end; numstates:=b[m]; n:=O; nextstate[0]:=1; tib[O] :=1; fib(1] :=1; for j:=2 to m+1 do fib[j] :=fib[j-1]+fib[j-2]; upper:=fib[m+1]-1; for i:=O to numstates-1 do a[i,-1]:=i; for i:=O to numstates-1 do for k:=O to nmax do a[i,k] :=9999; for i:=1 tom do c[i]:=1; 15

PAGE 22

encode(a,b,c,m,sum); a[sum,O] :=0; This section of the program receives input and initializes the arrays and veetors used. Vector b stores the possible number of states for m. The vector fib stores the number possible binary combinations which do not have two 1's, which are stones, next to each other i.e., for 2 x n the states are 00, 10, 01 ). Array a stores the minimum number of stones needed to independent dominate, so it is initialized to 99999. repeat n:=n+l; for i:=O to numstates-1 do begin for k:=O to m+1 do d[k]:=O; decode(c,b,m,i); for count:=O to upper do begin binary:=count; flag:=true; stone:=O; stone:=stone+a[i,n-1]; for j:=1 tom do begin If binary>=fib[m+1-j] then begin d[j] :=1; binary:=binary-fib[m+1-j]; end else d[j] :=0; end; The above program section first decodes the state and stores it in c. It then initializes a binary vector, d, to all O's. It will test the binary string as a possible state for n and then update the binary number by putting 1 in the first position. Each pass through the loop will create a new binary string to test. It repeats the loop until all possible binary strings have been tried. 16

PAGE 23

for k:=1 to m do begin if (c[k]=2) and (d[k]=1) then flag:=false; if (c[k]=O) and (d[k]=O) then flag:=false; if flag then begin if d [k] =1 then begin nextstate[k] :=2; stone:=stone+1; end; if d [k] =0 then if (c[k]=2) or (d[k+1]=1) or (d[k-1]=1) then nextstate[k] :=1 else nextstate[k] :=0; if (nextstate[k]=O) and (nextstate[k-1]=0) then flag:=false; end; {if flag} end; It is necessary to determine if there are two stones next to each other and to make sure that all undominated nodes in n 1 will be dominated by the state in n. If the binary string fails to dominate the nodes in n 1 then the program abandons the binary string. In order to check the independent condition the program checks to make sure that c; and d; do not have a 2 and a 1 respectively. If independence has not been violated, then the program determines the trinary state which has been produced in n. Any d; which has a 1 will produce a 2 in nextstate;. Otherwise, if there there is a 2 in the previous state or a 1 above or below the position the that program is looking at, the position is a 1, otherwise 0 is placed in the position. if flag then begin encode(a,b,nextstate,m,sum); if stone
PAGE 24

back[sum,n] :=i; end; end; end; {while loop} end; {outside for loop} If the number of stones is less than what is currently stored in a then update a with the smaller number of stones. The array back stores the state which leads to the number of stones placed in a. For example suppose the program started with 121 and then found a possible next state, 212, a stores the value 3 for the number of stones. If later, the program discovers that 010 is also a possible next state, the value in a is changed to 1 and in back the encoded value for 121 is stored. domnum:=9999; for i:=O to numstates-1 do begin flag2:=true; decode(c,b,m,i); for k:=1 to m do if c[k]=O then flag2:=false; if flag2 and (a[i,n]
PAGE 25

sum:=back[sum,n-i+1]; writeln end; Using back the program determines the patterns used to create the final state and thus the pattern which produced the lowest domination number. For example suppose that 3 x n is size of the grid and the program perceives 212 as the ending state. What state produced 212 can be determined by checking what is stored in back. Suppose that back had a 010, then the program looks to see where the 010 is from etc. i:=n-1; pat: =false; while (not pat) and (i>O) do begin diff:=a[O,n]-a[O,i]; j:=O; repeat if a[j,n]-a[j,i]=diff then pat:=true else if (a[j,i]=9999) and (a[j,n]=9999) then pat:=true else pat:=false; j:=j+1; until (not pat) or (j >numstates-1); i:=i-1; end; write('The domination number for an' ,m:O,'x' ,n:O,' is '); writeln(domnum:O); until pat; writeln('The' ,n:O,' and' ,i+1:0,' differ by diff:O) The final section of the program checks to see if the pattern has repeated for every possible state by the same amount; if so, it stops the program and records the recursion relation. 19

PAGE 26

Table 3 gives the results of this program. To save space, the independence domination numbers have been put into rows of 20. So for example, p8 1 = 3, p 8 2 = 5, ps,3 = 7, Ps,4 = 8, ... P8,2o = 39, P8.21 = 41, Ps,22 = 43 and PB,23 = 45. Following this is the first instance where Pm,n + q = Pm,n+po Table 3. The Output of the Program. 1 1 2 2 2 p(l,n+3) = p(l,n) + 1 for n 3 1 2 2 3 p(Z,n + 2) = p(Z,n) + 1 for n 2 1 2 3 4 4 6 6 p(.1,n + 4) = p(3,n) + 3 for n 3 2 3 4 4 6 7 7 8 p(4,n + 1) = p(4,n) + 1 for n 11 2 3 4 6 7 8 10 11 p(5,n + 5) = p(S,n) + 6 for n :2: 13 2 4 6 7 8 10 11 12 p(6, n + 7) = p(6, n) + 10 for n 2: 9 3 4 6 7 10 11 12 14 p(7,n + 3) = p(7,n) + 5 for n 2: 10 3 5 7 8 11 12 14 16 41 43 45 47 p(8,n+8)=p(8,n)+15forn2:_ 16 10 10 11 12 12 13 14 16 17 18 19 20 22 14 16 17 18 20 22 22 24 16 17 19 '21 22 18 20 22 24 26 28 30 :12 33 23 35 37 39 3 5 7 10 12 14 16 18 2'1 23 24 27 29 31 33 3S 38 39 42 44 45 48 50 52 54 56 59 60 63 65 p(9,n + 10) p(9,n) + 21 foe n 20 4 6 9 10 13 16 17 20 23 24 27 30 31 34 36 38 41 44 45 48 51 52 55 57 59 62 64 66 69 72 73 76 78 80 83 85 87 90 92 94 97 99 101 104 106 108 p(lO,n + 9) = p(lO,n) + 21 fro n 2: 37 4 6 9 11 14 17 19 22 24 27 30 32 35 38 40 43 45 48 50 53 W M M n ro 81 M m W% 106 109 111 114 116 119 122 124 127 129 132 p(ll,n + 11) = p(ll,n) + 28 for n 2:40 4 7 10 12 16 18 21 24 27 30 32 35 38 40 43 46 49 52 54 57 60 63 65 68 71 74 76 79 82 85 88 90 93 96 99 101 104 107 p(12,n + 13) R(12,n) + 36 for n 25 5 7 10 13 17 20 22 26 29 31 35 38 40 44 47 49 53 56 58 62 6S 67 71 74 76 80 83 85 89 92 94 98 101 103 107 110 112 116 119 121 125 128 130 134 137 139 143 146 148 152 155 157 161 164 166 170 173 175 179 182 184 188 191 193 197 200 202 206 209 211 215 218 220 p(13,n + 12) = p(13,n) + 36 for n 2:61 5 8 12 14 18 22 24 28 31 34 38 40 44 47 50 53 56 60 63 66 69 72 76 79 82 85 88 92 95 98 101 104 108 111 114 117 120 124 127 130 133 136 140 143 146 149 152 156 159 162 165 168 172 175 178 181 184 188 191 194 197 200 204 207 210 213 216 220 223 226 229 232 236 2:39 242 245 248 252 255 258 261 264 268 271 274 277 280 284 p(14,n + 5) = p(14,n) + 16 for n 2: 83 20

PAGE 27

5.3 A Conjecture Fisher[4] showed that the minimum domination number of a grid graph for n = 16, 17, 18,19 is l (m+2F"+2 ) j 4. This leads to the following theorem: Theorem 4. The independence domination number of an m x n grid graph 's -l(m+2)(n+2)J _4 Pm,n5 form= 16, 17, 18,19 and m :":: n. Proof. Since the set of independence dominations is a subset of the dominat t k th t < B Th 3 k < l(m+2)(n+2)J 4 1on se we now a /m,n Pm,n y eorem we now Pm,n 5 -, and Fisher showed that /m,n = l (m+2h(n+2) j 4 or m = 16, 17, 18, 19 so Pm,n = l (m+2h(n+2) j 4form=16, 17, 18, 19. 0 The fact that the bound is the minimum form = 14 and m = 16, 17, 18,19 leads us to believe for m = 15 and for m 2: 20 that the upper bound will be the minimum independence domination number. We state this belief in the following conjecture. This is similar to a conjecture given by Fisher[ 4]. Conjecture 1. For all m, n 2: 14, -l(m+2)(n+2)J _4 Pm,n-5 21

PAGE 28

6 References 1. Chang, T.Y., Domination Numbers of Grid Graphs, Ph.D. Thesis, Depart ment of Mathematics, University of South Florida, 1992. 2. Chang, T.Y., W.E. Clark & E.O. Hare, Domination Numbers of Complete Grid Graphs I, Ars Combinatoria (to appear). 3. Farber, M. Domination, Independent Domination and Duality in strongly Chordal Graphs, Discrete Appl. Math. 7 (1984) 115-1130. 4. Fisher, D.C. The Domination Number of Complete Grid Graphs, submitted to Journal of Graph Theory. 5. Hare E.O., S.T. Hedetniemi and W.R. Hare, Algorithms for Computing the Domination Number of K x N Complete Grid Graphs, Congressus Numeratium 55 (1986) 81-92. 22