Citation
The fractional domination number of complete grid graphs

Material Information

Title:
The fractional domination number of complete grid graphs
Creator:
Bisbee, Linda A
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
ix, 84 leaves : illustrations ; 29 cm

Subjects

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

Notes

Bibliography:
Includes bibliographical references (leaf 84).
Thesis:
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 Linda A. Bisbee.

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:
34880929 ( OCLC )
ocm34880929
Classification:
LD1190.L622 1995m .B57 ( lcc )

Downloads

This item has the following downloads:


Full Text
THE FRACTIONAL DOMINATION
NUMBER OF
COMPLETE GRID GRAPHS
by
Linda A. Bisbee
B.S., Birmingham-Southern College, 1975
M.S. (Biology), Purdue University, 1977
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1995


This thesis for the Master of Science
degree by
Linda A. Bisbee
has been approved
by
Date
n


Bisbee, Linda A. (M.S., Applied Mathematics)
The Fractional Domination Number of Complete Grid Graphs
Thesis directed by Associate Professor David C. Fisher
ABSTRACT
The M X N complete grid graph (notated PM x PN) is a graph with
MN nodes arranged in a square grid so that each node is connected to the
nodes immediately above, below, left and right of it. Each node is
assigned a non-negative weight such that the sum of the weight on each
node and its immediate neighbors is less than or equal to 1. This is the
fractional 2-packing. The sum of the weights of the nodes is then
maximized. The dual of the linear program problem is the fractional
domination, in which the sum of the weight on each node and its
immediate neighbors is greater than or equal to 1. The maximum sum of
the weight in a fractional 2-packing is equal to the minimum sum of
weights in a fractional domination. The common value is the fractional
domination number.
Hare [4,5] has found minimal fractional dominations for the nodes
of Pj x PN and P2 x PN graphs for all N. Additionally, minimal fractional
iii


dominations of PM x PN have been found for some other values of M and
N.
This thesis finds minimal fractional domination of P3 x PN for most
N (asymptotically about 77%) and P4 x PN for most N (asymptotically
about 80%). Some results are given for the minimum fractional
domination of larger grids.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
IV


CONTENTS
Figures............................................... vii
CHAPTER
0 Introduction .........................................1
Theorem 1 .............................................2
Theorem 2..............................................5
Theorem 3..............................................7
1 P, x PN ..............................................9
Theorem 4.............................................9
2 P2xPN ...............................................11
Theorem 5.............................................11
Theorem 6............................................ 11
3 P3 x PN ............................................ 14
Theorem 7............................................ 15
Theorem 8............................................ 36
Theorem 9............................................ 40
Theorem 10 .......................................... 41
4 P4 x PN..............................................45
Theorem 11 ......................................... 46
Theorem 12 ......................................... 59
Theorem 13 ......................................... 60
5 P5 x PN............................................. 62
Theorem 14 ......................................... 63
Theorem 15 ......................................... 71
v


6 P6 x PN .
Theorem 16
00 Y^Pm x Pn)
REFERENCES .
vi
72
73
83
84


FIGURES
Figure
1 ...............................................:................1
2 ................................................................5
3 P3xPj...........................................................6
4 ...............................................................10
5 .............................................................. 13
6 Symmetric weights for P3 x P7................................. 14
7 P3 x P4....................................................... 16
8 P3 x P5....................................................... 17
9 P3 x P6....................................................... 18
10 P3xP,........................................................ 19
11 P3 x P8...................................................... 20
12 P3 x P9...................................................... 21
13 P3 x P10..................................................... 22
14 P3 x Pn...................................................... 24
15 P3 x P12..................................................... 25
16 P3 x P13..................................................... 26
17 P3 x P14..................................................... 27
Vll


28
18 P3 x P15.........................
19 P3 x P7 with designation of c, d elements ............ 39
20 Symmetry of P4 x P7....................................45
21 P4xP4................................................. 47
22 P4xP4................................................ 48
23 P4xP5................................................. 49
24 P4xP6................................................. 50
25 P4xP7................................................. 51
26 P4 x P8............................................... 52
27 P4xP9................................................. 53
28 P4 x P10.............................................. 54
29 Symmetry of P5 x P7................................... 62
30 P5 x P5............................................... 64
31 P5 x P7............................................... 65
32 P5 x P8................................................66
33 P5xP,................................................. 67
34 P5xP10............................................... 69
35 P5xP..................................................70
36 ...................................................... 72
37(a) Fractional 2-packing of P6 x P6 .................. 74
viii


37(b) Fractional domination of P6 x P6 ........................... 75
38(a) Fractional domination of P7 x P7...............................76
38(b) Fractional 2-packing of P7 x P7 ............................ 77
39 PgxP8........................................................... 78
40 P9 x P9..........................................................80
41 P,, x Pu ........................................................82
IX


Chapter 0
Introduction
Let G be a graph such that the nodes of G are arranged in a
"checkerboard" pattern, where M is the number of nodes in each
horizontal row and N is the number of nodes in each vertical column.
Each node in G is connected to the node immediately above, below, left
and right of that node. The notation PM x PN is used to designate such a
graph. Further, let G be a graph such that the nodes of G have non-
negative weights such that the sum of a node and its neighbors is greater
than or equal to 1.
wi-i.j
W- i uj-1 w WM wi,j+l
Wiflj
Figure 1
Example of an interior node (wg) and its 4 neighbors
If W;., | + w,+ W|j + wij+1 + wi+1j > 1 for all i,j, then
G is a fractional dominated graph.
Conversely, if the nodes of G have non-negative weights such that
the sum of a node and its neighbors is less than or equal to 1,
page 1


wi-i,j + Wi.j-1 + wi,j + Wi,j+1 + wi+1J < 1 for all i, j
G is then a fractional 2-packing graph.
If the weights of the nodes of a fractional domination graph are
solved as a linear programming problem, the weights of the nodes of the
fractional 2-packing graph are its dual. We can express the fractional
domination linear program as: for n-vectors x and y, let x > y (or
conversely, x < y) mean that xt > yi (or Jt, < y,) for all i. Let 1 and 0
be vectors whose components are all one or all zero, respectively. We
will further define N(G) as the neighborhood matrix of G. yf, also called
the fractional domination number, is the minimum sum of the weights of
all vertices of G, so it is the solution to the linear programming problem,
y^-(G) = min lr x subject to x>0 and N{G)x>. 1
X
As the dual linear program, the fractional 2-packing can give
another formulation of the fractional domination number, Yf(G),
yf{G) = max 1T x subject to x>0 and N(G)x< 1
X
Theorem 1: There is a minimal fractional domination of PM x PN which
has 4-fold symmetry, i.e., wu = wM.i+u = wiN.i+1 = wM.1 + liN.j+1.
page 2


Proof: Let be a minimal fractional domination of PM x PN. For
simplicity, define = 0 for i < 0, i > M, j < 0 or j > N. Then for
all i,j with 1 < i < M and 1 < j < N, we have
Wij + Wjj.j + wMj + wij+I + wi+1J > 1 and
M N
=i j=i
Let w |j = (Wy + wM-i+ij + wLN.j+1 + wM_i+1N.j+1).
Then
W i.j-l = ~ (Wi,j-1 + WM-i+l,j-l + Wi,N-j+2 + WM-i+ KN-j + 2)
W + 1 = "4 ^W'j+1 WM-i+l,j + l + Wi,N-j + WM-i + l,N-j)>
^ (Wi.,j + wM_ij + Wj.i.N.j+i + wM.i+2jN.j+l)and
Wi+ij = ^ (Wi+1j + wM_!j + wl+1N.j+1 + WM.j N.j + i).
If we then add w^ + w^., + wij+1 + w;., j + wi+1 j and rearrange the
terms, we get
(the neighborhood of w; j)
page 3


+ (the neighborhood of wM i+1 j)
4
+ (the neighborhood of wi N.j+1)
+ (the neighborhood of wM.i+1 N:+1) > (4) > 1
4 4
(b) If we consider the sum of w^ for all i and j and rearrange the terms
as we did above, then
M N
EE \(.wij+wu-i.ij
i=i j=i 4
1 j + 1 + WM-i+W-j+0
M N
= 4EE H-
i-i y-i
= 7i(Pm x Pn)
(C) wij = wiiN.j+1
By symmetry in the definition of w.j and wi N_j+1, the two nodes
are equal.
(d) wij = wM_i+lj
page 4


By symmetry in the definition of w\j and wM_i-Hj> the two nodes
are equal.
Q.E.D.
Theorem 2: There is a maximum fractional 2-packing of PM x PN which
has 4-fold symmetry, i.e., w^ = wM_i+u = wiiN.j+1 = wM.I + liN.j+1.
Proof: Similarly, if we let vsj be a maximum fractional 2-packing of PM x
PN, and define v in the same way as w and w were defined, there is a
maximal fractional 2-packing of PM x PN which has 4-fold symmetry, i.e.,
Vij = VM-i + l.j = Vi,N-j +1 = VM-i+ l,N-j+ 1
Q.E.D.
The weights on each individual node may not be the same for the
fractional 2-packing and the fractional domination. We use squares to
represent the nodes because of the typesetting.
al a2 a3
a4 a5 a6
a7 a8 a9
Figure 2
page 5


0 1 2 0
1 1 1
2 2 2
0 1 0
2
Fractional domination
P3XP3
3 1 3
8 4 8
1 0 1
4 4
3 1 3
8 4 8
Fractional 2-packing
P3 x P3
5 5
Tr= - *2
Figure 3
(Hare, [4])
Hare [4,5] has found y^ X PN) and y,{P2 X PN) for all values of
N. Additionally, Hare [4,5] has found yr (P3 X PN) for N = 3, 4, 5, 6,
7, 8, 10, 11, 14; 7f (P4 X PN) for N = 4, 5, 8 and yf (P5 X PN) for N =
6, 9.
This thesis will find y^Pj X PN) and y( family of values for N and give some specific examples of y^Ps X PN) and
y, for all values of N will be proven.
page 6


Important considerations of the value of Yf(PM x PN) are the upper
and lower limit of fractional domination for all M, N in those cases where
the actual value of 7f(PM x PN) is not known. Hare [5] has published
general limits based upon Fibonacci numbers. Fibonacci numbers are the
sequence {0, 1, I, 2, 3, 5, 8, 13...}, where F0 = 0, F, = 1, and
Fk = Fk-1 + Fk-2-
Theorem 3: (Hare [5])
When N, M > 2,
NC + cp < Tf (Pm X PN) < NC + Cj
where C=
u i=lM
D = 3 Fm + Fm_[ and
cp and Cj are positive values depending only on M.
4
Also, cp > Fm_, when M > 6
For 2 < M < 6, bounds are:
- N + - < Yr (P3 X PN) < - N + -
7 7 7 7
page 7


10
11
N +
_4_
11
< Tf (P4 X PN) <
10
11
N +
12
11
20
18
N +
S_
18
Tr (P5 X PN) <
20
18
N +
20
18
page 8


Chapter 1
Pi x PN
Hare [4] found the fractional domination number of P[ x PN. For
completeness, we repeat these results.
Theorem 4: For all N > 1, we have 7^ x PN) = fN/3~l .
Proof: For N s 0 (mod 3), nodes 2, 5, 3i+2,...N-l are given
values of 1. All other nodes are given values of 0.
For N = 1 (mod 3) or N = 2 (mod 3), nodes 1, 4, 7, 3i + l, ... are
given values of 1. All other nodes are given values of 0 (see Figure 2).
For all N, this is both a fractional domination and a fractional 2-packing.
Since the number of nodes which are given the value of 1 is
we
have 7r(P, x PN) equals
Q.E.D.
The weights for all values of N are both a fractional 2-packing and
a fractional domination of P, x PN. Such a weight where the weights are
both a fractional two-packing and a fractional domination is called perfect
fractional dominations and a graph with perfect fractional domination is
called a perfect fractional domination graph. Figure 4 gives examples of
P[ x PN for N = 6, 7 and 8.
page 9


Chapter 1
Pi x PN
Hare [4] found the fractional domination number of Pt x PN. For
completeness, we repeat these results.
Theorem 4: For all N > 1, we have y^ x Pn) = fN/3~l .
Proof: For N = 0 (mod 3), nodes 2, 5, 3i+2,...N-l are given
values of 1. All other nodes are given values of 0.
For N s l (mod 3) or N =2 (mod 3), nodes 1, 4, 7, 3i+l, ... are
given values of 1. All other nodes are given values of 0 (see Figure 4).
For all N, this is both a fractional domination and a fractional 2-packing.
Since the number of nodes which are given the value of 1 is lyl we
have YifP, x PN) equals lyl .
Q.E.D.
The weights for all values of N are both a fractional 2-packing and
a fractional domination of P, x PN. Such a weight where the weights are
both a fractional two-packing and a fractional domination is called perfect
fractional dominations and a graph with perfect fractional domination is
called a perfect fractional domination graph. Figure 4 gives examples of
P! x PN for N = 6, 7 and 8.
page 9


For space considerations, these graphs are represented as their transposes.
For example, P! x P6 is actually shown as P6 x P; or (P! x P6)T.
0 1 0 0 1 0
Pf(P, x P6) = 7f(Pi x P6) = 3
1 0 0 1 0 0 1
P^P, x P7) = 7f(Pj x Pv) = 3
1 0 0 1 0 0 1 0
Pf(P, x Pg) = 7f(Pi x P8) = 3
Figure 4
page 10


Chapter 2
P2 x PN
Hare [4] also found the fractional domination number of P2 x PN.
There are two separate formulas depending upon whether N is even or
odd. Interestingly, P2 x PN is also a perfect fractional domination graph.
Theorem 5: For N odd, yf (P2 x PN) = (N + l)/2.
Proof: Consider the following weights:
Let v,: = v-,: = if i is odd.
2
Let v, | = v2ii = 0 if i is even.
If i is odd, then left and right neighbors are 0 and its upper (or
lower) neighbor is 1/2. The sum of its neighborhood is exactly 1. If v =
0, its left and right neighbor is 1/2 and its upper (lower) neighbor is 0.
The sum of its neighborhood is exactly 1. So this is a perfect fractional
domination. The graph contains a total of (N + 1) nodes of value 1/2 and
(N 1) nodes of value 0. The sum of all of the nodes of the graph is
therefore (N + l)/2.
Q.E.D.
Theorem 6: For N even,
Y/(P2 x Pn)
N(N + 2)
2(N +1)
page 11


Proof: Let N = 2i, and
if i is even
2(N + 1)
N + l-i if i is odd
l 2(N + 1)
If i is even, the neighbor to the left has an odd index and equal to
2 (N +1)
+ -^ and V| and its neighbor b<
2 (N +1)
indices and have equal values of -----
2(N + 1)
neighborhood of v, is equal to
i + i + (N-+ 1) (i 1) + (N + 1) 0 + 1)
If i is odd, the neighbor to the left has an even index and is equal
and Vj and its neighbor below (or above) have equal indices
A! + 1 (i 1)
the neighbor to the right has an odd index and equal to
2(N + 1)
to --------- the neighbor to the right has an even index and is equal to
2(N +1) &
i + 1
2 (N + 1)
2 (N + 1)
is equal to
i 1 + i + I + 2{N + 1) 2i
2(JV + 1)
= 1. So these weights are a
perfect fractional domination.
page 12


The sum of v,, is thus
(-)(- + 1)
2 2 N(N + 2)
(N + 1) 4 (N + 1)
Since E vx;
E v2 j, we then have
_ N(N + 2)
Y/ 2(N + 1)
Q.E.D.
For space considerations, these graphs are represented as their transposes.
For example, P2 X P6 is actually shown as P6 x P2 or (P2 x P6)T.
3 1 2 2 1 3
7 7 7 7 7 7
3 1 2 2 1 3
7 7 7 7 7 7
7f(P2 x P6)
1 0 1 0 J. 0 1
2 2 2 2
1 0 1 0 1 0 1
2 2 2 2
7c(P2 x P7) 4
Figure 5
page 13


Chapter 3
p3xpn
Only a few specific solutions has been published to date for P3 X
PN fractional domination or 2-packing. Hare [4,5] has published solutions
for fractional domination forN = 3, 4, 5, 6, 7, 10, 11, and 14, which
were solved by linear programming methods. Using similar linear
programming methods, it appears that there are at least four classes of
fractional domination patterns for different values of N. This chapter will
find yf(P3 x PN) for an infinite number of values of N > 3.
Figure 6 is an example of this designation of elements for P3 X P7.
For P3 X PN, let wu = w, 3 = &, and w2 i = bj. Then = aN+1_i5 and b;
= bN+1_i. For simplicity, let a0 = aN+1 = b0 = bN+1 = 0.
a, bi ai
a2 b2 a2
a3 b3 a3
a4 b4 a4
a3 b3 a3
a2 b2 a2
ai b, ai
Figure 6
Symmetrical weights for P3 X P7
page 14


Theorem 7: For N < 15, we have 7f(P3 x PN)-given below.
N 1 2 3 4 5
7.0*3 X PN) 1 2 - 1 ,1 4
2- 3-
2 3
N 6 7 8 9 10
7r(P3 X PN) . 2 ,2 2 _ 5
4- 5- 6 6- 7-
3 5 15 7 9
N 11 12 13 14 15
7.0*3 X PN) 8- 4 8 53 9 17 10- 9 u 17
Proof: For N = 1, see Chapter 1. For N = 2, see Chapter 2. For N =
3, see the Introduction. For N > 4, verifying a value of 7,{P3 X PN) can
be done by giving a fractional domination and a fractional 2-packing
whose weights sum to yf(P3 X PN).
page 15


1 1 1
3 3 3
1 0 1
3 3
1 0 1
3 3
1 1 1
3 3 3
Fractional domination and Fractional 2-packing
P3 X P4
Figure 7
Proof that 7^3 X P4) = 3 1/3.
page 16


1 1 1
4 2 5
1 0 1
4 4
1 0 1
2 2
1 0 1
4 . 4
1 1 1
4 2 4
Fractional domination and Fractional 2-packing
p3xp5
Figure 8
Proof that 7, page 17


1 3 1 3 1 3
1 0 1 3
i 0 I
3 3
1 0 1
3 3
1 0 1
3 3
1 1 1
3 3 3
Fractional 2-packing
P3XP6
0 2 3 0
1 1 i
3 3 3
1 0 1
3 3
1 0 1
3 3
1 1 1
3 3 3
0 2 0
3
Fractional domination
P3XP6
Figure 9
Proof that yf(P3 X P6) = 4 2/3.
page 18


1 10 1 2 1 10
T
dv-

5 1U 5
1 5 0 I 5
2 1 2

5 5 5
1 5 0 1 5
2 3 2

5 10 5
1 1 1

10 2 10
Fractional domination
P3XPV
2 5 1 5 2 5
1 4 0 1 4
7 3 7

20 10 20
1 1 1
i
10 5 10
7 3 7
'
20 10 20
1 4 0 1 4
2 l 2

5 5 5
Fractional 2-packing
P3XP7
Figure 10
Proof that Tf(P3 X P7) = 5 2/5.
page 19


0 3 5 0
2 2 2

5 5 5
1 1 1

5 15 5
1 2 1

3 15 3
1 2 1
-
3 15 3
1 1 1

5 15 5
2 2 2

5 5 5
0 3 5 0
Fractional domination
P3 x P8
11 4 11
30 15 30
3 0 3
10 10
1 2 1
3 15 3
7 1 7
30 5 30
7 1 7
30 5 30
1 2 1
3 15 3
3 0 3
10 10
11 4 11
30 15 30
Fractional two-packing
P3 x P8
Figure 11
Proof that 7f(P3 x P8) = 6 2/15.
page 20


0 4 7 0
3 3 3

7 7 7
1 1 1

7 14 7
5 3 5
.
14 14 14
2 0 2

7 7
5 3 5
- -
14 14 14
1 1 1

7 14 7
3 3 3

7 7 7
0 4 7 0
2 7 3 7 2 7
2 7 0 2 7
3 7 0 3 7
2 1 2

7 7 7
1 2 1

7 7 7
2 1 2

7 7 7
3 7 0 3 7
2 7 0 2 7
2 3 2

7 7 7
Fractional domination Fractional 2-packing
P3 x P9
P3 x P9
Figure 12
Proof that 7f(P3 x P9) = 6 6/7.
page 21


1 3 1 3 1 3
1 3 0 1 3
1 3 0 1 3
1 1 1

3 9 3
2 2 2

9 9 9
2 2 2

9 9 9
1 1 1

3 9 3
1 3 0 1 3
1 3 0 1 3
1 1 1

3 3 3
Fractional 2-packing
P3 x P10
1 9 5 9 1 9
1 2 1

3 9 3
1 3 0 1 3
1 1 1

3 9 3
2 2 2

9 9 9
2 2 2

9 9 9
1 1 1

3 9 3
1 3 0 1 3
1 2 1

3 9 3
1 5 1

9 9 9
Fractional domination
P3 x P10
Figure 13
Proof that 7^3 x P10) = 7 5/9.
page 22


Theorems 1 and 2 show there is a maximum fractional 2-packing and a
minimum fractional domination of PM x PN that are symmetric about the
N
middle row(s). To save space, we will only show the first (if N is
iV+1
even) or (if N is odd) rows of such symmetric weightings for
graphs P3 x Pn (Figure 14), P3 x P12 (Figure 15), P3 x P13 (Figure 16), P3
x P14 (Figure 17) and P3 x P15 (Figure 18).
page 23


1 4 1 4 1 4
1 1 1

4 8 4
3 1 3

8 8 8
1 0 1

4 4
3 3 3

8 8 8
0 5 8 0
Fractional domination
P3 x Pu
Proof that 7^3 x Pu) = 8 1/4.
15 3 15
56 14 56
29 1 29
112 8 112
39 1 39
112 7 112
1 1 1
4 28 4
41 0 41
112 112
43 13 43
112 56 112
Fractional 2-packing
P3 x Pn
Figure 14
page 24


0 32 53 0
21 21 21
53 53 53
11 2 11
53 53 53
19 8 19
53 53 53
15 5 15
53 53 53
14 10 14
53 53 53
41 12 41
106 53 106
16 0 16
53 53
33 9 33
106 53 106
23 11 23
106 53 106
14 10 14
53 53 53
35 4 35
106 53 106
Fractional domination
P 3 X P12
Figure 15
Proof that y,{P3 x P12) = 8 52/53.
Fractional 2-packing
P3 x P12
page 25


0 10 17 0
7 7 7
17 17 17
3 1 3
17 17 17
6 3 6
17 17 17
5 1 5
17 17 17
5 3 5
17 17 17
4 3 4
17 17 17
Fractional domination
P3 x P13
_6_ 17 5 17 6_ 17
_5_ 17 0 5 17
6 2 6

17 17 17
4 3 4
.
17 17 17
4 4 4
- -
17 17 17
5 2 5

17 17 17
6 1 6
....
17 17 17
Fractional 2-packing
P3 x P13
Figure 16
Proof that 7f(P3 x P13) = 9 12/17.
page 26


0 13 18 0
5 5 5
.
18 18 18
4 9 0 4 9
5 1 5

18 9 18
1 1 1

6 3 6
2 2 2

9 9 9
7 18 0 7 18
Fractional domination
P3 x P14
5 4 5
18 9 18
5 0 5
18 18
4 0 4
9 9
5 1 5
18 9 18
1 1 1
6 3 6
2 2 2
9 9 9
7 0 _7_
18 18
Fractional 2-packing
P3 X P14
Figure 17
Proof that y,{P3 x P14) = 10 4/9
page 27


0 11 17 0
6 6 6

17 17 17
5 17 0 5 17
6 2 6
-
17 17 17
4 3 4

17 17 17
4 4 4

17 17 17
5 2 5
-
17 17 17
6 1 6

17 17 17
6 17 17 6 17
17 0 6 17
_5_ 17 0 _5_ 17
6 2 6
-
17 17 17
4 3 4

17 17 17
4 4 4
'
17 17 17
5 2 5
i
17 17 17
6 1 6
- 11
17 17 17
Fractional domination
Fractional 2-packing
P3 X P15
Figure 18
^3 X ^15
page 28


Proof that x P15) = 11 2/17.
For N > 15, we can solve each value of N using linear
programming methods as we did for 3 < N < 16. However, the purpose
is to find a general algorithm which will generate all values of 7^3 x PN).
In developing a general algorithm for P3 x PN, we were struck by the
existence of at least three separate "classes" of N. Each class had a
slightly different pattern of a^s and bjs and are designated as Type A,
Type B and Type C.
Let
r_ -(l+^+A/S-1
2
0 =cos_1(^-)
2
=(
N-1
2
)0
O) =(
N-3
2
)0
page 29


*=(
N-5
2
)6
We have found values, designated as p and q, which are associated with
the specific types of P3 x PN and can be used to calculate a-t and bi5 for all
i. These types of P3 x PN are designed as Type A, Type B and Type C.
A Type A P3 x PN is characterized by a domination graph where the
weight of a! = 0, the weight of bj = 1 a2 and cannot be calculated by
another formula, and b, + b2 + b3 + 2a2 > 1. If the sum of a node and
its neighbors is greater than 1, that node is said to be overdominated.
Definition 1: A Type A weighting of P3 x PN has p and q where
(v/2 + l)cos(w)A (^)cos(<|>)
7 7
P = ------------------------------------------------
(r + rw)(-v^-l)cos(o>) (y/2 l)(r2 + rN ^cos^)
(i)(r + /-w)+(v/2-l)(r2 + rwl)(|)
(r + rN){-\jl- I)cos(w) (i/2- l)(r2 +rAM)cos( and
page 30


a, = -^ + p(r + rN+1") + q cos[( )9]> v i
bj = f 1 a2 = 1 aN.l5 i = 1, N
{ p(r' + rN+1_i) V i> 1, i l
Lemma l:r+l + = \/2 (trivial)
r
Lemma 2: For all k and 0, we have
cos[(k-l)0] + cos[(k+l)0] = (v/2 1) cos (k0) (trivial)
Using these variables we have just defined, we now need to verify
that the sum of the weights on the nodes in the neighborhood of a; equals
1 and the sum of the weights on the nodes in the neighborhood of bj also
equals 1. We will first examine the sum of weights of a^ + a; + ai+1 +
bj, the neighborhood of a and then consider the neighborhood of bj, or 2a,
+ b,_j + bj + bi+1.
Lemma 3: A Type A weighting has aj = 0.
Proof: aj = + p(r + rN) + q cos[( ~~~ )0])
page 31


By applying the definitions of p and q and distributing the results, we get
= | [(r + rN)(- v/2 +1) cos(oj)
- ( v/2 -l)(r2 + rN_1)cos(0)]
+ (r1 + rN)[( Jl +1)cos(cj) - cos(0)]
7 7
+ cos,)[ (r + rN) + ( \jl -lXr2 + O \ ]
7 7
= 0
Q.E.D.
Lemma 4: For all i except i = 1 and i = N, we have
a;., + aj + aj+1 + b| = 1. (the neighborhood of ai)
Proof: a;., + a, + ai+1 + bj
= + p(ri_1 + rN+1'1)) + q cos[( (i-1) )9]
7 2
+ ^ + p(r + rN+1'') + q cos[( )]
page 32


+ + p(r1+1 + rN+1'(1+1)) + q cos[( (i+l)-~^ )9]
+ + \J2 p(r + rN+1) sjl q cos[( i-^^- )0]
7 2
= 1 + p(ri_1 + f + ri+1 + rN+2_i + rN+1-'' + rN+i)
+ v/2 p(r + rN+1-)
+ q {cos[( (i-1)--^ )0] + cos[( i)0] +
cos[( 0+D )0]}
- & cos[( i-^ )0]}
= 1 + p(r + (1+ sj2 ) + r)(r +rNi+1)
+ q{cos((k-l)0) + cos((k+l)0) + ( where k = i (+) .
2
Then by Lemmas 1 and 2, we have the result.
Lemma 5: For i = 1 and i = N, we have + a2 + bj = 1.
Proof: Since and bNdo not follow the general formula of b
treat i = 1 and i = N as special cases. By Theorem 1, since aj
bj = bN.|, we need only prove one case. For ease, we will take
at + a2 + b(
= 0 + a2 + (1 a2)
Q.E.D.
we must
= aN_; and
i = 1.
page 33


= 1.
Q.E.D.
Lemma 6: For all i > 2 and i < N 1, we have
2aj + bui + b; + bi+1 = 1. (the neighborhood of b;)
Proof: 2a; + b^ + bj + bi+1
= 2( + p(r + r'1'1'1) + q cos[( )]) +
+ y/2 p^'1 + rN+1-(U1)) - y/2 qcos[( (i-1)- )0]
+ ^ + y/2 p(r + rN+1'i)
- y/2 qcos[( )0]
+ ^ + v/2 p(ri+1 + rN+1'(i+1)
- y/2 q cos[( (i+1)-^ )0]
= 1 + y/2 ( y/2 -1) p(r + rN+1") y/2 ( y/2 -ljp^ + rN+u)
+ y/2 ( y/2 -1) q cos[( (i-1)-^ )0]
- y/2 ( y/2 -1) q cos[( (i-1)-^ )0]
= 1 + p(r_1 + 1 + r)(r' + rNi+1)
+ q{cos((k+l)0) + cos((k-l)0) -( y/2 1 )(cos(k0))}
page 34


, . ,JV+L
where k = 1 (------) .
2
Then by Lemmas 1 and 2 we have the result.
Q.E.D.
Lemma 8: In a Type A weighting, a2 = b2 and aN.j = bN_j.
Proof: By Theorem 1, a2 = aN_! and b2 = bN_!. For ease, we will only
prove a2 = b2.
a2 = -^ + pCr2 + r'4'1) + q cos(co)
= ^ + \]2 pCr2 + r^1) \fl q cos(w)
+ + (1- \f2 )p(r2 + rN_1) + (1+ sj2 ) q cos(u>)
= b2 + | + (1- ft )p(r2 + r141) + (1+ v/2 ) q cos(co)
Applying the definition of p and q and distributing the results, we get
= b2 + ^ {(- \J2 -l)(r+rN)cos(w) + ( \J2 +l)(r+rN)cos(w)
+ 2(r2+rN'1)cos(co) 2(r2+rN'1)cos(o;)
+ ( \J2 -lX^+r^cosO^) ( \j2 -lX^+r^cos^)
= b2
Q.E.D.
Lemma 9: 2^ H- b2 + b2 = 1 and 2aN + bN + bN_! = 1.
page 35


Proof: Since b] and bN do not follow the general formula of bh we must
treat i = 1 and i = N as special cases. By Theorem 1, since a, = aN.j and
bi = bN_i, we need only prove one case. For ease, we will take i = 1.
2a] + b| + b2
= 2 (0) + bj + b2
= (1 a2) + b2
Since'a2 = b2,
= 1.
Q.E.D.
We have shown that the sums of the weights of the nodes in the
neighborhood of a, and bj are equal to 1 in the Type A P3 x PN fractional
domination graph. In order to show that the variables and values defined
describe a fractional domination or fractional 2-packing, all values of a;
and bj must be greater or equal to 0 and less than or equal to 1. In
addition, for the general case of P3 x PN, we need a formula for the sum
of all nodes (i.e., 7f(P3 x PN)) so that the calculation of the weight of each
node is not necessary.
Theorem 8: Let {a;}, {fy} be a Type A weighting of a P3 x PN. If a] >
0 and b; > 0 Vi, then the following is true:
a) The neighborhood of b2 > 1
page 36


b) tKPjxPn)= | N + | + |a2 +
or
N
E
(2a, + b)
5 N 2
--- +
7 7
2b2
~T
Proof:
a) bj + b2 = 1
The neighborhood of b2 = + b2 + 2a2 + b3
Since a2 > 0 and b3 > 0,
the sum of the neighborhood of b2 > 1
b) Tr = I (2a, + b;)
.N-l 2 +ai*i+b)+ifL^ai+ I 2 bi-i+hi + Kv>
II -4 1 + 10 a, + 7 14 a3 + 7 , 14 .. + aN.2
^ 10 + aN-l + Ij aN + ~1 bl + - b2 + b3 + 7 7
+ ^ bN-2 + bN.[ + 1 h bN
=>£(2ai + bj) = \ E N(a,) + | E N(b,) + 10 T a' + a2 7
+ ^ aN-l + 10 y aN + | b1 + 7b>
+ ^ bN-l + 6 k
Since £N(b2) > 1 and a! = 0, then
page 37
cn | r


Yr = - (N-2) + (N-4) + a2 + 2b: + b3
7 7 7 7
Since 1 = a2 + bls then
7r =
5A + 2
7
- a2 +
7
3
Q.E.D.
We now need to consider the Type A fractional 2-packing graph.
For clarity, we will use the notation Cj and di5 where i = 1, 2... N as the
nodes of the 2-packing graph. We have found values s and t which can be
used to calculated Cj and di for all i. A Type A 2-packing graph is
characterized by weight of d2 = 0 and c, + dt + c2 < 0. When the sum
of the weights of a node and its neighbors is less than 1 in a 2 fractional
2-packing graph, the node is said to be underpacked.
Definition 2: Define the following values:
i(^)cos(o))-i(y2)cos[^^e]
l(-v^)(rw+1+l)-^(-V2)(r2+rw-1)
(-2)cos(a,)(.- + l)+2cos[^6](^+,-)
Cj = ^ + s(r' +p992Xr?F+1t')x>s[(i- )0]
d, = - + s(F + rN+u) ft t cos[(i- )0]
7 2
page 38


P3 x P7 with designation of c, d elements
Figure 19
Let values of 6, , w, and r be defined as previously.
Lemma 10: If c, and d; have the same values as above, then the sum of
the neighborhood of Cj = 1.
Proof: Since the sum of the neighborhood of Cj is not dependent upon the
values of s and t but on the definition of C; and di; this proof is the same
as Lemma 4.
Q.E.D.
Lemma 11: If Cj and ds have the same values as above, then the sum of
the neighborhood of d; = 1.
page 39


Proof: Since the sum of the neighborhood of dj is not dependent upon the
values of s and t but upon the definition of Cj and di5 this proof is the same
as Lemma 6.
Q.E.D.
Lemma 12: d2 = 0.
Proof: d2 = -^ + \J2 s(r2 + rN+I"2) \Jl t cos(co)
By applying the definitions of s and t and distributing the results, we get
(2 cos[ ^-^0 ](r2+ rN+1'2) 2(r + rN+1)cos(co)
7 2
+ 2(1^ + rN+1'2)cos(a)) 2(r2 + rN+l2)cos(w)
- 2(r2 + rN+1'2)cos(co) + 2(r + rN+1)cos(o;)
= 0
Q.E.D.
Theorem 9: Suppose G is a P3 X PN fractionally 2-packed graph. Then
if C; > 0 and d; > 0 V i and d2 = 0, the following is true:
a) The sum of the neighborhood of C[ <1.
b) I(2Ci +d,) = ^ + | c2 + | d,
Proof:
a) (Proof by contradiction):
page 40


Suppose that £N(a,) = c, + c2 + d, = 1.
2c, + d, = 1 => c, = c2
c, + c, + c3 = 1 => c3 = d,
c, + c, + c3 + d3 = 1 => d3 = 0
But d3 > 0 = c, + c2 + d, < 1
b) £20, + ^ =
, AM
N-1
^E e m
' i=2 ' i=2
5 ,XT _ , 20 , 8 , 12 . , 2 .
- (N-2) + c, + c2 + d, + d2
7 7 7 7 7
d2 = 0; 2c, + d, = 0;
fc2 +
12
7
d,
Theorem 10: Given the previous definitions, then
E =E CV4)
i=l i=l
Proof: The sum of all of the weights of a Type A graph is
A 5N 2 2ai 2b3
> = + + +
^ 7 7 7 7
since b, = 1 a2,
5N t 2bi [ 4bi t 2fe3
7 + 7 + 7 + 7
Substituting for values of b,, b2 and b3, we get
CM 7 49 7 7
e.£.D.
page 41


+ ^P(r3+rN-2)-^q cos(A.)
2 -2
Substituting for p and q where p =s(-) and q = t(-)
v/2-2 j2+2
= 5n + i6 + jA/2^(r2 +rAt-i) 1^ f cos(o))
7 49 7 7
7 7
By Lemmas 1 and 2, we can manipulate the variables and get
- ^ + !.Ms(r+0-4£_4
7 49 7 7
+ Mi!S(r2+r<*-i)-Mi?(C0S(u)
7 7
Rearranging, we get
+( +s(r2 + rN~l) +1 cos(o))) + ( + J2s(r+r N) T^fcosCtJ)))
111 11
+ ( + J2s(r2+rN~l) -\/2rcos((j)))
7 7 49
+ ^^s(r+rN)-^^tcos( 1 1
= +^a^-l+i^+rV^r^
7 7 7 7 49 7 7
d2 = 0 and ^ + =£ (2c+c?.) so
= S (2ci+ ^ ^ + ~~s{r+r N) ~ ~^~4* cos( page 42


Substituting for values of s and t, we get
£(2c,+d,)+|(0)
= £(2c,-4)
Q.E.D.
This case above is defined as a Type A P3 X PN. An easy filter for
Type A is | cos(oj) | although this does not predict all values of N
which are Type A. Values of N (1 < N < 100) which are Type A are
1, 2, 6, 8, 9, 11, 12, 13, 16, 17, 18, 21, 22, 23, 25, 26, 27, 28, 30, 31,
32, 35, 36, 39, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51, 53, 54, 55,
57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 76,
77, 78, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90, 91, 92, 94, 95, 96,
97, 99, and 100. Examining all values of N from 3 to 1,000 shows us
that approximately 770 of these graphs are Type A. Thus, P3 x PN graphs
are asymptotically 77.0% Type A.
There are other classes or types of P3 X PN. Type B is
characterized by a minimum fraction domination with b3 = 0 and b2
overdominated and a maximal fractional 2-packing with b2 = 0 and b3
underpacked. Examples of Type B are N = 15, 19 and 20. Type C is
characterized by a minimal fractional domination with a^ b3 = 0 and b2
overdominated and a maximal fractional 2-packing with b2, b3 = 0 and b3
page 43


underpacked. Examples of Type C are 10, 24 and 34. Formulas similar
to that developed for type A can be found for Type B and Type C.
Not all P3 x PN are in the Type A, Type B or Type C. P3 x P2g is
an example of this fourth class or type which cannot be characterized
definitely. This class contains at least two zeros in the fractional
domination, frequently a, and b3 and one or two zeros in the P2 at b2 and
sometimes also b3. In most cases, there are two nodes in the fractional
domination which are overdominated. This type must be solved for each
N. The distinguishing characteristic of each class of P3 x PN is the
number and location of nodes in the fractional domination which are
overdominated.
page 44


Chapter 4
P4XPN
The symmetry of P4 x PN graphs is shown below, where the aj
elements are the side columns of the graph and the bj elements are the two
center columns. An example of this designation of elements is found in
Figure 20 for P4 X P7.
al b, bi ai
a2 b2 b2 a2
a3 b3 b3 a3
a4 b4 b4 a4
a3 b3 b3 a3
a2 b2 b2 a2
ai bi bi ai
Figure 20
Symmetry of P4 X P7 fractional graph
No general solution has been published to date for PM X PN
fractional domination or fractional 2-packing, M = 4. Hare [4,5] has
published a number of specific solutions for N = 4 and 8, which were
solved by linear programming methods. Using similar linear
programming methods, it appears that there are at least two classes of
page 45


fractional domination patterns for different values of N. This chapter will
present a generalized solution for M = 4 and most values of N > 4. It
will also prove the upper and lower limits of the fractional domination and
give those values of N which are in different classes.
Theorem 11: For N < 10, we have 7^4 x P4) given below.
N 4 5 6 7 8 9 10
Yf^M x PN) 4 5 6 6* 8 89
11 29 3 38 131
Proof: For N < 10, verifying a value of 7f(PM x PN) can be done by
giving a fractional domination and a fractional 2-packing whose weights
sum of 7f(PM x PN).
page 46


[Hare, 4]
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
Fractional 2-packing
P4 x P4
0 0 0 0
1 1 1 1
2 2 2 2
1 1 1 1
2 2 2 2
0 0 0 0
Fractional domination
P4 x P4
Figure 21
The P4 x P4 graph can also be represented as a perfect fractional
domination graph.
page 47


0 1 1 0
2 2
1 0 0 1
2 2
1 0 0 1
2 2
0 1 1 0
2 2
P4 X P4
Figure 22
Proof that y,{P4 x P4) =4.
page 48


6 2 2 6
11 11 11 11
3 1 1 3
11 11 11 11
1 4 4 1
11 11 11 11
3 1 1 3
11 11 11 11
6 2 2 6
11 11 11 11
Fractional domination and Fractional 2-packing
P4 x P5
Figure 23
Proof that x P5) = 5 3/11.
page 49


11 8 8 11
29 29 29 29
10 1 1 10
29 29 29 29
6 7 7 6
29 29 29 29
6 7 7 6
29 29 29 29
10 1 1 10
29 29 29 29
11 8 8 11
29 29 29 29
Fractional domination and Fractional 2-packing
P4 x P6
Figure 24
Proof that 7^4 x P6) = 6 1/29
page 50


8 31 11 31 11 31 8 31
12 1 1 12
31 31 31 31
10 6 6 10
31 31 31 31
3 8 8 3
31 31 31 31
10 6 6 10
31 31 31 31
12 1 1 12
31 31 31 31
8 11 11 8
31 31 31 31
Fractional domination and Fractional 2-packing
P4 x P7
Figure 25
Proof that 7f(P4 x P7) = 6 28/31
[Hare, 4,5]
page 51


1 5 2 5 2 5 1 5
2 5 0 0 2 5
2 1 1 2

5 5 5 5
1 1 1 1

5 5 5 5
1 1 1 1

5 5 5 5
2 1 1 2

5 5 5 5
2 5 0 0 2 5
1 2 2 1

5 5 5 5
1 0 0 1
0 0 0 0
0 1 1 0
2 2
1 0 0 1
2 2
1 0 0 1
2 2
0 1 1 0
2 2
0 0 0 0
1 0 0 1
Fractional 2-packing Fractional domination
P4 x P8
P4 x P8
Figure 26
Proof that yf(P4 x Pg) = 8
page 52


17 9 9 17
38 38 38 38
12 3 3 12
38 38 38 38
6 11 11 6
38 38 38 38
9 7 7 9
38 38 38 38
16 4 4 16
38 38 38 38
9 7 7 9
38 38 38 38
6 11 11 6
38 38 38 38
12 3 3 12
38 38 38 38
17 9 9 17
38 38 38 38
Fractional domination and Fractional 2-packing
P4 x P9
Figure 27
Proof that 7XP4 x P9) = 8 16/38
page 53


Theorems 1 and 2 show there is a maximum fractional 2-packing and a
minimum fractional domination of PM x PN that are symmetric about the
N
middle row(s). To save space, we will only show the first (if N is
even) or (if N is odd) rows of such symmetric weightings for
graph P4 x P10 (Figure 28).
44 40 40 44
131 131 131 131
47 7 7 47
131 131 131 131
33 30 30 33
131 131 131 131
47 7 7 47
131 131 131 131
44 40 40 44
131 131 131 131
Fractional domination and Fractional 2-packing
P4 x P10
Figure 28
Proof that yt(P4 x P10) = 9 89/131
page 54


For N > 10, we can solve each value of N using linear
programming methods as we did for 4 < N < 11. However, the purpose
is to find a general algorithm which will generate all values of 7XP4 x PN).
v
In developing a general algorithm for P4 x PN, we were struck by the
existence of two separate "classes" of N. Each class had a slightly
different pattern of a;s and bfs and are designated as Type A and Type
non-A.
Let
-3-1/5. 3v/5-l
2 \ 2
2
-1 V^-3
0=cos ------
4
e
N-3
(jl) =---0

Definition 3: Define the following values:
P=-
-?-[(3 -2v/5)cos(i)) +(^ll)cos(A)]
XX **
A+B
page 55


q=-

A+B
A=[(-^)(r+rN)(cosmM(.^^(r+rN)(cos(m
^=[()(^2+^w_1)(cos((J))) -(v/5)(r2+rw'1)(cos(A.))]
arjr +p(ri+rN+1~i) + 4 cos[(i-^-^)0]
1 1 Zr
bt= + p (r i+rJV+1-i) (-S^-I) q cos[(i-)0]
11 2 2 2
Lemma 13: r + 1 + = ^ (trivial)
r 2
Lemma 14: For all k and 6, we have
cos[(k-l)0] + cos[(k+l)0] = fe_3_ CQS^0) (trj[viai)
2
Using these variables we have just defined, we now need to verify
that the sum of the weights on the nodes in the neighborhood of a; equals
1 and the sum of the weights on the nodes in the neighborhood of b| also
equals 1. We will first examine the sum of a^, + aj + ai+1 + b;, the
neighborhood of ai5 and the consider the neighborhood of b;, or a; + bul
+ 2b; + bi+1.
Lemma 15: For all i, we have a^ + aj + ai+1 + b; = 1.
Proof: a;., + as + ai+, + bj
page 56


= + p(r1_1 + rN+1''n) + q cos[(i-l- )9) +
11 2 11
+ p(r + rN+1'') + q cos[(i- y-^ )0]
+ y + p(r1+1 + rN+1'(1+1)) + qcos[(i + l- y-^ )9]
+ + (^+*) p(r' + rN+l i) - *) q cos[(i- ^ )9]
11 2 2 2
= 1 + p(ri_1 + f + ri+1 + rN+2_i + rN+1'i + rN+i)
+ (y^L) P(fi + rN+l i) + q {cos[((i-l)- y-^ )0] + cos[(i- y^ )&]
+ COS[((i + l)- y^ )6]- (^y) COS[(i- y^ )0]}
= 1 + p(r* + 1 + r)(r + rNi+1)
+ q [cos((k-l)0) + cos((k+l)0) ( ^y ) (cos(kfl)]
. . . N+l
where k = i --------- .
2
Then by Lemmas 9 and 10, we have the result.
Q.E.D.
Lemma 16: For all i, we have a; + b^ + 2b; + bi+1 = 1.
Proof: aj + b^ + 2b, + bi+1
= y + p(r + rN+l r) + q cos[(i- y^ )0]
page 57


+ ii + (^r} p(I-i 1 + rN+2i}" (^r} q cos[((i'1)_ 6]
+ 2^+2 p(r' + rN+I i) 2 (^) q cos[(i- ^ 6]
+ ry + p(ri+1 + rN-j) (^) q [cos[((i + l) ~~ )0]
= 1 + (^y^) P (ri_1 + r1 + ri+I + rN+2- + rN+1i + rN-)
+ (4y^) p (r1 + r^11) (^) qcos[((i-l)- )6]
- (^p) q cos[(i- )d]~ (^p) qcos[((i + l) ~~ W
- Y^ q cos^i_ ~y~~ )0] = 1 + (-^) p O"1 + 1 + r)(fi +
j.N-t-1-i)
- (J^). {q [cos((k-l)0) + cos((k+l)0) + (&*) cos(k0)]}
2 2
. ,N+l.
where k = i (---------) .
2
Then by Lemmas 9 and 10, we have the result.
Q.E.D.
We have proved that the sums of the weights of the nodes in the
neighborhood of a, and b; are equal to 1. In order to show that the
variables and values defined describe a fractional domination or fractional
2-packing, all values of a; and bj must be greater or equal to 0 and less
page 58


than or equal to 1. In addition, for the general case of P4 x PN, we need a
formula for the sum of all nodes (i.e., 7,{P4 x PN)) so that the calculation
of all nodes is not necessary.
Theorem 12: Let {a^, {b;} be a Type A weighting of a P4 x PN. If
a; > 0 and b; > 0 Vi, then £(2a; + 2bj) = a,+b.
n 11 1 U 1
Proof: £2aj + 2b; = + 2 X) b;
- 2( -^j- )Lan + ai + ai+i + b; + 2( -jy )Xbi., + 2bi + bi+1
+ a; + 16 ai 11 + 6 11 a2 + 6 a + 11 16 aN + 11 b 11
+ 11 b2 + 4 11 t>N-l + 11 bN
3 2 32 12
= 2( )(N-2) + 2( )(N-2) + a, + a2
11 11 11 11
+ bj + b2
11 11
Since a, + a, + b, = 1 and a, + 2b, + b2 = 1,
ION 12 , 8 ,
---- + a, + b,
11 11 11
Q.E.D.
page 59


A Type A P4 x PN graph is perfectly dominated. A test for Type A is
| q | < 0.42. For values of N = 4 to 100, all Type As were predicted
by this test. Values of N which are Type A are 5, 6, 7, 9, 10, 11, 12,
13, 14, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 30, 31, 32, 34,
34, 36, 37, and 38. |q| takes extreme values from 0.1 (many values of
N) to 73 (at N = 375). The varying values of q are due to the cyclical
nature of the cos(0) and cos(X) terms in the denominator. Interestingly,
these cyclical cosine values result in a semi-regular pattern of values of N
which are non-Type A. For example, N = 8 is a non-Type A, as is N =
15, N = 22, N = 29 and N = 33. There are 7 values between 8 and 15,
7 values between 15 and 22, 7 values between 22 and 29 and 4 values
between 29 and 33, resulting in a 1-1-1-A pattern. We observed this 7-7-
7-4 pattern consistently for values of 4 < N < 1000. However, a second
pattern, 1-1-1-1-A, also appears, which makes it difficult to use this
observation to predict non-Type A graphs. Other values of N for P4 x PN
have no discernable pattern and therefore cannot be solved for the general
case.
Theorem 13: [Hare, 4,5]
10W 4 10W 12
----+ ------------+
11 11 f 11 11
page 60


Proof: For the lower bound of y(, assign a value of to the corners,
3 2
a value of to the side nodes (a:) and a value of to all interior
11 11
nodes and bP The sum of the neighborhood of the corner nodes is
The sum of the neighborhood of the side nodes is at most 1 and the sum
of the neighborhood of the interior nodes is 1.
The total sum of the lower bound of y{ is
4 3 2 1ON 4
4() +2(iV-2)() +2(A0() = +
11 11 11 11 11
For the upper bound of yf, assign a value of to the corner nodes, a
3 2
value of to the side nodes and a value of to the interior
11 11
nodes. The sum of the neighborhood of the corner nodes is 1. The sum
of the neighborhood of the side nodes is at least 1 and the sum of the
interior nodes is at least 1.
The total sum of the upper bound of y( is
5 3 3 2 10N 12
4() + 2(N-2)i) + 4() + 2(N-2)() = +
11 11 11 11 11 11
Q.E.D.
page 61


Chapter 5
P5 x PN
For P5 x PN, aj elements are the side columns of the graph, bj elements
are the next two inner columns and Cj elements are center column. An
example of this designation of elements is found in Figure 29 for P5 X PN.
al bi Cl bi ai
a2 b2 c2 b2 a2
a3 b3 c3 b3 a3
a4 b4 c4 b4 a4
a3 b3 c3 b3 a3
& ro b2 c2 b2 a2
ai bi Cl bi ai
Figure 29
Symmetry of P5 X P7 fractional graph
For all values of M,N > 3, no generalized solution has been published
to date for PM X PN fractional domination or 2-packing. Hare [4,5] has
page 62


published a number of specific solutions for M = 5 and N = 6 and 9,
which were solved by linear programming methods. Using similar linear
programming methods, it appears that there are at least three classes of
fractional domination patterns for M = 5 and different values of N. This
chapter will present some specific solutions for M = 5 and a lower and
upper bound for N = 3i, i = 2, 3,...
Theorem 14: For N = 5, 7, 8, 9, 10, and 11, 7f(P5 x PN) is
Proof: For N = 5, 7, 8, 9, 10, and 11, verifying a value of 7f(P3 x PN)
can be done by giving a fractional domination and a fractional 2-packing
whose weights sum to 7^3 x PN).
page 63


4 11 _7_ 22 5 22 _7_ 22 4 11
7 1 3 1 7
22 11 22 11 22
5 3 5 3 5
22 22 11 22 22
7 1 3 1 7
22 11 22 11 22
4 7 5 7 4
11 22 22 22 11
Fractional domination and fractional 2-packing
P5xP5
Figure 30
Proof that 7, page 64


1 3 U 3 1
2 8 8 2
1 1 1 1 1
8 8 4 8 8
1 1 1 1 1
4 8 2 8 4
1 0 0 0 1
2 2
1 1 1 1 1
4 8 2 8 4
1 1 1 1 1
8 8 4 8 8
1 3 0 3 1
2 8 8 2
Fractional 2-packing
1 1 1 1 1
4 4 4 4 4
1 1 1 1 1
2 2 2 2 2
0 0 0 0 0
0 1 1 1 0
2 2 2
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
1 1 1 1 1
4 4 4 4 4
Fractional domination
P5 x P7
P5 x P7
Figure 31
Proof that 7f(P5 x P7) = 8 1/2.


31 16 25 16 31
74 74 74 74 74
27 2 17 2 27
74 74 74 74 74
14 12 17 12 14
74 74 74 74 74
21 18 5 18 21
74 74 74 74 74
21 18 5 18 21
74 74 74 74 74
14 12 17 12 14
74 74 74 74 74
27 2 17 2 27
74 74 74 74 74
31 16 25 16 31
74 74 74 74 74
Fractional domination and fractional 2-packing
P5 X ^8
Figure 32
Proof that y^Ps x P8) = 9 24/37.
page 66


1 6 1 3 1 3 1 3 1 6
1 1 0 1 1

2 6 6 2
1 1 1 1 1

6 6 3 3 6
1 1 1 1 1

6 6 3 6 6
1 1 0 1 1

2 6 6 2
1 1 1 1 1

6 6 3 6 6
1 1 1 1 1

6 6 3 6 6
1 1 0 1 1

2 6 6 2
1 1 1 1 1

6 3 3 3 6
1 1 1 1 1
2 6 3 6 2
1 0 1 0 1
3 3 3
1 1 1 1 1
6 6 3 6 6
1 1 0 1 1
3 3 3 3
1 1 0 1 1
6 6 6 6
1 1 0 1 1
3 3 3 3
1 1 1 1 1
6 6 3 6 6
1 0 1 0 1
3 3 3
1 1 1 1 1
2 6 3 6 2
Fractional 2-packing Fractional domination
P5 x P9
P5 x P9
Figure 33
Proof that 7XP5 x P9) = 10 2/3
page 67


Theorems 1 and 2 show that there is a maximum fractional 2-packing and
a minimum fractional domination of PM x PN that are symmetric about the
N
middle row(s). To save space, we will only show the first (if N is
N+l
even) or (if N is odd) rows of such symmetric weightings for
graphs P5 x P10 (Figure 34) and P5 x P (Figure 35).
page 68


70 40 9 40 70
131 131 131 131 131
21 12 42 12 21
131 131 131 131 131
28 16 56 16 28
131 131 131 131 131
66 19 1 19 66
131 131 131 131 131
18 29 36 29 18
131 131 131 131 131
Fractional Domination and Fractional 2-packing
P5 x P10
Figure 34
Proof that y,(Ps x P10) = 11 123/131
page 69


7 9 0 9 7
20 20 20 20
1 1 1 1 1
5 5 10 5 5
1 1 1 1 1
4 20 2 20 4
1 0 3 0 1
2 10 2
1 3 1 3 1
4 20 5 20 4
1 2 1 2 1
10 5 5 5 10
Fractional domination and fractional 2-packing
P5 x Pn
Figure 35
Proof that 7XP5 x Pn) = 13.
page 70


Theorem 15: For N = 3i, i = 4, 5, 6
Pf(P5 x PN) = (10i+4)/9 < Yr ^ JfVs x PN) = (10i+6)/9
Proof: It is possible to construct a fractional domination of P5
follows:
a, = 1/6; b, = c, = 1/3
ai+2 = 1/2; i = 0, 1, 2...
a, = 1/2; 1 i+2
bj = 1/6; j 1
ci+2 = 0
ck = 1/3; k ^ i+2
The sum of y( = (10i+6)/9.
Hare [5] has shown that yf(P5 x PN) > (10i+4)/9.
PN as
Q.E.D.
page 71


Chapter 6
Pm x Pm
An easier problem to solve is to examine cases of PM x PM which show
a 4-fold symmetry. An example of this type of symmetry is shown in
Figure 36 below.
a b c d c b a
b d e f e d b
c g h i h g c
d j k 1 k j d
c g h i h g c
b d e f e d b
a b c d c b a
Figure 36
Using this symmetric model, the number of variables are decreased and
the problem is thus simpler to solve using linear programming.
Interestingly, the fractional domination of the square is not necessarily
perfect.
page 72


Theorem 16: For M = 6, 7, 8, 9 and 11, we have given Yf(PM x PM).
M 6 7 8 9 11
Yf(Pvi x Pm) ni 22 14 SI 00 22 26
4 2 27 61 27
Proof: For M = 6, 7, 8, 9 and 11, verifying a value of Yf(PM x PM) can
be done by giving a fractional domination and a fractional 2-packing
whose weights sum to 7f(PM x PM).
page 73


9 3 1 1 3 9
16 16 4 4 16 16
3 0 5 5 0 3
16 16 16 16
1 5 1 1 5 1
4 16 8 8 16 4
1 5 1 1 5 1
4 16 8 8 16 4
3 0 5 5 0 3
16 16 16 16
9 3 1 1 3 9
16 16 4 4 16 16
Fractional 2-packing
P6xP6
Figure 37(a)
page 74


0 1 2 3 16 3 16 1 2 0
1 5 1 1 5 1
-
2 16 8 8 16 2
3 1 1 1 1 3

16 8 4 4 8 16
3 1 1 1 1 3

16 8 4 4 8 16
1 5 1 1 5 1
-
2 16 8 8 16 2
0 1 2 3 16 3 16 1 2 0
Fractional domination
P6 x P6
Figure 37(b)
Proof that 7f(P6 x P6) = 8 3/4.
page 75


1 3 1 1 1 3 1
4 8 4 4 4 8 4
3 1 1 1 1 1 3
8 8 8 4 8 8 8
1 1 1 1 1 1 1
4 8 4 4 4 8 4
1 1 1 0 1 1 1
4 4 4 4 4 4
1 1 1 1 1 1 1
4 8 4 4 4 8 4
3 1 1 1 1 1 3
8 8 8 4 8 8 8
1 3 1 1 1 3 1
4 8 4 4 4 8 4
Fractional domination
P7 x P7
Figure 38(a)
page 76


6 2 2 3 2 2 6
14 7 7 14 7 7 14
2 0 3 3 3 0 2
7 14 14 14 7
2 3 2 1 2 3 2
7 14 7 7 7 14 7
3 3 1 1 1 3 3
14 14 7 14 7 14 14
2 3 2 1 2 3 2
7 14 7 7 7 14 7
2 0 3 3 3 0 2
7 14 14 14 7
6 2 2 3 2 2 6
14 7 7 14 7 7 14
Fractional 2-packing
Pv x P7
Figure 38(b)
Proof that y,(P7 x P7) = 11 1/2
page 77


13 7 6 8 8 6 7 13
27 27 27 27 27 27 27 27
7 1 6 5 5 6 1 7
27 27 27 27 27 27 27 27
6 6 9 3 3 9 6 6
27 27 27 27 27 27 27 27
8 5 3 7 7 3 5 8
27 27 27 27 27 27 27 27
8 5 3 . 7 7 3 5 8
27 27 27 27 27 27 27 27
6 6 9 3 3 9 6 6
27 27 27 27 27 27 27 27
7 1 6 5 5 6 1 7
27 27 27 27 27 27 27 27
13 7 6 8 8 6 7 13
27 27 27 27 27 27 27 27
Fractional domination and Fractional 2-packing
£*8 X ^8
Figure 39
Proof that yf(P8 x P8) = 14 22/27.
page 78


Assignment of values for P9 x P9.
a b c d e d c b a
b f g h i h g f b
c g j k 1 k j g c
d h k m n m k h d
e i 1 n 0 n 1 i e
d h k m n m k h d
c g j k 1 k j g c
b f g h i h g f b
a b c d e d c b a
a 12
61
b 49
122
c 43
122
d 21
122
e 19
61
f 3
61
page 79


g 9
122
h 10
61
i 21
61
j 22
61
k 15
61
1 1
61
m 13
61
n 9
61
0 25
61
Fractional domination and Fractional 2-packing
P9 x P9
Figure 40
Proof that 7f(P9 x P9) = 18 15/61.
page 80


Assignment of values for Pu x Pn.
a b c d e f e d c b a
b g h i j k j i h g b
c h 1 m n 0 n m 1 h c
d i m P q r q P m i d
e j n q s t s q n j e
f k 0 r t u t r 0 k f
e j n q s t s q n j e
d i m p q r q p m i d
c h 1 m n 0 n m 1 h c
b g h i j k j i h g b
a b c d e f e d c b a
page 81


2-packing fractional domination
a 18 3
27 27
b 9 12
54 27
c 9 21
54 54
d 9 7
27 108
e 8 13
27 54
f 7 53
27 108
g 0 3
54
h 9 11
27 108
i 11 33
54 108
j 3 11
27 54
k 4 3
27 108
2-packing fractional domination
1 8 4
27 27
m 1 35
54 108
n 13 6
54 27
0 10 2
27 27
P 13 0
54
q 7 19
27 108
r 0 49
108
s 7 4
27 27
t 3 27
27 108
u 10 0
27

Pn x Pn
Figure 41
Proof that y^P,, x P,,) = 26 22/27
page 82


Chapter oo
TfCPM x Pn)
In conclusion, this thesis has examined the general case of 7({Pm x Pn),
where M,N e N. If M = 1 or 2, there is an algorithm for constructing the
2-packing and fractional domination graphs and a formula to calculate Yf
for all values of N. These were first published by Hare.
However, for M > 3, there does not appear to be a generalized
algorithm or formula to determine yf except for very specific values of N.
For the values of M = 3, 4 and 5, it appears that there are more than one
set of algorithms and formulas for different values of N.
Examining PM x PM does not show any easy algorithms or formula for
graphs or y{. One can make some observations, however, about PM x PN,
M,N > 3. If Xj equals zero, then the fractional domination is not perfect.
If Xj of the fractional domination is equal to 0, then the same Xj in the two-
packing will be underpacked. Conversely, if X; of the two-packing is 0,
then the same XjOf the fractional domination will be overdominated.
The problem of finding a generalized algorithm for the fractional
domination graph and fractional 2-packing graph remains a difficult one.
At this time, there does not seem to be any easy answers.
page 83


References
1. Fisher, David C., "The 2-Packing Number of Complete Grid
Graphs," Ars Combinatoria, 30 (1993) 261-270.
2. Fisher, David C., "The Domination Number of Complete Grid
Graphs," submitted to Journal of Graph Theory, (1994).
3. Grinstead, D.L. and Slater, P. J., "Fractional Domination and
Fractional Packing in Graphs," Congressus Numeratum, 71 (1990),
153-172.
4. Hare, E. 0., "k-Weight Domination and Fractional Domination of PM
x PN," Congressus Numeratum, 78 (1990), 71-80.
5. Hare, E. O., "Fibonacci Numbers and Fractional Domination of PM x
PN," manuscript, 1992.
page 84


Full Text

PAGE 1

THE FRACTIONAL DOMINATION NUMBER OF COMPLETE GRID GRAPHS by Linda A. Bisbee B.S., Birmingham-Southern College, 1975 M.S. (Biology), Purdue University, 1977 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1995

PAGE 2

This thesis for the Master of Science degree by Linda A. Bisbee has been approved by _lL_i 1{) )' Date 11

PAGE 3

Bisbee, Linda A, (M.S., Applied Mathematics) The Fractional Domination Number of Complete Grid Graphs Thesis directed by Associate Professor David C. Fisher ABSTRACT The M X N complete grid graph (notated PM x PN) is a graph with MN nodes arranged in a square grid so that each node is connected to the nodes immediately above, below, left and right of it. Each node is assigned a non-negative weight such that the sum of the weight on each node and its immediate neighbors is less than or equal to 1. This is the fractional 2--packing. The sum of the weights of the nodes is then maximized. The dual of the linear program problem is the fractional domination, in which the sum of the weight on each node and its irnn1ediate neighbors is greater than or equal to 1. The maximum sum of the weight in a fractional 2-packing is equal to the minimum sum of weights in a fractional domination. The common value is the fractional domination number. Hare [4,5] has found minimal fractional dominations for the nodes of P, x PN and P2 x PN graphs for all N. Additionally, minimal fractional Ill

PAGE 4

dominations of PM x PN have been found for some other values of M and N. This thesis finds minimal fractional domination of P3 x PN for most N (asymptotically about 77%) and P4 x PN for most N (asymptotically about 80%). Some results are given for the minimum fractional domination of larger grids. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. lV

PAGE 5

CONTENTS Figures Yll CHAPTER 0 Introduction Theorem 1 2 Theorem 2 5 Theorem 3 7 1 P, X PN 9 Theorem 4 9 2 P, X PN 11 Theorem 5 11 Theorem 6 11 3 PJ X PN 14 Theorem 7 15 Theorem 8 36 Theorem 9 40 Theorem 10 41 4 P, X PN 45 Theorem 11 46 Theorem 12 59 Theorem 13 60 5 P5 x PN ', ... 62 Theorem 14 63 Theorem 15 71 v

PAGE 6

6 p6 X PN ... Theorem 16 00 y,(PM X PN) REFERENCES .. VI 72 73 83 84

PAGE 7

FIGURES Figure 1 1 2 5 3 P3 x P1 6 4 10 5 13 6 Symmetric weights for P1 x P7 14 7 pl X p4 16 8 p] X P, 17 9 pl X p6 18 10 P3 x P7 19 11 P3 x P8 20 12 P3 x P9 21 13 pl X PIIJ. 22 14 PJ X pll 24 15 PJ X pl2 25 16 pl X pll 26 17 PJ X pl4 27 Vll

PAGE 8

18 p] X PIS 28 19 P3 x P7 with designation of c, d elements 39 20 Symmetry of P4 x P7 45 21 P4 x P4 47 22 P4 x P4 48 23 P, X P, 49 24 P, X p6 50 25 P, X P, 51 26 P, X P, 52 27 P, X P9 53 28 P, X PIO 54 29 Symmetry of P5 x P7 62 30 P, X P, 64 31 P5 X P7 65 32 P5 x P8 66 33 P, X p9 67 34 P5 x P10 69 35 P, X PI! 70 36 72 37(a) Fractional 2-packing of P6 x P6 74 VIII

PAGE 9

37(b) Fractional domination of P6 x P6 38(a) Fractional domination of P7 x P7 38(b) Fractional 2-packing of P7 x P7 39 P8 X Ps 40 P, X p9 41 P11 X pll IX 75 76 77 78 80 82

PAGE 10

Chapter 0 Introduction Let G be a graph such that the nodes of G are arranged in a "checkerboard" pattern, where M is the number of nodes in each horizontal row and N is the number of nodes in each vertical column, Each node in G is connected to the node immediately above, below, left and right of that node, The notation PM x P, is used to designate such a graph, Further, let G be a graph such that the nodes of G have nonnegative weights such that the sum of a node and its neighbors is greater than or equal to I, wl .. l,_i I Wl,)-1 wi,J I wi+l,.i Figure 1 Example of an interior node (w,,) and its 4 neighbors If w,.,,, + w1 1 1 + w,,, + w,,,, 1 + w,, ,,, 1 for all i,j, then G is a fractional dominated graph. Conversely, if the nodes of G have non-negative weights such that the sum of a node and its neighbors is less than or equal to 1, page 1

PAGE 11

+ + w1 1 + 1 + '" s 1 for all i, j G is then a fractional 2-packing graph, If the weights of the nodes of a fractional domination graph are solved as a linear programming problem, the weights of the nodes of the fractional 2-packing graph are its dual. We can express the fractional domination linear program as: for n-vectors x andy, let x 2 y (or conversely, x s y) mean that x, 2 y, (or x, s y) for all i, Let 1 and 0 be vectors whose components are all one or all zero, respectively, We will further define N(G) as the neighborhood matrix of G, y1 also called the fractional domination number, is the minimum sum of the weights of all vertices of G, so it is the solution to the linear programming problem, y1(G) =min 1 T x subject to x:>O and N(G)x:>l X As the dual linear program, the fractional 2-packing can give another formulation of the fractional domination number, y1(G), y1(G) =max 1 T x subject to nO and N(G)xd X Theorem 1: There is a minimal fractional domination of PM x PN which page 2

PAGE 12

Proof: Let w,., be a minimal fractional domination of PM x P,. For simplicity, define w,, = 0 fori 0, i ;;;, M, j 0 or j ;;;, N. Then for all i,j with 1 i M and 1 j N, we have M N LL wiJ=yjPMxPN) i l 1 Let w't,j = Then w't,j = w' I [,_I 1 4 If we then add w',, + w',.,.1 + terms, we get 1 (the neighborhood of w,) 4 wi.j+l + w',.1 1 + w',,1,, and rearrange the page 3

PAGE 13

+ + + 1 (the neighborhood of w M-i + 1 ) 4 1 (the neighborhood of w1_N-1+1 ) 4 1 (the neighborhood of wM-i"LN-J+;) ;::: 4 1 (4) ;::: 1 4 (b) If we consider the sum of w'1 1 for all i and j and rearrange the terms as we did above, then M N l t1f;; 4(wij+wM-i+lJ.+wi,N-J+l +wM-i+l..N-J+l) = 1 -W4 'J (c) w',_1 = w'i,N-J+l By symmetry in the definition of w',_1 and w'1_N-J+1 the two nodes are equaL (d) W = w' Lj M-i+ l.J page 4

PAGE 14

By symmetry in the definition of w' ,,, and w' M,1 1 ,J' the two nodes are equaL Q,E,D, Theorem 2: There is a maximum fractional 2-packing of PM x P, which Proof: Similarly, if we let v,,, be a maximum fractional 2-packing of PM x PN, and define v in the same way as w and w' were defined, there is a maximal fractional 2-packing of PM x which has 4-fold symmetry, Le, Q.E.D, The weights on each individual node may not be the same for the fractional 2-packing and the fractional domination, We use squares to represent the nodes because of the typesetting, a, a, a, a, a 5 a6 a, a a9 Figure 2 page 5

PAGE 15

0 1 0 _,_ 2 1 1 1 -2 2 2 0 l 0 2 Fractional domination -y, (Hare, [4]) 5 2 Figure 3 3 1 8 4 1 0 4 3 1 -8 4 Fractional 2-packing 5 2 3 8 1 -4 3 8 Hare [4,5] has found -y1(P, X PN) and -y1{P2 X PN) for all values of N. Additionally, Hare [4,5] has found -y, (P3 X PN) for N = 3, 4, 5, 6, 7, 8, 10, 11, 14; -y, (P4 X PN) for N = 4, 5, 8 and -y1 (P5 X PN) for N = 6, 9. This thesis will find -y,{P, X PN) and -y1{P4 X PN) for an infinite family of values for N and give some specific examples of -y1(P5 X PN) and -y,{PN X P,J. Also a lower limit of the fractional domination of P5 X PN for all values of N will be proven. page 6

PAGE 16

Important considerations of the value of rr(PM x PN) are the upper and lower limit of fractional domination for all M, N in those cases where the actual value of y1(PM x PN) is not known. Hare [5] has published general limits based upon Fibonacci numbers. Fibonacci numbers are the sequence {0, 1, 1, 2, 3, 5, 8, 13 ... }, where F0 = 0, F1 = 1, and Theorem 3: (Hare [5]) When N, M 2: 2, where C = D = 3 FM + FM_1 and c" and c1 are positive values depending only on M. Also, cr 2: 4 FM_1 when M > 6 D For 2 < M < 6, bounds are: 5 7 N+ 2 7 page 7 5 N + 7 4 7

PAGE 17

10 N+ 11 20 N + 18 4 11 8 18 page 8 10 N + 11 20 N + 18 12 ll 20 18

PAGE 18

Chapter 1 Hare [ 4] found the fractional domination number of P 1 x P". For completeness. we repeat these results. Theorem 4: For all N 1, we have ,,(P, x PN) = IN13l Proof: For N = 0 (mod 3), nodes 2, 5, ., 3i+2, ... N-1 are given values of 1. All other nodes are given values of 0. For N = 1 (mod 3) or N = 2 (mod 3), nodes 1, 4, 7, ... 3i+1, ... are given values of 1. All other nodes are given values of 0 (see Figure 2). For all N, this is both a fractional domination and a fractional 2-packing. Since the number of nodes which are given the value of 1 is N, i we 3 have ,,(P1 x PN) equals Q.ED The weights for all values of N are both a fractional 2-packing and a fractional domination of P1 x PN. Such a weight where the weights are both a fractional two-packing and a fractional domination is called perfect fractional dominations and a graph with perfect fractional domination is called a perfect fractional domination graph. Figure 4 gives e!tamples of P1 x P, for N = 6, 7 and 8. page 9

PAGE 19

Chapter 1 Hare [4] found the fractional domination number of P1 x P,. For completeness, we repeat these results. Theorem 4: For all N 2 1, we have ,,(P, x P,) = INi3l Proof: For N = 0 (mod 3), nodes 2, 5, ... 3i+2, ... N-1 are given values of 1. All other nodes are given values of 0. For N = l (mod 3) or N = 2 (mod 3), nodes 1, 4, 7, ... 3i+1, ... are given values of 1. All other nodes are given values of 0 (see Figure 4). For all N, this is both a fractional domination and a fractional 2-packing. Since the number of nodes which are given the value of 1 IS we Q.E.D. The weights for all values of N are both a fractional 2-packing and a fractional domination of P1 x PN. Such a weight where the weights are both a fractional two-packing and a fractional domination is called perfect fractional dominations and a graph with perfect fractional domination is called a perfect fractional domination graph. Figure 4 gives examples of P1 x PN for N = 6, 7 and 8. page 9

PAGE 20

For space considerations, these graphs are represented as their transposes. For example, P1 x P6 is actually shown as P6 x P, or (P1 x P6)T 0 I 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 P,(P1 x P8 ) = y1(P1 x P,) = 3 Figure 4 page 10 0 1 1 0

PAGE 21

Chapter 2 Hare [4] also found the fractional domination number of P2 x PN. There are two separate formulas depending upon whether N is even or odd. Interestingly, P2 x PN is also a perfect fractional domination graph. Theorem 5: For N odd, y1 (P2 x PN) = (N + 1)/2. Proof: Consider the following weights: I 2 if i is odd. Let v,,, = v2 1 = 0 if i is even. If i is odd, then left and right neighbors are 0 and its upper (or lower) neighbor is 112. The sum of its neighborhood is exactly I. If v = 0, its left and right neighbor is l/2 and its upper (lower) neighbor is 0. The sum of its neighborhood is exactly l. So this is a perfect fractional domination. The graph contains a total of (N + I) nodes of value l/2 and (N l) nodes of value 0. The sum of all of the nodes of the graph is therefore (N + l )/2 Theorem 6: For N even, y1(P2xPN) page ll Q.E.D. N(N +2) --2(N + l)

PAGE 22

Proof: Let N 2i, and r Z(N + ii/ is even 1 l N+1-i if i is odd 2(N + 1) If i is even, the neighbor to the left has an odd index and equal to N+1-(i-1) 2(N + 1) N + 1 (i + 1) 2(N + 1) the neighbor to the right has an odd index and equal to and v, and its neighbor below (or above) have equal indices and have equal values of 2(N + 1) The sum of the neighborhood of v, is equal to i + i T (Nc_l_L:ji_1) + (N + 1) (i +_!2 2(N + 1) = L If i is odd, the neighbor to the left has an even index and is equal to i 1 the neighbor to the right has an even index and is equal to 2(N + 1) i + 1 and v, and its neighbor below (or above) have equal indices 2(N + 1) and have equal values of N + 1 i 2(N + 1) The sum of the neighborhood of v, i 1 + i + 1 + 2(N + 1 ) 2i 2(N + 1) is equal to 1 So these weights are a perfect fractional domination_ page 12

PAGE 23

The sum of v 1 1 is thus (N)(N + 1 ) 2 2 N(N + 2) (N + 1) 4(N + 1) N(N + 2) Since l.: v,,, = l.: v2 1 we then have y1 = "-'-''-'---"'"2(N + 1) Q.E.D. For space considerations, these graphs are represented as their transposes. For example, P2 X P6 is actually shown as P6 x P2 or (P2 x P6)r 3 1 7 7 3 1 7 7 1 0 2 1 0 2 2 2 7 7 2 2 -7 7 y,(P, X P6) = 1 0 2 1 0 2 24 7 1 2 I 2 y,(P, X P,) = 4 Figure 5 page 13 1 3 7 7 1 3 7 7 0 1 2 0 1 2

PAGE 24

Chapter 3 Only a few specific solutions has been published to date for P3 X PN fractional domination or 2-packing. Hare [4,5] bas published solutions for fractional domination for N = 3, 4, 5, 6, 7, 10, 11, and 14, which were solved by linear programming methods. Using similar linear programming methods, it appears that there are at least four classes of fractional domination patterns for different values of N. This chapter will find r1(P3 x PN) for an infinite number of values of N 3. Figure 6 is an example of this designation of elements for P3 X P7. For P3 X PN, let w1 1 = Wu = a, and w2_, = b1 Then a, = aN+t-i and b, = bN + 1 1 For simplicity, let a0 = aN, 1 = b0 = bN + 1 = 0. a, b, a, a, b, a, a. bJ a 3 a4 b4 a4 aJ b] a, a:: b, a::. a, b, a, Figure 6 Symmetrical weights for P3 X P7 page 14

PAGE 25

Theorem 7: For N :":: 15, we have 'Yr(P3 x PN) given below. N ,,(PJ X PN) N ,,{PJ X PN) N 1 1 6 3 11 sl 4 2 2 7 5 12 852 53 3 2_1_ 2 8 62 15 13 9E. 17 4 3_1_ 3 9 7 14 1oi 9 5 4 10 72 9 15 u2 17 Proof: For N = 1, see Chapter 1. For N = 2, see Chapter 2. For N = 3, see the Introduction. For N 4, verifying a value of ,,{P3 X PN) can be done by giving a fractional domination and a fractional 2-packing whose weights sum to rr(P3 X PN) page 15

PAGE 26

I I I --3 3 3 I 0 I --3 3 I 0 I --3 3 I I I --3 3 3 Fractional domination and Fractional 2-packing Figure 7 Proof that r1(P3 X P,) = 3 1/3. page 16

PAGE 27

1 1 1 4 2 5 1 0 1 4 4 1 0 1 -2 2 1 0 1 -4 4 1 1 1 --4 2 4 Fractional domination and Fractional 2-packing Figure 8 Proof that ,,{P3 X P,) = 4. page 17

PAGE 28

1 1 l 0 2 0 ,_ 3 3 3 3 1 0 j l 1 1 ----J 5 .l j :J I 0 I 1 0 1 , ,_ -3 3 3 3 1 0 1 1 0 1 --3 3 3 3 1 0 I 1 1 1 -----3 3 3 3 3 1 1 I 0 2 0 -,_ -3 3 3 3 Fractional 2-packing Fractional domination Figure 9 Proof that r1{P3 X P6 ) = 4 2/3, page 18

PAGE 29

I l l 2 I 2 ----10 ., lO 5 5 :I 2 J ,, .. j 0 l --5 10 5 4 'I I 0 I 7 3 7 5 5 20 10 20 2 1 2 1 1 1 ----5 5 5 10 5 10 1 0 1 7 3 7 ---5 5 20 10 20 2 3 2 1 0 1 ----5 10 5 4 4 1 1 1 2 1 2 -----10 2 10 5 5 5 Fractional domination Fractional 2-packing Figure 10 Proof that y1(P7 X P7 ) = 5 2/5. page 19

PAGE 30

0 3 0 11 4 11 5 30 15 30 2 2 2 3 0 3 --5 5 5 10 10 l 1 l I 2 1 -5 15 5 3 15 3 1 2 1 7 1 7 3 15 3 30 5 30 1 2 1 7 1 7 3 15 3 30 5 30 1 I 1 1 2 1 ---5 15 5 3 15 3 2 2 2 3 0 3 ----5 5 5 10 10 0 3 0 11 4 11 ---5 30 15 30 Fractional domination Fractional two-packing Figure 11 Proof that rr(P3 x P8 ) = 6 2/15. page 20

PAGE 31

0 4 0 2 3 2 ---7 7 7 7 3 3 3 2 0 2 --7 7 7 7 7 1 1 1 3 0 3 -7 14 7 7 7 5 3 5 2 1 2 ---14 14 14 7 7 7 2 0 2 1 2 1 ----7 7 7 7 7 5 3 5 2 1 2 ---14 14 14 7 7 7 1 1 1 3 0 3 -7 14 7 7 7 3 3 3 2 0 2 ---7 7 7 7 7 0 4 0 2 3 2 ---7 7 7 7 Fractional domination Fractional 2-packing pl X Pg Figure 12 Proof that rr
PAGE 32

1 l l l 5 l --3 3 3 9 9 9 l 0 l l 2 l --3 3 3 9 3 l 0 l I 0 l ---3 3 3 3 l l l 1 l l -3 9 3 3 9 3 2 2 2 2 2 2 ---9 9 9 9 9 9 2 2 2 2 2 2 --9 9 9 9 9 9 l l l l l l --3 9 3 3 9 3 l 0 1 1 0 1 -3 3 3 3 l 0 l 1 2 l ---3 3 3 9 3 1 l l 1 5 1 -3 3 3 9 9 9 Fractional 2-packing Fractional domination Figure 13 Proof that (1{P3 x P10) = 7 5/9. page 22

PAGE 33

1 1 1 ---4 4 4 1 1 1 ---4 8 4 3 1 3 ---8 8 8 1 0 1 --4 4 3 3 3 ---8 8 8 0 5 0 -8 Fractional domination Figure 14 Proof that y,(P3 x Pll) = 8 114. page 24 15 3 15 --56 14 56 29 1 29 --112 8 112 39 1 39 ---112 7 112 1 1 1 -4 28 4 41 0 41 -112 112 43 13 43 -112 56 112 Fractional 2-packing PJ X pll

PAGE 34

0 32 0 41 12 41 -53 106 53 106 21 21 21 16 0 16 -53 53 53 53 53 11 2 ll 33 9 33 -53 53 53 106 53 106 19 8 19 23 11 23 -53 53 53 106 53 106 15 5 15 14 10 14 ---53 53 53 53 53 53 14 10 14 35 4 35 -53 53 53 106 53 106 Fractional domination Fractional 2-packing Figure 15 Proof that y,{P3 x P,2 ) = 8 52/53. page 25

PAGE 35

0 10 0 -6 5 6 -17 17 17 17 7 7 7 5 0 5 --17 17 17 17 17 3 1 3 6 2 6 ---17 17 17 17 17 17 6 3 6 4 3 4 ----17 17 17 17 17 17 5 1 5 4 4 4 ---17 17 17 17 17 17 5 3 5 5 2 5 ---17 17 17 17 17 17 4 3 4 6 1 6 ---17 17 17 17 17 17 Fractional domination Fractional 2-packing Figure 16 Proof that rr(PJ X Pll) = 9 12/17. page 26

PAGE 36

0 13 0 5 4 5 -18 18 9 18 5 5 5 5 0 5 18 18 18 18 18 4 0 4 4 0 4 ---9 9 9 9 5 I 5 5 1 5 18 9 18 18 9 18 1 1 1 1 1 1 ----6 3 6 6 3 6 2 2 2 2 2 2 ------9 9 9 9 9 9 7 0 7 7 0 7 --18 18 18 18 Fractional domination Fractional 2-packing Figure 17 Proof that y1(P1 x P14) = 10 4/9 page 27

PAGE 37

0 ll 0 -6 5 6 ---17 17 17 17 6 6 6 6 0 6 ---17 17 17 17 17 5 0 5 5 0 5 --17 17 17 17 6 2 6 6 2 6 ----17 17 17 17 17 17 4 3 4 4 3 4 ----17 17 17 17 17 17 4 4 4 4 4 4 ----17 17 17 17 17 17 5 2 5 5 2 5 ---17 17 17 17 17 17 6 1 6 6 l 6 ---17 17 17 17 17 17 Fractional domination Fractional 2-packing Figure 18 page 28

PAGE 38

Proof that y,(P3 x P,5 ) = 11 2117. For N > 15, we can solve each value of N using linear programming methods as we did for 3 < N < 16. However, the purpose is to find a general algorithm which will generate all values of 'Y r{P 3 x P Nl. In developing a general algorithm for P3 x PN, we were struck by the existence of at least three separate "classes" of N. Each class had a slightly different pattern of a;'s and his and are designated as Type A, Type B and Type C. Let r -(1 +/2) +-/2/2 -1 2 e -1(/2-1) -cos -2 N-3 2 page 29

PAGE 39

N-5 Jc-(-)8 2 We have found values, designated as p and q, which are associated with the specific types of P 3 x P N and can be used to calculate a, and b1 for all i. These types of P3 x PN are designed as Type A, Type B and Type C. A Type A P 3 x P, is characterized by a domination graph where the weight of a1 = 0, the weight of b1 = 1 a2 and cannot be calculated by another formula, and b1 + b2 + b3 + 2a2 > l. If the sum of a node and its neighbors is greater than 1, that node is said to be overdominated. Definition 1: A Type A weighting of P3 x PN hasp and q where Fi 2 1 (v .. +l)cos(w)(-)(-)cos() 7 7 p and page 30

PAGE 40

a, 2 7 N+I + p(r' + rN+t ') + q cos[( z---)8], 'I i 2 b, (I -a, 1 -aN-t, i = I, N 1 7 + fi p(r' + rN+ti)-fi qcos[( i-N+I )8], 2 'I i> I, i
PAGE 41

By applying the definitions of p and q and distributing the results, we get = _?:_ [(r + rN)(-12 +1) cos(w) 7 ( 12 -1)(r2 + rN1)cos()] + (r1 + rN)[( 12 + 1)cos(w) 2 7 cos()] 7 +cos()[ 1 (r + rN) + ( 12 -1)(r2 + rN1 ) 2 7 7 =0 Lemma 4: For all i except i = 1 and i = N, we have a, 1 + a, + a,+ 1 + b1 = 1. (the neighborhood of a) Proof: a,_1 + a, + a," 1 + b, = + 2 7 2 7 +p(r11 +rN+11111)+qcos[( (i-1)-N+1 )8] 2 N+l + p(r1 + rN+ 1 1 ) + q cos[( 1--)8] 2 page 32 Q.E.D.

PAGE 42

+ 2 7 + p(r1 1 + + q cos[( (i+1)N+ 1 )8] 2 + 1 7 + f2 p(r1 + rN+l 1 ) f2 q cos[( i-N+ 1 )8] 2 + q {cos[( (i-l)-N+1 )8] +cos[( i-N+1 )8] + 2 2 cos[( (i+1)-N+1 )8]} 2 f2 cos[( iN+1 )8]} 2 = 1 + p(r' + (1+ f2 ) + r)(r1 +rN1 + 1 ) + q {cos( (k -1 )0) + cos( (k + 1 }11) + ( f2 1 )( cos(kO)} Then by Lemmas 1 and 2, we have the result. Lemma 5: Fori = 1 and i = N, we have a, + a2 + b, = 1. Q.E.D. Proof: Since b1 and bN do not follow the general formula of b1 we must treat i = 1 and i = N as special cases. By Theorem 1, since a1 = aN-i and b1 = bN_, we need only prove one case. For ease, we will take i = 1. a1 + a2 + b1 = 0 + a2 + (1 -a2 ) page 33

PAGE 43

= 1. Lemma 6: For all i > 2 and i < N-1, we have 2a 1 + b 1 1 + b 1 + b 1 .. 1 = 1. (the neighborhood of b) Proof: 2a 1 + b 1 .. 1 + b1 + b 1 + 1 = 2( + p(r1 + rN"11) + q cos[( i-N+1 )8]) + 1 7 2 7 + fi p(r'' + rN' lli-11)-fi q cos[( (i-1)N+ 1 )8] 2 + l + fi p(r' + rN+ 1-i) 7 fi q cos[( N+1 )8] i-2 + 1 + fi p(r'-cJ + rN+1-Ii-1) 7 fi q cos[( (i+1)-N+1 2 )8] = 1 + fi ( fi -1) p(r 1 + rN'11)-fi ( fi -1)p(r1 + r"H1 ) + fi ( fi -1) q cos[( (H)-N+1 )8] 2 -fi ( fi -1)qcos[( (H)-N+l )8] 2 = 1 + p(r1 + 1 + r)(r 1 + rN-i+1 ) + q{cos((k+l)O) + cos((k-1)0) -( fi -1 )(cos(k8))} page 34 Q.ED.

PAGE 44

N+l where k = i -(--) 2 Then by Lemmas 1 and 2 we have the result Lemma 8: In a Type A weighting, a2 = b2 and aN-I = bN I Q.E.D. Proof: By Theorem 1, a2 = aN-I and b2 = bN-I For ease, we will only prove a2 = b2 + 1 7 1 7 2 7 = b, + + p(r2 + rn1 ) + q cos(w) + fi p(r2 + rN-:) fi q cos(w) + (1fi )p(r' + rNI) + (1 + fi ) q cos(w) 1 7 + (1fi )p(r2 + r"1 ) + (1+ fi ) q cos(w) Applying the definition of p and q and distributing the results, we get = b, + _!_ {(fi -l)(r+rN)cos(w) + ( fi +l)(r+rN)cos(w) 7 + 2(r'+rN-1)cos(w)2(r2+rN-1)cos(w) + ( fi -l)(r2+rN-1)cos()-( fi -l)(r2+rN-1)cos() = b, page 35 Q.E.D.

PAGE 45

Proof: Since b1 and bN do not follow the general fonnula of b1 we must treat i = 1 and i = N as special cases. By Theorem I, since a, = aNi and b, = we need only prove one case. For ease, we will take i = 1. 2a1 + b, + b2 = 2 (0) + b, + b, = (1 -a2 ) + b2 Since a2 = b2 = I. Q.E.D. We have shown that the sums of the weights of the nodes in the neighborhood of a, and b1 are equal to 1 in the Type A P 3 x P N fractional domination graph. In order to show that the variables and values defined describe a fractional domination or fractional 2-packing, all values of a, and b1 must be greater or equal to 0 and less than or equal to 1. In addition, for the general case of P3 x P,, we need a formula for the sum of all nodes (i.e., y,(P3 x P,)) so that the calculation of the weight of each node is not necessary. Theorem 8: Let {a,}, {bJ be a Type A weighting of a P3 x PN. If a, 0 and b1 0 \ti, then the following is true: a) The neighborhood of b2 > 1 page 36

PAGE 46

b) or 5 N + 7 2 7 + 2 a,+ 7 N SN 2 2az 2hz L (2a1 +b) = + -+ -+ ioJ 7 7 7 7 Proof: a) b1 + b2 = 1 The neighborhood of b2 = b1 + b2 + 2a2 + b3 Since a2 > 0 and b3 > 0, the sum of the neighborhood of b2 > I b) rr = I;(2a, + b;) 4 10 a, + 14 14 = al + -aJ + ... + aN., 7 7 7 7 10 4 aN+ I bl + 6 b, + 4 bl + + aN-t + 7 7 7 7 7 4 bN + + 7 => r (2a, + b,) + + 4 aN.J + 7 I bN.J + 7 = 6 bN.J + I br-; 7 7 4 I; N(a1 ) + I [ N(b;) + 7 7 10 a" + 6 bl + 1 b, -7 7 7 b 7 N Since I; N(b2 ) > I and a, = 0, then page 37 10 7 a I 2 b3 7 + 4 7 a,

PAGE 47

4 (N-2) + 1 (N-4) 16 + 2b, + 2 b, lr = + a, 7 7 7 7 Since 1 = a, + b,, then rr= 5N+2 + 2 + 2 bl a, 7 7 7 Q.ED We now need to consider the Type A fractional 2-packing graph. For clarity, we will use the notation c1 and d1 where i = 1, 2 ... N as the nodes of the 2-packing graph. We have found values sand t which can be used to calculated c1 and d1 for all i. A Type A 2-packing graph is characterized by weight of d2 = 0 and c, + d1 + c1 < 0. When the sum of the weights of a node and its neighbors is less than 1 in a 2 fractional 2-packing graph, the node is said to be underpacked. Definition 2: Define the following values: c = I 2 7 1 7 N+1 + s(r1 +p992Xr"f' 'r1):os[(i-)8] 2 + 12 s(r1 + r'" ,_,) 12 t cos[(i-N+ 1 )8] 2 page 38

PAGE 48

c l d, c l c, d, c, Cl d3 cJ c 4 d, c, c, d, Cl c, d, c, c, d, c, P3 x P7 with designation of c, d elements Figure 19 Let values of IJ, w, and r be defined as previously. Lemma 10: If c, and d1 have the same values as above, then the sum of the neighborhood of c1 = 1. Proof: Since the sum of the neighborhood of c, is not dependent upon the values of s and t but on the definition of c, and d1 this proof is the same as Lemma 4. QED. Lemma 11: If c, and d, have the same values as above, then the sum of the neighborhood of d, = 1. page 39

PAGE 49

Proof: Since the sum of the neighborhood of d, is not dependent upon the values of s and t but upon the definition of c, and d,, this proof is the same as Lemma 6. Lemma 12: d2 = 0. Proof: d2 = 1 7 + 12 s(r + rN+12)12 tcos(w) Q.ED. By applying the definitions of s and t and distributing the results, we get 1 N+1 . (2 cos[ --8 ](r2+ rN+ 12)-2(r + rN+1)cos(w) 7 2 + 2(r2 + rN+I-2)cos(w)-2(r2 + rN+1 2)cos(w) -2(r2 + rN'1 2)cos(w) + 2(r + rN+1)cos(w) = () Q.E.D. Theorem 9: Suppose G is a P3 X PN fractionally 2-packed graph. Then if c, 2 0 and d, 2 0 v i and d2 = 0, the following is true: a) The sum of the neighborhood of c1 < 1. b) [ (2c, + d,) Proof: 5N 7 + a) (Proof by contradiction): page 40

PAGE 50

Suppose that I N(a,) = c, + c, + d, 1. c, + c, + c1 + d, = 1 => d, = 0 But d, > 0 => c, + c, + d, < d. = = N-I N-l b) I;2c, + d, = 4" 1 L, L N(b) 7;o2 71"2 2 (N-2) + 7 0: 2c, id, 5 N + 8 7 7 20 -C; + 7 = 0: + 12 c, 7 8 7 d, c, + 12 d, + 7 Theorem 10: Given the previous definitions. then N N L (2a, +b)= L (2c1 +d) l = 1 2 d, 7 Proof: The sum of all of the weights of a Type A graph is ;__ 5N 2 2a2 2b1 L, '"' 7 7 7 7 since b, = 1 -a:5N 2b1 4b2 2b3 -1-7 7 7 7 Substituting for values of b,. b1 and b,. we get 5N 16 4/2-2 2. N-1 4/2+2 -----+ --p(r 'r ) q cos(w) 7 49 7 7 page 41 Q.E.D.

PAGE 51

Substituting for p and q where 2 p=s(-) /2-2 and = 5n 16 -4-6/2 ( 2 N-J) 4-6/it ( ) -++ s r +r -cos w 7 49 7 7 + -4-4 r2 3 N 2 4-4 12 ---"-Y-"s(r +r -)-Y"" tcos(A) 7 7 By Lemmas 1 and 2, we can manipulate the variables and get = 5N 16 4+4 12 4/2-4 -++ Y s(r+rN)---tcos(
PAGE 52

Substituting for values of s and t, we get 2 '\' (2c. +d.)+ -(0) ....t I l 7 Q.E.D. Tbis case above is defined as a Type A P3 X PN. An easy filter for Type A is I cos(w) I although this does not predict all values of N which are Type A. Values of N (l ,;:; N ,;:; 100) which are Type A are l, 2, 6, 8, 9, 11, 12, 13, 16, 17, 18, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 35, 36, 39, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51' 53, 54, 55' 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 76, 77, 78, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90, 91, 92, 94, 95, 96, 97, 99, and 100. Examining all values of N from 3 to 1,000 shows us that approximately 770 of these graphs are Type A. Thus, P3 x P, graphs are asymptotically 77.0% Type A. There are other classes or types of P3 X PN. Type B is characterized by a minimum fraction domination with b3 = 0 and b2 overdominated and a maximal fractional 2-packing with b2 = 0 and b3 underpacked. Examples of Type Bare N = 15, 19 and 20. Type C is characterized by a minimal fractional domination with a1 b3 = 0 and b2 overdominated and a maximal fractional 2-packing with b2 b3 "' 0 and b3 page 43

PAGE 53

underpacked. Examples of Type C are 10, 24 and 34. Formulas similar to that developed for type A can be found for Type B and Type C. Not all P1 x P, are in the Type A, Type B or Type C. P3 x P" is an example of this fourth class or type which cannot be characterized definitely. This class contains at least two zeros in the fractional domination, frequently a1 and b1 and one or two zeros in the P2 at b2 and sometimes also b1 In most cases, there are two nodes in the fractional domination which are overdominated. This type must be solved for each N. The distinguishing characteristic of each class of P3 x PN is the number and location of nodes in the fractional domination which are overdominated. page 44

PAGE 54

Chapter 4 P, X PN The symmetry of P 4 x P N graphs is shown below, where the aJ elements are the side columns of the graph and the b, elements are the two center columns. An example of this designation of elements is found in Figure 20 for P4 X P7 a, b, b, a, a, b, b, a, a3 b, b3 aJ a, b, b, a, a, b, b, a, a2 b, b, a, a I b, b, a, Figure 20 Symmetry of P4 X P7 fractional graph No general solution has been published to date for PM X P, fractional domination or fractional 2-packing, M = 4. Hare [4,5] has published a number of specific solutions for N = 4 and 8, which were solved by linear programming methods. Using similar linear programming methods, it appears that there are at least two classes of page 45

PAGE 55

fractional domination patterns for different values of N. This chapter will present a generalized solution for M = 4 and most values of N 4. It will also prove the upper and lower limits of the fractional domination and give those values of N which are in different classes. Theorem 11: For N :S 10. we have y,(P4 x P4 ) given below. N 4 4 5 s2 ll 6 6-1 29 7 8 8 9 38 10 9 89 131 Proof: For N :S 10, verifying a value of 'Yr(PM x PN) can be done by giving a fractional domination and a fractional 2-packing whose weights page 46

PAGE 56

[Hare, 4] 0 0 1 l 0 0 0 0 0 0 0 0 1 I I I --2 2 2 2 0 0 0 0 1 1 1 I -2 2 2 2 0 0 1 1 0 0 0 0 Fractional 2-packing Fractional domination Figure 21 The P 4 x P 4 graph can also be represented as a perfect fractional domination graph. page 47

PAGE 57

0 0 1 1 -2 2 0 0 1 1 --2 2 0 0 l 1 --2 2 0 0 I 1 -2 2 Figure 22 page 48

PAGE 58

6 2 2 6 -11 11 11 11 3 1 1 3 --11 11 11 li 1 4 4 1 11 11 11 11 3 1 1 3 --11 11 11 11 6 2 2 6 --11 11 11 11 Fractional domination and Fractional 2-packing Figure 23 Proof that ,,(P4 x P1 ) = 5 3/11. page 49

PAGE 59

11 8 8 11 -29 29 29 29 10 1 1 10 -29 29 29 29 6 7 7 6 29 29 29 29 6 7 7 6 --29 29 29 29 10 1 1 10 --29 29 29 29 11 8 8 11 --29 29 29 29 Fractional domination and Fractional 2-packing Figure 24 Proof that 'Yr(P4 x P6 ) = 6 1129 page 50

PAGE 60

8 11 11 8 -31 31 31 31 12 l 1 12 --31 31 31 31 10 6 6 10 -31 31 31 31 3 8 8 3 31 31 31 31 10 6 6 10 31 31 31 31 12 1 1 12 -31 31 31 31 8 11 11 8 --31 31 31 31 Fractional domination and Fractional 2-packing Figure 25 Proof that ,,(P4 x P7 ) = 6 28/31 !Hare, 4,5] page 51

PAGE 61

1 0 0 I 1 2 2 1 ----5 5 5 5 2 0 0 2 0 0 0 0 -5 5 2 1 l 2 0 0 1 1 -5 5 5 5 2 2 l 1 1 1 0 0 1 1 --5 5 5 5 2 2 l l 1 1 0 0 l 1 --5 5 5 5 2 2 2 1 1 2 0 0 1 I ---5 5 5 5 2 2 2 0 0 2 0 0 0 0 -5 5 1 2 2 l 1 0 0 I -5 5 5 5 Fractional 2-packing Fractional domination Figure 26 Proof that /r(P4 x P8 ) = 8 page 52

PAGE 62

17 9 9 17 -38 38 38 38 12 3 3 12 --38 38 38 38 6 11 ll 6 38 38 38 38 9 7 7 9 --38 38 38 38 16 4 4 16 --38 38 38 38 9 7 7 9 38 38 38 38 6 11 11 6 -38 38 38 38 12 3 3 12 38 38 38 38 17 9 9 17 38 38 38 38 Fractional domination and Fractional 2-packing Figure 27 Proof that )'r{P4 x P9 ) = 8 16/38 page 53

PAGE 63

Theorems I and 2 show there is a maximum fractional 2-packing and a minimum fractional domination of PM x PN that are symmetric about the middle row(s). To save space, we will only show the flfSt N (if N is 2 even) or N+1 2 (if N is odd) rows of such symmetric weightings for graph P, x P,0 (Figure 28). 44 40 40 44 131 131 131 131 47 7 7 47 -131 131 131 131 33 30 30 33 --131 131 131 131 47 7 7 47 --131 131 131 131 44 40 40 44 --131 131 131 131 Fractional domination and Fractional 2-packing Figure 28 Proof that r1(P4 x Plll) = 9 89/131 page 54

PAGE 64

For N > 10, we can solve each value of N using linear programming methods as we did for 4 < N < 11. However, the purpose is to find a general algorithm which will generate all values of rr(P4 x PN). In developing a general algorithm for P4 x PN, we were struck by the existence of two separate "classes" of N. Each class had a slightly different pattern of a,' s and b;' s and are designated as Type A aud Type non-A. Let -3-.(5 3/5-1 2 2 _____ _,_ __ 2 1 15-3 _V_J_ N-3 2 N-5 A.=-B 2 4 Definition 3: Define the following values: 1 [ (3 -2/5)cos( tj>) + ( -3/5-1 )cos( A.)] 11. 2 p A+B page 55

PAGE 65

-[5)(r+r N)(cos())] -[( 3[5 +S (r+r N)(cos(A.))] 2 3 N 1 N+1 +p(r'+r _,) +q cos[(i---)6] I 11 2 Lemma 13: r + 1 + 1 r = -/5-1 2 Lemma 14: For all k and e, we have (trivial) cos[(k-l)e] + cos[(k+l)O] = [5-3 cos(k8) (trivial) 2 Using these variables we have just defined, we now need to verify that the sum of the weights on the nodes in the neighborhood of a1 equals 1 and the sum of the weights on the nodes in the neighborhood of b1 also equals 1. We will first examine the sum of a11 + a1 + a1,.1 + b1 the neighborhood of a1 and the consider the neighborhood of b1 or a1 + b1 1 Lemma 15: For all i, we have a,_1 + a, + a,H + b1 = 1, Proof: a,_, + a, + a,, 1 + b: page 56

PAGE 66

= 3 11 N+1 + p(r'' + r"''"") + q cos[(i-1)0) + 2 N+1 + p(r' + r" '1 ') + q cos[(i)0] 2 + + 3 11 2 11 N+l + p(r1 1 + r'''''") + q cos[(i+1)0] 2 3 11 + (/5+1 ) p(r1 + r'"') + q {cos[((i-1)-N+l )e] + cos[(iN+ 1 )e] 2 2 2 + cos[((i+1)-N+ 1 )lij-(/5-l) cos[(i-N+l )Ill} 2 2 2 = 1 + p(r' + 1 + r)(r1 + r''+') + q Ieos( (k -1 )II) + cos( (k + 1 )II) -( /5-3 ) ( cos(kli)] 2 where k = i-N+l 2 Then by Lemmas 9 and 10, we have the result. Lemma 16: For all i, we have a,+ b1 1 + 2b1 + b,.,, = 1. Proof: = 3 11 a1 + b,_1 + 2b, + N+1 + p(r' + r'''') + q cos[(i)OJ 2 page 57 Q.E.D.

PAGE 67

+ + 2 2 11 + 2 11 =1+ (/5-1 ) q [cos[((i+1)-N+l )0] 2 2 J5 1 ) q cos[((i-1)(N+l) )OJ 2 2 (JS-1 ) q cos[(i(N+1 ) )0]-(/5-1 ) q cos[((i+l) (N+l) )e] 2 2 2 2 -(/5-3 ) q cosf(i-(Nd) )OJ= 1 + (/5+1 ) p (r' + 1 + r)(r' + 2 2 2 (JS-1 ) {q [cos((k-1)0) + cos((k+1)0) + 2 N+l where k = i -(--) 2 T'hen by Lemmas 9 and 10, we have the result. ( /5-3 ) cos(kO)]} 2 QED We have proved that the sums of the weights of the nodes in the neighborhood of a, and b, are equal to 1. In order to show that the variables and values defined describe a fractional domination or'fractional 2-packing, all values of a, and b, must be greater or equal to 0 and less page 58

PAGE 68

than or equal to I. In addition, for the general case of P4 x PN, we need a formula for the sum of all nodes (i.e., rr(P4 x PN)) so that the calculation of all nodes is not necessary. Theorem 12: Let {a,}, {b,} be a Type A weighting of a P4 x PN. If a, 2 0 and b, 2 0 v i, then L: (2a, + 2b;) = Proof: L: 2a, + 2b, = 2 L: a, + 2 L: b, = 2( 3 ) L: a, I + ai + airl + b, + 2( 2 -11 11 +a,+ 16 + 6 a, + 6 + 11 al 11 11 aN-1 + 4 b, + 4 bN-1 + 18 bN -11 11 11 ION +_i_b 11 11 l Jj I ) L:b:-1 + 2b, + b,.,l 16 aN+ 18 b, 11 11 = 2( 3 )(N-2) + 2( 2 )(N-2) + 32 al + 12 a, 11 11 11 11 + 36 b1 + 8 b, --11 11 Since a 1 + a, + b 1 = I and a, + 2b 1 + b, = 1, ION 12 + 8 b1 = + -al 11 11 ll page 59 QED.

PAGE 69

A Type A P4 x graph is perfectly dominated. A test for Type A is I q I < 0.42. For values of N = 4 to 100, all Type A's were predicted by this test. Values of N which are Type A are 5, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 30, 31. 32, 34, 34, 36, 37, and 38. I q 1 takes extreme values from 0.1 (many values of N) to 73 (at N = 375). The varying values of q are due to the cyclical nature of the cos() and cos(,\) terms in the denominator. Interestingly, these cyclical cosine values result in a semi-regular pattern of values of N which are non-Type A. For example, N = 8 is a non-Type A, as is N = 15, N = 22, N = 29 and N = 33. There are 7 values between 8 and 15, 7 values between 15 and 22, 7 values between 22 and 29 and 4 values between 29 and 33, resulting in a 7-7-7-4 pattern. We observed this 7-77-4 pattern consistently for values of 4 < N < 1000. However, a second pattern, 7-7-7-7-4, also appears, which makes it difficult to use this observation to predict nonType A graphs. Other values of N for P 4 x P N have no discernable pattern and therefore cannot be solved for the general case. Theorem 13: [Hare, 4,5] page 60

PAGE 70

Proof: For the lower bound of rr assign a value of 4 11 to the corners, a value of 3 to the side nodes (a1 ) and a value of 11 2 ll to all interior nodes and b1 The sum of the neighborhood of the corner nodes is 9 11 The sum of the neighborhood of the side nodes is at most 1 and the sum of the neighborhood of the interior nodes is 1. The total sum of the lower bound of rr is 4 3 2 10N4 4(-) + 2(N2)(-) I 2(N)(-) = +-11 11 11 11 11 For the upper bound of rr. assign a value of 5 11 to the corner nodes, a value of 3 to the side nodes and a value of 2 to the interior 11 11 nodes. The sum of the neighborhood of the corner nodes is 1. The sum of the neighborhood of the side nodes is at least 1 and the sum of the interior nodes is at least 1. The total sum of the upper bound of rr is 5 3 3 2 10N 12 4(-) +2(N-2)(-) +4(-) +2(N-2)(-) =+-11 11 11 11 ll 11 Q.E.D page 61

PAGE 71

Chapter 5 For P5 x PN, a, elements are the side columns of the graph, b1 elements are the next two inner columns and c, elements are center column. An example of this designation of elements is found in Figure 29 for P5 X PN. al b, c I b, a. a2 b, C::. b, a, aJ b] c, b, a, a4 b4 c4 b4 a4 aJ b, CJ b3 a, a, b, c2 b, a, a I b, c, b, a, Figure 29 Symmetry of P5 X P7 fractional graph For all values of M,N 3, no generalized solution has been published to date for PM X PN fractional domination or 2-packing. Hare [4,5] has page 62

PAGE 72

published a number of specific solutions for M = 5 and N = 6 and 9, which were solved by linear programming methods. Using similar linear programming methods, it appears that there are at least three classes of fractional domination patterns for M = 5 and different values of N. This chapter will present some specific solutions for M = 5 and a lower and upper bound for N = 3i, i = 2, 3, ... Theorem 14: For N = 5, 7, 8, 9, 10, and 11, rr(P5 x PN) is given below. 5 N riPs 62 X PN) 11 7 8_! 2 8 9 24 37 9 3 10 11 123 131 11 13 Proof: For N = 5, 7, 8, 9, 10, and 11, verifying a value of yr(P3 x PN) can be done by giving a fractional domination and a fractional 2-packing whose weights sum to r1(P1 x PN). page 63

PAGE 73

4 7 5 7 4 --11 22 22 22 11 7 1 3 1 7 -22 11 22 11 22 5 3 5 3 5 -22 22 11 22 22 7 1 3 1 7 --22 11 22 11 22 4 7 5 7 4 --11 22 22 22 11 Fractional domination and fractional 2-packing P, X P, Figure 30 Proof that 'Yr(P5 x P5 ) = 6 3111 page 64

PAGE 74

0 1 3 3 1 l 1 l 1 l ---2 8 8 2 4 4 4 4 4 1 1 1 1 1 l 1 1 1 1 ---8 8 4 8 8 2 2 2 2 2 1 1 l 1 1 0 0 0 0 0 ---4 8 2 8 4 0 0 0 1 1 0 0 1 l 1 -2 2 2 2 2 1 I 1 1 1 0 0 0 0 0 --4 8 2 8 4 1 1 1 1 1 1 1 l 1 1 ------8 8 4 8 8 2 2 2 2 2 0 1 3 3 l 1 I 1 1 1 --2 8 8 2 4 4 4 4 4 Fractional 2-packing Fractional domination P, X P, Figure 31 Proof that rr(P5 x P7 ) = 8 112. page 65

PAGE 75

31 16 25 16 31 -74 74 74 74 74 27 2 17 2 27 ----74 74 74 74 74 14 12 17 12 14 ---74 74 74 74 74 21 18 5 18 21 -----74 74 74 74 74 21 18 5 18 21 ---74 74 74 74 74 14 12 17 12 14 74 74 74 74 74 27 2 17 2 27 -74 74 74 74 74 31 16 25 16 31 ----74 74 74 74 74 Fractional domination and fractional 2-packing Figure 32 Proof that r1{P5 x P8 ) = 9 24/37. page 66

PAGE 76

I 1 1 1 1 1 1 1 1 I -------2 6 3 6 2 6 3 3 3 6 0 0 I 1 1 0 l 1 1 1 -----3 3 3 2 6 6 2 1 1 1 1 1 l 1 l 1 1 -----6 6 3 6 6 6 6 3 3 6 1 1 0 1 l 1 1 -l I l -3 3 3 3 6 6 3 6 6 l 1 0 l l l 0 l l 1 ---6 6 6 6 2 6 6 2 l 1 0 1 1 1 1 -l l l --3 3 3 3 6 6 3 6 6 1 I I 1 1 1 1 1 1 l ---6 6 3 6 6 6 6 3 6 6 0 0 l 1 1 0 l l I l ---3 3 3 2 6 6 2 1 1 l l 1 l l 1 1 l ----2 6 3 6 2 -6 3 3 3 6 Fractional 2-packing Fractional domination Figure 33 Proof that rr
PAGE 77

Theorems 1 and 2 show that there is a maximum fractional 2-packing and a minimum fractional domination of PM x PN that are symmetric about the middle row(s). To save space, we will only show the first N (if N is 2 even) or N+l 2 (if N is odd) rows of such symmetric weightings for graphs P5 x PIU (Figure 34) and P5 x P11 (Figure 35). page 68

PAGE 78

70 40 9 40 70 --131 131 131 131 131 21 12 42 12 21 131 131 131 131 131 28 16 56 16 28 131 131 131 131 131 66 19 1 19 66 131 131 131 131 131 18 29 36 29 18 131 131 131 131 131 Fractional Domination and Fractional 2-packing Figure 34 Proof that y1(P5 x P10) = 11 123/131 page 69

PAGE 79

7 9 0 9 7 --20 20 20 20 1 l 1 1 1 ---5 5 10 5 5 1 1 1 1 1 ----4 20 2 20 4 0 0 1 3 1 --2 10 2 1 3 1 3 l ----4 20 5 20 4 l 2 1 2 l -----10 5 5 5 10 Fractional domination and fractional 2-packing Figure 35 Proof that y,{P5 x P11) = 13. page 70

PAGE 80

Theorem 15: For N = 3i, i = 4, 5, 6 ... P,(P, X PN) = (lOi +4)/9 < fl :s; rr(P, X PN) = (lOi +6)/9 Proof: It is possible to construct a fractional domination of P5 x PN as follows: a, = 1/6; b, = c, = 1/3 a1+2 = 112; i = 0, 1, 2. a, = 1/2; I ,o i + 2 b: = 1/6; j "' 1 c, = 113; k ;" i+2 The sum of rr = (10i+6)/9. Hare [5] has shown that r1{P5 x PN) 2 (lOi +4)/9. page 71 Q.E.D.

PAGE 81

Chapter 6 PM X PM An easier problem to solve is to examine cases of PM x PM which show a 4-fold symmetry. An example of this type of symmetry is shown in Figure 36 below. a b c d c b a b d e f e d b c g h l h g c d J k l k J d c g h l h g c b d e f e d b a b c d c b a Figure 36 Using this symmetric model, the number of variables are decreased and the problem is thus simpler to solve using linear programming. Interestingly, the fractional domination of the square is not necessarily perfect. page 72

PAGE 82

Theorem 16: ForM = 6, 7, 8, 9 and 11, we have given rr(PM x PM). M 6 7 8 9 11 rr(PM X sl ul 14 22 26 22 PM) 4 2 27 61 27 Proof: ForM = 6, 7, 8, 9 and 11, verifying a value of rr(PM x PM) can be done by giving a fractional domination and a fractional 2-packing whose weights sum to rr(PM x PM). page 73

PAGE 83

9 3 1 1 3 9 --16 16 4 4 16 16 0 0 3 5 5 3 ----16 16 16 16 1 5 1 1 5 1 --4 16 8 8 16 4 1 5 1 1 5 1 ---4 16 8 8 16 4 0 3 5 5 0 3 16 16 16 16 9 3 1 1 3 9 ----16 16 4 4 16 16 Fractional 2-packing Fignre 37(a) page 74

PAGE 84

0 0 1 3 3 1 --2 16 16 2 1 5 1 1 5 1 ----2 16 8 8 16 2 3 1 1 l l 3 --16 8 4 4 8 16 3 1 1 1 1 3 ---16 8 4 4 8 16 1 5 1 l 5 l ----2 16 8 8 16 2 0 0 1 3 3 1 ---2 16 16 2 Fractional domination Figure 37(b) page 75

PAGE 85

1 3 1 1 1 3 1 -4 8 4 4 4 8 4 3 1 1 1 I 1 3 ---8 8 8 4 8 8 8 1 1 1 1 1 1 1 ----4 8 4 4 4 8 4 1 1 0 I 1 1 l -4 4 4 4 4 4 1 1 I 1 1 1 1 ----4 8 4 4 4 8 4 3 1 1 1 1 1 3 --8 8 8 4 8 8 8 1 3 1 1 1 3 1 ---4 8 4 4 4 8 4 Fractional domination P, X P, Figure 38(a) page 76

PAGE 86

6 2 2 3 2 2 6 -----14 7 7 14 7 7 14 0 0 2 3 3 3 2 ---7 14 14 14 7 2 3 2 1 2 3 2 ------7 14 7 7 7 14 7 3 3 1 1 1 3 3 ------14 14 7 14 7 14 14 2 3 2 I 2 3 2 ---7 14 7 7 7 14 7 2 0 3 3 3 0 2 ---7 14 14 14 7 6 2 2 3 2 2 6 ------14 7 7 14 7 7 14 Fractional 2-packing P, X P, Figure 38(b) Proof that y1(P7 x P7 ) = 11 112 page 77

PAGE 87

13 7 6 8 8 6 7 13 --27 27 27 27 27 27 27 27 7 1 6 5 5 6 1 7 27 27 27 27 27 27 27 27 6 6 9 3 3 9 6 6 --27 27 27 27 27 27 27 27 8 5 3 7 7 3 5 8 27 27 27 27 27 27 27 27 8 5 3 7 7 3 5 8 -27 27 27 27 27 27 27 27 6 6 9 3 3 9 6 6 -27 27 27 27 27 27 27 27 7 1 6 5 5 6 1 7 --27 27 27 27 27 27 27 27 13 7 6 8 8 6 7 13 --27 27 27 27 27 27 27 27 Fractional domination and Fractional 2-packing Figure 39 Proof that 'Y 1(P 8 x P 8 ) = 14 22/27. page 78

PAGE 88

Assignment of values for P9 x P9 a b c d e d c b a b f g h 1 h g f b c g J k l k J g c d h k m n m k h d e 1 l n 0 n l 1 e d h k m n m k h d c g J k l k J g c b f g h 1 h g f b a b c d e d c b a a 12 -61 b 49 122 c 43 122 d 21 122 e 19 -61 f 3 -61 page 79

PAGE 89

g 9 122 h 10 -61 I 21 -61 J 22 -61 k 15 -61 I 1 -61 m 13 -61 n 9 -61 0 25 -61 Fractional domination and Fractional 2-packing Figure 40 Proof that y1(P, x P9 ) = 18 15/61. page 80

PAGE 90

Assignment of values for P11 x P". a b c d e f e d c b a b g h I J k J I h g b c h I m n 0 n m I h c d I m p g r g p m I d e J n g s t s g n J e f k 0 r t u t r 0 k f e J n g s t s g n J e d i m p g r g p m I d c h I m n 0 n m I h c b g h I J k J I h g b a b c d e f e d c b a page 81

PAGE 91

2-packing fractional 2-packing fractional domination domination a 18 3 1 8 4 --27 27 27 27 b 9 12 ill 1 35 ---54 27 54 108 c 9 21 n 13 6 --54 54 54 27 d 9 7 0 10 2 --27 108 27 27 e 8 13 p l3 0 27 54 54 f 7 53 q 7 19 --27 108 27 108 g 0 3 r 0 49 -54 108 h s 9 11 7 4 -27 108 27 27 1 11 33 t 27 3 --54 108 27 108 J 3 ll u 0 10 --27 54 27 k 4 3 -27 108 Figure 41 Proof that r1{P11 x P11) = 26 22/27 page 82

PAGE 92

Chapter oo ,,(PM X PN) In conclusion, this thesis has examined the general case of x PN), where M,N E N. If M = 1 or 2, there is an algorithm for constructing the 2-packing and fractional domination graphs and a formula to calculate lr for all values of N. These were first published by Hare. However, for M 2 3, there does not appear to be a generalized algorithm or formula to determine It except for very specific values of N. For the values of M = 3, 4 and 5, it appears that there are more than one set of algorithms and formulas for different values of N. Examining PM x PM does not show any easy algorithms or formula for graphs or 'Yr One can make some observations, however, about PM x PN, M ,N 2 3. If x, equals zero, then the fractional domination is not perfect. If x, of the fractional domination is equal to 0, then the same x1 in the two packing will be underpacked. Conversely, if x, of the two-packing is 0, then the same x, of the fractional domination will be overdominated. The problem of finding a generalized algorithm for the fractional domination graph and fractional 2-packing graph remains a difficult one. At this time, there does not seem to be any easy answers. page 83

PAGE 93

References 1. Fisher, David C, "The 2-Packing Number of Complete Grid Graphs," Ars Combinatoria, 30 (1993) 261-270. 2. Fisher, David C., "The Domination Number of Complete Grid Graphs," submitted to Journal of Graph Theory, (1994). 3. Grinstead, D.L. and Slater, P. J., "Fractional Domination and Fractional Packing in Graphs," Congressus Numeratum, 71 (1990), 153-172. 4. Hare. E. 0 .. "k-Weight Domination and Fractional Domination of PM x PN," Congressus Numeratum, 78 (1990), 71-80. 5. Hare, E. 0., "Fibonacci Numbers and Fractional Domination of PM x PN," manuscript, 1992. page 84