THE FRACTIONAL DOMINATION
NUMBER OF
COMPLETE GRID GRAPHS
by
Linda A. Bisbee
B.S., BirminghamSouthern 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 nonnegative 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 2packing. 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 2packing 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 2packing 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 2packing 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.
wii.j
W i uj1 w WM wi,j+l
Wiflj
Figure 1
Example of an interior node (wg) and its 4 neighbors
If W;.,  + w,+ Wj + wij+1 + wi+1j > 1 for all i,j, then
G is a fractional dominated graph.
Conversely, if the nodes of G have nonnegative weights such that
the sum of a node and its neighbors is less than or equal to 1,
page 1
wii,j + Wi.j1 + wi,j + Wi,j+1 + wi+1J < 1 for all i, j
G is then a fractional 2packing 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 2packing graph are its dual. We can express the fractional
domination linear program as: for nvectors 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 2packing 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 4fold 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 + wMi+ij + wLN.j+1 + wM_i+1N.j+1).
Then
W i.jl = ~ (Wi,j1 + WMi+l,jl + Wi,Nj+2 + WMi+ KNj + 2)
W + 1 = "4 ^W'j+1 WMi+l,j + l + Wi,Nj + WMi + l,Nj)>
^ (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+wui.ij
i=i j=i 4
1 j + 1 + WMi+Wj+0
M N
= 4EE H
ii yi
= 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_iHj> the two nodes
are equal.
Q.E.D.
Theorem 2: There is a maximum fractional 2packing of PM x PN which
has 4fold 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 2packing of PM x
PN, and define v in the same way as w and w were defined, there is a
maximal fractional 2packing of PM x PN which has 4fold symmetry, i.e.,
Vij = VMi + l.j = Vi,Nj +1 = VMi+ l,Nj+ 1
Q.E.D.
The weights on each individual node may not be the same for the
fractional 2packing 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 2packing
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 = Fk1 + Fk2
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,...Nl 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 2packing.
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 2packing and
a fractional domination of P, x PN. Such a weight where the weights are
both a fractional twopacking 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,...Nl 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 2packing.
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 2packing and
a fractional domination of P, x PN. Such a weight where the weights are
both a fractional twopacking 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 + li 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 2packing. 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 2packing
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 2packing
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 2packing
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 2packing
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 2packing
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 twopacking
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 2packing
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 2packing
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 2packing 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 2packing
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 2packing
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 2packing
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 2packing
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 2packing
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/S1
2
0 =cos_1(^)
2
=(
N1
2
)0
O) =(
N3
2
)0
page 29
*=(
N5
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 at 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/2l)(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[(kl)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[( (i1) )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[( (i1)^ )0] + cos[( i)0] +
cos[( 0+D )0]}
 & cos[( i^ )0]}
= 1 + p(r + (1+ sj2 ) + r)(r +rNi+1)
+ q{cos((kl)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[( (i1) )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[( (i1)^ )0]
 y/2 ( y/2 1) q cos[( (i1)^ )0]
= 1 + p(r_1 + 1 + r)(r' + rNi+1)
+ q{cos((k+l)0) + cos((kl)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 2packing, 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;)
.Nl 2 +ai*i+b)+ifL^ai+ I 2 bii+hi + Kv>
II 4 1 + 10 a, + 7 14 a3 + 7 , 14 .. + aN.2
^ 10 + aNl + Ij aN + ~1 bl +  b2 + b3 + 7 7
+ ^ bN2 + bN.[ + 1 h bN
=>Â£(2ai + bj) = \ E N(a,) +  E N(b,) + 10 T a' + a2 7
+ ^ aNl + 10 y aN +  b1 + 7b>
+ ^ bNl + 6 k
Since Â£N(b2) > 1 and a! = 0, then
page 37
cn  r
Yr =  (N2) + (N4) + 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 2packing graph.
For clarity, we will use the notation Cj and di5 where i = 1, 2... N as the
nodes of the 2packing graph. We have found values s and t which can be
used to calculated Cj and di for all i. A Type A 2packing 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
2packing 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+rw1)
(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 2packed 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
N1
^E e m
' i=2 ' i=2
5 ,XT _ , 20 , 8 , 12 . , 2 .
 (N2) + 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+rN2)^q cos(A.)
2 2
Substituting for p and q where p =s() and q = t()
v/22 j2+2
= 5n + i6 + jA/2^(r2 +rAti) 1^ f cos(o))
7 49 7 7
7 7
By Lemmas 1 and 2, we can manipulate the variables and get
 ^ + !.Ms(r+04Â£_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 2packing 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 2packing 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 2packing, 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 2packing 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 2packing
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 2packing
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 2packing
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 2packing
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 2packing 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 2packing
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 2packing 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 2packing
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
nonA.
Let
31/5. 3v/5l
2 \ 2
2
1 V^3
0=cos 
4
e
N3
(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+1i) (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[(kl)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[(il )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[((il) 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((kl)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(Ii 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 + rNj) (^) q [cos[((i + l) ~~ )0]
= 1 + (^y^) P (ri_1 + r1 + ri+I + rN+2 + rN+1i + rN)
+ (4y^) p (r1 + r^11) (^) qcos[((il) )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.Nt1i)
 (J^). {q [cos((kl)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
2packing, 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>Nl + 11 bN
3 2 32 12
= 2( )(N2) + 2( )(N2) + 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 semiregular pattern of values of N
which are nonType A. For example, N = 8 is a nonType 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 111A pattern. We observed this 77
74 pattern consistently for values of 4 < N < 1000. However, a second
pattern, 1111A, also appears, which makes it difficult to use this
observation to predict nonType 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(iV2)() +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(N2)i) + 4() + 2(N2)() = +
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 2packing. 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 2packing
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 2packing
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 2packing
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 2packing
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 2packing 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 2packing 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 2packing
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 2packing
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 4fold 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 2packing
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 2packing
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 2packing
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 2packing
Â£*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 2packing
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
2packing 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
2packing 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
2packing 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 twopacking 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 2packing 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 2Packing Number of Complete Grid
Graphs," Ars Combinatoria, 30 (1993) 261270.
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),
153172.
4. Hare, E. 0., "kWeight Domination and Fractional Domination of PM
x PN," Congressus Numeratum, 78 (1990), 7180.
5. Hare, E. O., "Fibonacci Numbers and Fractional Domination of PM x
PN," manuscript, 1992.
page 84

PAGE 1
THE FRACTIONAL DOMINATION NUMBER OF COMPLETE GRID GRAPHS by Linda A. Bisbee B.S., BirminghamSouthern 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 nonnegative 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 2packing. 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 2packing 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 2packing 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 2packing 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 nonnegative 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 2packing 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 2packing graph are its dual. We can express the fractional domination linear program as: for nvectors 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 2packing 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 Mi + 1 ) 4 1 (the neighborhood of w1_N1+1 ) 4 1 (the neighborhood of wMi"LNJ+;) ;::: 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+wMi+lJ.+wi,NJ+l +wMi+l..NJ+l) = 1 W4 'J (c) w',_1 = w'i,NJ+l By symmetry in the definition of w',_1 and w'1_NJ+1 the two nodes are equaL (d) W = w' Lj Mi+ 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 2packing of PM x P, which Proof: Similarly, if we let v,,, be a maximum fractional 2packing of PM x PN, and define v in the same way as w and w' were defined, there is a maximal fractional 2packing of PM x which has 4fold symmetry, Le, Q.E.D, The weights on each individual node may not be the same for the fractional 2packing 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 2packing 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, ... N1 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 2packing. 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 2packing and a fractional domination of P1 x PN. Such a weight where the weights are both a fractional twopacking 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, ... N1 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 2packing. 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 2packing and a fractional domination of P1 x PN. Such a weight where the weights are both a fractional twopacking 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+1i 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(i1) 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 2packing. 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+ti 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 twopacking 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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(/21) cos 2 N3 2 page 29
PAGE 39
N5 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 aNt, i = I, N 1 7 + fi p(r' + rN+ti)fi qcos[( iN+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[( (i1)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[( iN+ 1 )8] 2 + q {cos[( (il)N+1 )8] +cos[( iN+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 = aNi 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 < N1, 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[( iN+1 )8]) + 1 7 2 7 + fi p(r'' + rN' lli11)fi q cos[( (i1)N+ 1 )8] 2 + l + fi p(r' + rN+ 1i) 7 fi q cos[( N+1 )8] i2 + 1 + fi p(r'cJ + rN+1Ii1) 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 + rNi+1 ) + q{cos((k+l)O) + cos((k1)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 aNI = bN I Q.E.D. Proof: By Theorem 1, a2 = aNI and b2 = bNI 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'+rN1)cos(w)2(r2+rN1)cos(w) + ( fi l)(r2+rN1)cos()( fi l)(r2+rN1)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 2packing, 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 + + aNt + 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 (N2) + 1 (N4) 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 2packing graph. For clarity, we will use the notation c1 and d1 where i = 1, 2 ... N as the nodes of the 2packing graph. We have found values sand t which can be used to calculated c1 and d1 for all i. A Type A 2packing 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 2packing 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[(iN+ 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+I2)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 2packed 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. = = NI Nl b) I;2c, + d, = 4" 1 L, L N(b) 7;o2 71"2 2 (N2) + 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 17 7 7 7 Substituting for values of b,. b1 and b,. we get 5N 16 4/22 2. N1 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() /22 and = 5n 16 46/2 ( 2 NJ) 46/it ( ) ++ s r +r cos w 7 49 7 7 + 44 r2 3 N 2 44 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/24 ++ 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 2packing 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 2packing 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 2packing, 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 61 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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 nonA. Let 3.(5 3/51 2 2 _____ _,_ __ 2 1 153 _V_J_ N3 2 N5 A.=B 2 4 Definition 3: Define the following values: 1 [ (3 2/5)cos( tj>) + ( 3/51 )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 = /51 2 Lemma 14: For all k and e, we have (trivial) cos[(kl)e] + cos[(k+l)O] = [53 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[(i1)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[((i1)N+l )e] + cos[(iN+ 1 )e] 2 2 2 + cos[((i+1)N+ 1 )lij(/5l) cos[(iN+l )Ill} 2 2 2 = 1 + p(r' + 1 + r)(r1 + r''+') + q Ieos( (k 1 )II) + cos( (k + 1 )II) ( /53 ) ( cos(kli)] 2 where k = iN+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+ (/51 ) q [cos[((i+1)N+l )0] 2 2 J5 1 ) q cos[((i1)(N+l) )OJ 2 2 (JS1 ) q cos[(i(N+1 ) )0](/51 ) q cos[((i+l) (N+l) )e] 2 2 2 2 (/53 ) q cosf(i(Nd) )OJ= 1 + (/5+1 ) p (r' + 1 + r)(r' + 2 2 2 (JS1 ) {q [cos((k1)0) + cos((k+1)0) + 2 N+l where k = i () 2 T'hen by Lemmas 9 and 10, we have the result. ( /53 ) 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 2packing, 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 aN1 + 4 b, + 4 bN1 + 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 )(N2) + 2( 2 )(N2) + 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 semiregular pattern of values of N which are nonType A. For example, N = 8 is a nonType 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 7774 pattern. We observed this 7774 pattern consistently for values of 4 < N < 1000. However, a second pattern, 77774, 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(N2)() +4() +2(N2)() =+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 2packing. 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing Fractional domination Figure 33 Proof that rr
PAGE 77
Theorems 1 and 2 show that there is a maximum fractional 2packing 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 2packing 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 2packing 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 4fold 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 2packing 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 2packing 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 2packing 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 2packing 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 2packing 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
2packing fractional 2packing 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 2packing 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 twopacking 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 2packing 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 2Packing Number of Complete Grid Graphs," Ars Combinatoria, 30 (1993) 261270. 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), 153172. 4. Hare. E. 0 .. "kWeight Domination and Fractional Domination of PM x PN," Congressus Numeratum, 78 (1990), 7180. 5. Hare, E. 0., "Fibonacci Numbers and Fractional Domination of PM x PN," manuscript, 1992. page 84
