
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00005731/00001
Material Information
 Title:
 Directed biclique covers and partitions of digraphs
 Creator:
 Hefner, Kim A. Sidwell
 Publication Date:
 1988
 Language:
 English
 Physical Description:
 100 leaves : illustrations ; 28 cm
Thesis/Dissertation Information
 Degree:
 Doctorate ( Doctor of Philosophy)
 Degree Grantor:
 University of Colorado Denver
 Degree Divisions:
 Department of Mathematical and Statistical Sciences, CU Denver
 Degree Disciplines:
 Mathematics
 Committee Chair:
 Lundgren, J. Richard
 Committee Members:
 Ryan, Jennifer M.
Subjects
 Subjects / Keywords:
 Directed graphs ( lcsh )
Directed graphs ( fast )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Bibliography:
 Includes bibliographical references (leaves 98100).
 General Note:
 Submitted in partial fulfillment of the requirements for the degree, Doctor of Philosophy, Department of Mathematics.
 Statement of Responsibility:
 by Kim A. Sidwell Hefner.
Record Information
 Source Institution:
 University of Colorado Denver Collections
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 19687617 ( OCLC )
ocm19687617
 Classification:
 LD1190.L622 1988d .H436 ( lcc )

Downloads 
This item has the following downloads:

Full Text 
DIRECTED BICLIQUE COVERS AND PARTITIONS
OF DIGRAPHS
by
Kim A. Sidwell Hefner
B.A., University of Colorado at Denver, 1983
M.S., University of Colorado at Denver, 1986
A dissertation submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Department of Mathematics
1988
This dissertation for the Doctorate of Philosophy degree by
Kim A. Sidwell Hefner
has been approved for the
Department of
Mathematics
by
Date
Z 2
Hefner, Kim A. Sidwell (Ph.D., Applied Mathematics)
Directed Biclique Covers and Partitions of Digraphs
Dissertation directed by Professor J. Richard Lundgren
The theory of directed biclique covers and
partitions is traced through the history of clique covers
and partitions into the current research areas. The
problem of finding a cover/partition of a digraph is
NPcomplete, so restrictions are made to narrow the range
of possible outcomes.
One such restriction limits the study to one type
of digraph. In particular, the complement of a cycle and
the complement of a path are examined. An algorithm for
generating their directed biclique covers and partitions
is discussed. This algorithm is then generalized to work
for an arbitrary digraph.
Another restriction involves requiring the
digraph to have no cycles. Bounds on the directed biclique
cover and partition numbers are found for these acyclic
digraphs. Also, general bounds for digraphs with cycles
are examined.
An mregular digraph has m incoming arcs and m
outgoing arcs. The minimum cover and partition numbers
for a 5regular digraph, bc(n,5) and bp(n,5), are
considered. This problem necessitates finding a 5regular
digraph on n vertices which has the minimum cover and
IV
partition numbers. The types of digraphs are only
restricted to being 5regular.
V
ACKNOWLEDGMENTS
Even though a dissertation advisor should help
the student think about problems, proofs, and life in
general, advisors also should receive credit. I have
been extremely fortunate in having Richard Lundgren as
my guiding light in mathematics. He has refused to allow
me to include him in all of the areas of my dissertation
where he has helped. Therefore, I must thank him now
(even before page one) for the patience, the intelligence,
and the belief in me which kept me going.
CONTENTS
TABLES........................... vi'ii
FIGURES ........................................ ix
CHAPTER
I. HISTORY .......................... . 1
Introduction .............................. 1
Clique Covers and Partitions of
Graphs .................................. 3
Biclique Covers and Partitions of
Bipartite Graphs ........................ 7
Directed Biclique Covers and Partitions
of Digraphs ............................ 12
Covers and Partitions of Regular
Digraphs ... 17
II. DIRECTED BICLIQUE COVERS AND PARTITIONS
OF THE COMPLEMENTS OF CYCLES AND PATHS
IN A DIGRAPH..................................... 23
Directed Biclique Covers . .......... 23
Directed Biclique Partitions ............. 45
III. DIRECTED BICLIQUE COVERS AND PARTITIONS .
OF ACYCLIC DIGRAPHS .......... 56
Introduction ............................. 56
Unilaterally Connected, Acyclic
Digraphs .............................. 57
Strictly Weakly Connected, Acyclic
Digraphs.............................. 59
Results for Digraphs with Cycles ... 66
vn
CHAPTER
IV. DIRECTED BICLIQUE COVERS AND PARTITIONS
OF kREGULAR DIGRAPHS ....................... 77
Partitions for (n,3) and Cn,n3) ... 78
Values where bc(n,k) = b~t)(n,k) .... 81
Cases where b"p(n,k) = rR(n,k) .... 84
Finding bc(n,k) and bp(n,k) ............... 85
BIBLIOGRAPHY ......................................... 98
V1 11
TABLES
T able
1. Values for ,cc(C ) and cc(Pn+1) for
n = 1, ., 28............... . . 7
2. Relationships between elements in digraphs,
graphs, and sets ............................. 30
3. Values for s(n), bc(D ), and bc(D*)
for n = 1 53...................
44
FIGURES
Figure
1. A bipartite graph and its adjacency
matrix ..................................... 9
2. Bicliques and their associated adjacency
matrices................ ..............10
3. A directed biclique .......................13
A. A digraph and its adjacency matrix .... 15
5. The adjacency matrix of Figure A and
its relationship to a bipartite graph . 16
6. An adjacency matrix of a digraph where
bc(2k,n2) = s(k) and bp(2k,n2) = k ... 18
7. An adjacency matrix of a digraph where
bc(n,2) = bp(n,2) for n odd ....... 21
8. A C 0 h) . 2 A
9. A(D*) ............................ 2 A
10. A(B2n) ........ ,. .......... 25
11. The bipartite graph associated with "Dn . 26
12.. A(B2n) ................................ . 31
13. The bipartite graph associated with "D* . . 31
1A. a. A directed biclique dn n vertices ... 55
b. A cycle on n1 vertices ................55
15. A strictly weakly connected acyclic
digraph where bc(D) = bp(D) =1 ........ 63
16. A strictly weakly connected acyclic
digraph where bc(D) = bp(D) = 2
6A
X
Figure
17. A strictly weakly connected acyclic
digraph where bc(D) = bp(D) = i ...........65
18. Strongly connected digraph where
bc(D) = bp CD) =2 .......................68
19. Strictly unilaterally connected digraph
where bc(D) = bp(D) =2 ................. 69
20. Strictly weakly connected digraph
where bc(D) = bp(D) = 2 ................70
21. Strictly unilaterally connected digraph
>
where bc(D) = bp(D) = n for
a. n even .... *........................71
b. n odd ............................... 71
22. Strictly weakly connected digraph
> j
where bc(D) = bp(D) = n for
a. neven .......................... . 73
b. n odd . ..............................7.3
23. Adjacency matrix of a strongly connected
digraph where bc(D) = top CD) =2 ........73
24. Adjacency matrix of a strictly
unilaterally connected digraph where
bc(D)=bp(D)=i .............................. 74
25. Adjacency matrix of a strictly weakly
connected digraph where
bc(D) = bp(D) = i ...........................75
26. Adjacency matrix of a digraph D e 0(11,5)
with bc(D) = 5.............................. 82
27. Adjacency matrix of a digraph D e 0(11,5)
where bp(D) = 6 82
28. An adjacency matrix whose digraph
DeD(8,5)hasbc(D)=bp(D)=5 ................... 87
29. An 8x8 5regular matrix
where C is a 4x4 88
XI
Figure
30. Partial construction of a matrix where
only two directed bicliques are needed to
cover the ones surrounding C (3 x 4) ... 89
31. An adjacency matrix whose digraph
D e D(9,5) has bc(D) = bp(D) =5.............91
32. Adjacency matrix where C is a 4x5
directed biclique ............ 92
33. A partial adjacency matrix where C is a
4x4 and two directed bicliques cover
the ones surrounding C ................93
34. A partial adjacency matrix where two
directed bicliques cover the ones
below C ...............................94
35. Partial adjacency matrix where C is a
3x5 and three directed bicliques
cover the ones below C.............. 95
]
CHAPTER I
HISTORY
Introduction
In the history of mathematics, graph theory can
be viewed as a relatively new branch. During the 1700s
the residents of Konigsberg, Germany, wanted to know if
it was possible to take a walk in their city, cross each
of their bridges exactly once, and return to the starting
point. Konigsberg had islands linked to each other and
the banks of the River Pregel by seven bridges. Euler,
a mathematician of that era, is credited with inventing
graph theory when he solved the Konigsberg Bridge problem.
He made each area of the city into a vertex of a graph.
The bridges were represented by edges from one vertex to
another. It then became the graphtheoretic question of
whether a circuit could be created beginning at a vertex,
and using each edge exactly once. The answer for Konigsberg
was that it could not be done, but a circuit which uses
the edges of a graph exactly once has come to be known as
an Eulerian circuit.
Since that time, graph theory has expanded in
both theory and application. One of the appealing aspects
of graph theory is that it can be applied to such areas
2
as biology, chemistry, engineering, operations research,
and music. A problem which can be broken down into
vertices and arcs or edges can be' solved using graph
theoretic techniques. Each new set of theorems in graph
theory extends the field of application and broadens the
number of problems which can be solved.
The theoretic motivation for studying biclique
covers and partitions of digraphs has its roots in the
studies of clique covers of graphs and biclique covers
of bipartite graphs. A graph G = (V,E) is defined to be a
set of vertices, V, and a set of edges, E _c_ V x V. A
bipartite graph B = [X,Y,E) has two disjoint sets of
vertices, X and Y, where each edge of E occurs only between
X and Y. A multigraph is a graph where more than one edge
is allowed between two vertices. For G = (V,E), any
subset of V which has an edge between every pair of
vertices in that subset is called a complete subgraph,
or clique. In a clique cover, any edge of G must be in
at least one clique. The smallest number of cliques
needed to cover the edges of a graph G is known as the
clique cover number of G, and is denoted cc(G). In a
clique partition, each edge of G must be in exactly one
clique. The clique partition number of G, cp(G), is the
minimum number of cliques needed to partition the edges
of G.
3
Similarly, biclique covers and partitions for a
bipartite graph B = (X,Y,E) can be defined. Any two
subsets of vertices, U
U is adjacent to every vertex in V and neither U nor V
is empty, is a complete bipartite subgraph, or biclique.
The minimum number of bicliques needed to cover/partition
the edges of B is the bicllque cover/partition number of
B, denoted bc(B) and bp(B).
After results were formed for the covers and
partitions of graphs and bipartite graphs, it was natural
to try to extend these results to directed graphs
(digraphs). Some of this research is presented in
sections 4 and 5 of this chapter.
Clique Covers and Partitions of, Graphs
In the past eleven years, surveys on the theory
of edge coverings and partitions liave been presented by
Orlin [l7], Pullman [19] and Roberts [20] In Orlins
paper, the clique partition number is called the content
of a graph, and the clique cover number is known as the
Rcontent of a graph.
A large portion of Chapter II depends upon the
following definition and theorems. These theorems tie
set theory into the bounding and computation of the clique
cover number of a graph G.
4
(1) Definition: Given a family of subsets S1,...,Sn,
the corresponding intersection graph G has vertices
vl,....,v such that the number of edges between v^
and v. is equal to Is^ n
(2) Theorem (SzpilrajnMarczewski [2l]): Let G be a
graph with possibly multiple edges and with vertices
1***vn*
Then there exists a set S and a family
of subsets S^,...,Sn of S such that s^ n S j  is
equal to the number of edges in G joining v. to v..
J
(3) Theorem [based o'.n the extension theorem by Szpilrajn
Marczewski [22]) : Let G be a graph with no multiple
edges and with vertices v^,.. ,vn. Then there exists
a set S and a family of subsets S1,...,Sn such that
S. n s. > 1 if and only if v. and v. are adjacent.
J J
In (2) and (3), the elements of S can be identified
with the cliques of the graph. To see this, let a be an
element of S. Suppose that Sal,Sa2,...,Sal<, are the subsets
which contain
With all of the other.subsets in this family. This implies
that all possible edges exist between vertices
val*va2* *'vaK* Therefore, these vertices form a
complete graph, or clique. If we look at (2), each edge
is going to be in one clique. This results from s. n S.
r J
being equal to the number of edges between v. and v..
^ J
Each of these edges is in a different clique. In [3),
the minimum number of elements in any S satisfying the
5
conditions of the theorem will be the clique cover number
of G. It is the minimum number of complete graphs which
cover the edges of G.
Why dont the subsets in (3) constitute a clique
partition of G? Consider the set {Sal>sa2*SaK> It
is possible that S and S A have another element, 3, in
common since s n S . >1. However, since G is not a
Otl 0(.J
multigraph, va^ and vaj have only one edge between them.
This results in the edge (vai>vaj) belonging to both the
clique a and the clique 3. Therefore, this cannot be a
partition. Further constraints which allow a clique
partition to be generated using sequences, of subsets will
be discussed in Chapter II.
This settheoretic approach was used by de Caen,
Gregory, and Pullman [5] to generate clique covers of
complements of paths and cycles in a graph. The complement
of a cycle, on n vertices, Cn, is a complete graph, Kn,
which has a simple ncycle removed. Thecomplement of a
path on n vertices, Fp, is a complete graph, Kn, which has
a simple path of length n1 removed.
Complements of paths are the intersection graphs
of consecutively disjoint subsets [f^,F2,..,F ]. A
sequence is consecutively disjoint if F^ n F^+^ = $ for
i = l,...,nl and all other subsets intersect. If we
remove a simple path of length n1 from a complete graph,
we can label the vertices so that the edges
6
(v1,v2), (v2,v3),...,(vn_1}vR) are the missing edges.
Therefore, the subsets representing these vertices must
be disjoint, and the result is a consecutively disjoint
sequence of subsets. Sequences of subsets were generated
for C4 through C^q ard P3 through P^.
Similarly, complements of cycles are the
intersection graphs of cyclically disjoint subsets
[frifr2 ,frnl ^ sequence is cyclically disjoint if
Fi n ^i+l = ^ fr ^ = n 1* and ^ n Fp = J2f and all
other sets intersect. When an ncycle is removed from a
complete graph, the vertices can be labeled so that
(v1,v2),(v2,v3),...,(vn_1,vn), (v1,vn) are the edges
which have been removed. So the subsets representing
these vertices must be cyclically disjoint, since the
edges and (vj,v ) do not exist.
A problem which confronts all researchers who use
the approach of generating sequences, of subsets is to
restrict the size of the subsets. This is a necessary
restriction asn becomes large, unless there is a computer
available which is dedicated only to the search for
sequences of subsets. If every size of subset must be
tried as every possible F^, even computers take a great
amount of time. In their paper, de Caen, Gregory, and
Pullman [5] conjeqtured that if the minimum number of
elements needed to cover P was k = 2r+l, then all subsets
7
except the first and last must be of size r. This was
based on work done by Meredith and Lloyd [l6].
The exact values for ccCPp+1) and cc(C"n) are given
in Table 1, as calculated by de Caen, Gregory, and Pullman.
Table 1
Values for cc(Cn) and cc(Pn+1)
for n = 1,...,28
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 . . 28
cc(Cn) 0 2 5 5 7 6 7 6 8 7 7 7 8 7 8 7 8 . . 8
cc(p'n + l> 0 1 3 a 5 5 6 6 6 6 7 7 7 7 7 7 7 7 8 . . 8
Source: D. de Caen, 0. A. Gregory, and N. J. Pullman, Clique coverings
of complements of paths and cycles, Ann, of Discrete Math., 27 (1985), p. 260.
Siclique Covers and Partitions
of Bipartite Graphs
The early work in clique covers and partitions
of graphs naturally gravitated to the study of biclique
covers and partitions of graphs. Several authors,
including Or 1 in [17] Gregory and Pullman [ll] Tuza'[23] ,
and Graham and Pollack [9] have considered this problem.
Biclique covers and partitions of bipartite graphs
play an important role in finding the directed biclique
cover and partition numbers of a digraph. The relationship
between the biclique cover number of both bipartite graphs
8
and digraphs and the Boolean rank of (0,1)matrices is
given by de Caen, Gregory, and Pullman [4]. If A is an
m x n (0,1)matrix its Boolean rank, rQCA), is the least
k for which there exist m x k and k x n CO, 1)matrices B
and C such that A = BC (where the arithmetic underlying
the matrix multiplication is Boolean, that is, it is tire
usual integer arithmetic, except 1+1 =1). An equivalent
definition for rQ(A) is the minimum number of
(0,1)matrices of rank one whose Boolean sum is A. If
B = (X,Y,E) is a bipartite graph, X = {x1,x2,..,xm> and
Y = {y1,y2yn} the adjacency matrix of B, A(B), is
defined as follows:
Definition: Let the rows of A(B) be labeled x1,x2,...,xm
and the columns of A(B) be labeled y^,y2> >Yn Then
fO if (v,Vj) is not an edge of B
.
1 if (v^,Vjj is an edge of B.
A(B) is an m x n (O', 1)matrix and bc(B) = r&(A(B)) [4].
Orlin [17] additionally proves that finding r^(A) is an
NPcomplete problem. Other results on the Boolean rank
of (0,1)matrices have been published by Kim [l4] .
Following is an example which illustrates bc(B) = rn(A(B)).
D
In Figure 1, a bipartite graph B = (X,Y,E) is shown with
its adjacency matrix, A(B). A possible biclique cover for
B is:
9
Bx = {(1,2),Cl,A),(3,2),(3,4)},
B2 = {(3,6), (5,6)},
B3 = {(1,4),(1,8),(7,A),(7,8)}.
X Y
A(B)
2 4 6 00
1 1 \ 1 0 1
3 1 1 1 0
5 0 0 1 0
7 0 1 0 1
Figure 1. A bipartite graph and its adjacency matrix.
Another way to express these bicliques, rather than listing
all of the edges in each, is:
= {1,3} > {2,4},
B2 = {3,5} {6},
B3 = {1,7} {4,8}.
This is possible since every vertex.in the first group
of each biclique is adjacent to every vertex in the second
group. Every biclique in B corresponds to a submatrix
of ones in A(B) often referred to as a block of ones.
10
Figure 2 shows the blocks of A(B) associated with each
of the bicliques. Notice that edge (1,4) is in both
and Bj, so these bicliques do not represent a partition.
1
B
2 1 2 1 4 1
4 A(B,) = 3 1 1
6
3 _ 5 o ^>=o 6 a(b2) = 3 5 1 1_
4 8
1 1 1
^ ;> A(B3) = 7 1 1
Figure 2. Bicliques and their associated
adjacency matrices.
Since, in Boolean arithmetic, 1 + 1 = 1, we see
that A(B) is the sum of three m x n rank one matrices
which correspond to each one of the bicliques:
11
A(B)
1 1 0 0 0 0 0 0
1 1 0 0 + 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 1 0 1
0 0 0 0
0 0 0 0
0 1 0 1
The only place we need to add 2 ones together is where
an edge is in more than one biclique. This also illustrates
why the Boolean rank of A(B) is equal to the biclique
cover number of B.
Analogous to the biclique cover problem is the
biclique partition number of a bipartite graph. This
number is related to the nonnegative integer rank of A(B),
r^+ (A(B)). If A is an m x n (0,1)matrix, its nonnegative
integer rank, r^+ (A), is the least k for which there
exist m x k and k x n matrices F and G over Z+ providing
the factorization A = FG. Results regarding bp(B) =
r^+ (A(B)) have been found by Gregory, Jones, Lundgren,
and Pullman [lo] .
The covering obtained for the bipartite graph B
in Figure 1 will not work as a partition. It will actually
take four bicliques to partition the edges of B. These
four bicliques can be constructed as follows:
12
(1) Bi = {ls in column
m Bi = {ls in row i};
O) Bi = {1,3} {2,4},
B2 = {3,5} {6},
B3 = {7}  {A},
8 4 = {1,7} {8}.
There are other possibilities, but none of them use fewer
than four bicliques. Any partition forms a cover for a
graph, even though the converse is not true. Therefore,
bc(B) < bp(B). Using the relationships to Boolean rank
and nonnegative integer rank r^( A(B)) Â£ rz+ C ACBj ) follows
directly.
Bipartite graphs prove to be the bridge when
solving the cover/partition problems for digraphs and the
analogous problems for graphs. This relationship will
be examined in the following section, then further in
Chapter II.
Directed Biclique Covers and
Partitions of Digraphs
The term "directed biclique" has gone through a
number of semantic changes as the years have progressed.
In the beginning, Lundgren and Maybee [l5] referred to
these new structures as cliques. This tied the idea into
that of clique covers of graphs. However, the directed
biclique is more like the biclique of a graph rather than
a clique. It is a complete directed bipartite subdigraph,
13
where all arcs are oriented from the vertices in X to the
vertices in Y. This is shown in Figure 3. Thus, the
term "biclique" was borrowed to also refer to the directed
bicliques. Generally, when speaking of graphs, bicliques
are taken to be undirected. If digraphs are the topic,
bicliques are directed. To avoid any possible confusion,
this paper will always refer to a biclique of a digraph as
a directed biclique. Unfortunately, be and bp are used
as the biclique cover and partition numbers for both
graphs and digraphs in most papers. Recently, however,
Gregory, Jones, Lundgren, and Pullman [lo] introduced the
notation Idc and bp to denote directed biclique cover and
partition numbers. That notation will be adopted here.
Figure 3. A directed biclique.
Actually, the journey of the terminology for
directed bicliques follows the path that the research has
taken: from cliques to bicliques to directed bicliques.
The question of what bc(D) and bp(D) are for any digraph D
is a large problem. Therefore, certain types of digraphs
have been isolated, for study. For a tournament on n
14
vertices, Tn, Lundgren and Maybee .[15] found that
be (Tn) = b^p C Tn D = n1.
Let s(n) be defined by:
s(n) = min{k: n <_ ( Lk/2_P
where LxJ is the greatest integer less than or equal to
x. The number s(n) was found to be the directed biclique
cover number of the complete digraph on n vertices, DKn,
by de Caen, Gregory, and Pullman [4]. Pritikin [l&] used
a technique due to Tverberg [24] to show that ttp(DKn) = n.
Results related to the complements of cycles and paths in
a digraph [l] will be discussed in depth in Chapter II.
The biclique cover and partition numbers for regular
digraphs will be examined both in the next section and
in Chapter IV.
An important relationship is that of Etc to be and
bp to bp. Consider the digraph D and its adjacency matrix
A(D) shown in Figure 4. The rows and columns of A(D) are
both labeled with the vertices of D.
Jo if (v^,v.) is not an arc of D
a. = n *'
jj. if (v^,Vj) is an arc of D,
where (v.,Vj) means that the arc is oriented from v^
toward v.. Each one in the matrix A(D) represents one arc
of D. This is similar to the adjacency matrix,
A(B), of a bipartite graph B, since each edge
15
1
A CD)
1 2 3 4 5
1 0 1 0 0 1
2 1 0 1 0 1
3 1 0 0 1 1
4 0 0 0 0 0
5 0 0 0 1 0
Figure 4. A digraph and its adjacency matrix.
corresponds to a one in A(B). A block of ones in A(D),
say {(2, l),(2,5),(3,1),(3,5)}, forms a directed biclique
in D. As a matter of fact, we can relabel the rows and
columns in such a way (see Figure 5) that A(D) becomes
the adjacency matrix of a bipartite graph. Since the
matrix itself remains the same and each biclique of B is
represented by a block of ones, finding bc(B) and bp(B)
are the same problems as finding bc(D) and fctp(D). This
is because we.can express each problem in terms of the
adjacency matrix: What are the fewest number of blocks
of ones needed to cover/partition the ones of A(D) (or
A(B))? Hence, it can be seen that bc(B) = bc(D) and
16
A(B)
2 4 6 8 1G
1 0 1 0 0 1
3 1 0 1 0 1
5 1 0 0 1 1
7 0 0 0 0 0
9 0 0 0 1 0
X Y
1 2
3 4
B = 5 6
7 0 'x\2s> 8
9 10
Figure 5. The adjacency matrix of Figure 4 and
its relationship to a bipartite graph.
b.p'(B) = bp(D) since the minimum number of blocks of ones
is the same in both cases.
The difference between covers and partitions,
when looking at blocks of ones in a matrix, still relates
back to the definitions of both. In a cover, an edge or
arc can be in more than one biclique. This means that
ones in the adjacency matrix may be in more than one
block. Since this is not allowed in a partition, each
one will be found in only one block of a biclique partition.
17
Covers and Partitions of Regular Digraphs
One way of narrowing the field for finding bc(D)
and bp(D) is to restrict D to being a kregular digraph.
If every vertex v of D has indegree k and outdegree k,
denoted id(v) and od(v), respectively, then D is a
kregular digraph. The adjacency matrix A(D) of a
kregular digraph has k ones in each row and k ones in
each column. If a specific value for k is fixed, a digraph
can be found which gives the minimum cover and partition
numbers for kregular digraphs.
A similar problem was first investigated for
kregular graphs. A graph is kregular if every vertex
has degree equal to k. Pullman and de.Caen have results
in clique coverings of regular graphs [7] and in clique
partitions of regular graphs [6].
The earliest results for kregular digraphs came
from Jones, Lundgren, and Maybee [l3]. Let D(n,m) be the
set of digraphs on n vertices which are mregular.
Important theorems for the set of all mregular digraphs
on n vertices in this paper include:
(1) Theorem: Let q > 2 be an arbitrary integer.
(a) If q > 3, for each m >_ 2, there exists an element
D e D(qm,2m) such that bp(D) = q.
(b) If q = 2, for each m >_2, there exists an element
D e D(2m,m) such that bp(D) = 2.
18
(2) Theorem: If bp(n,m) = min bp(D) for D e D(n,m) and
n = qm, then bp(n,m) = q.
(3) Theorem: If bp(n,m) e min lop CD) for D e D(n,m) and
n = 2q+'l, then b"p(n,2) = q+2.
A later paper by Barefoot, Jones, Lundgren, and
Maybee [2] further extended the theory of. kregular
digraphs. This paper concentrated on (n2)regular
digraphs on n points. The following results were given:
(1) bc(2k,n2) = s(k).
(2) bp(2k,n2) = k.
(3) If n = 2k+l >_ 9, then s(k+2) _< bc(n,n2) < s(kl)+2.
C4) bp(2k+l,n2) = k+2.
The adjacency matrix which corresponds to Cl) and [2)
above is in Figure 6. Each two rows or two columns of
A(D) can be taken as a directed biclique in a partition of
D. Since rB(A(D)) = rB(Ik) = s(k) [ll] Cwhere Tk is the
complement of the identity matrix), then bc(D) = s(k).
A(D)
00
00
00
00
ls
00
00
Figure 6. An adjacency matrix of a digraph where
bc(2k,n2) = s(k) and bp(2k,n2) = k.
19
Still more recently, bc(n,k) and bp(n,k) were
solved for k < 4 by Gregory et al. [lo] The results found
in this paper are analogous to those found by Brualdi,
Manber, and Ross [3] while investigating the minimum real
rank of square binary kregular matrices. Barefoot et
al. [2] found the following bounds for bc(n,k) and bp(n,k):
< bc(n,k) Â£ bp(n,k) _< k
The following lemma gives exact values for D(n,l) and
D (n 2) :
Lemma: For all n Â£ 1, bp(n,l) = bc(n,l) = n and for all
n Â£ 2, bp(n,2) = bc(n,2) = L^J + 1 + (l)n+1.
Consider A(D) for D in D(n,l); it is easy to see
why it will take n blocks to cover all of the ones. In
A(D), each row and each column have a single one, so the
largest block is a lxl. Since there are n ones, it
will take n blocks and any cover must be a partition. To
understand the results for D(n,2), first consider n an
even integer. The adjacency matrix of the digraph which
gives the minimum cover and partition numbers would then
be the complement of the matrix given in Figure 6 (i.e.,
the ones would become zeros, and the zeros would become
ones), so there will be 2x2 blocks of ones. Since n
is even, (l)n + 1 is negative and bp = be = j, making each
2D
of the 2x2 blocks a directed biclique in both a cover
and partition.
But what if n is odd? According to the lemma,
L^J+2 directed bicliques would be needed. Let n = 2q+l,
then L^J = q. As shown in Figure 7, the first 2(ql) rows
and columns will, contain q1 2x2 blocks of ones. The
remaining three rows and columns must be 2regular. Since
bc(3,2) = bpC.3,2) = 3, it will take q1+3 = L^J+2 directed
bicliques to cover or partition a digraph of D(2q+1,2).
The following theorem gives exact values for
y
bc(n,3) and bp(n,3) :
Theorem: Let s(n) = 0 if n = 0 (mod 3) and s(n) = 3
otherwise. Then for all n >_ 3
bc(n,3) = bp(n,3) = L^J + s(n).
The proof of this theorem involves constructing
a minimal example, then showing it is optimal. This
construction, as well as those for D(n,l) and D(n,2),
makes use of D an m x m submatrix of all ones. For
m, m
m <_ 4, construction of adjacency matrices which achieve
the minimum values of bc(n,m) and bp(n,m) for their
associated digraphs use as many replicas of Jm m as
possible. In the above theorem, if n = 0 (mod 3), say
n = 3q, then q replicas of can be placed down the
diagonal so that they do not intersect in any column or
row. Thus, there will be q = ^ directed bicliques. For n
21
1 1
1 1
1 1
1 1
Os
1 1
1 1
Os
0 I1 1
1 0 1
1 1 0
Figure 7. An adjacency matrix of a digraph where
bc(n,2) = bp(n, 2) for n odd.
not congruent to 0 mod 3, qI ^s can be used.. This
leaves either a DK.^ or an element of D(5,3) in the last
four or five rows and columns, respectively,. Both have
be = bp = 4.
The results for D(n,4) are obtained similarly:
Let s(n) = 0, 3, 2, or 4, according as n = 0, 1, 2, or 3
(mod 4). Then for all n > 5 ,
Theorems
tfc (n, 4) = tp C n, 4) = + s(n),
be(5,4) = 4, and bp(5,4) = 5.
The constructions for these digraphs are analogous to
those used in the previous theorem. The major problem
22
with this approach is that a casebycase study must be
made regarding the size of possible blocks of ones, in
order to show that the construction using Jm m actually
achieves a minimum value for bc(n,m) and bp(n,m). As m
gets larger, the cases get even more tedious,, and keeping
track of all possibilities becomes an insurmountable task.
There will be more discussion of this problem in Chapter IV.
CHAPTER II
DIRECTED BICLIQUE COVERS AND PARTITIONS
OF THE COMPLEMENTS OF CYCLES
AND PATHS IN A DIGRAPH
Directed Biclique Covers
A natural extension of the work done by de Caen,
Gregory, and Pullman [5] was to consider the covers and
partitions of complements of cycles and paths in a digraph.
The results for directed biclique covers have been
published by Barefoot, Hefner, Oones, and Lundgren [l] .
All work shown here that is not credited to a coauthor
has been done solely by Kim A. S. Hefner.
Let Dn be a complete digraph on n vertices minus
the arcs of an ncycle, and A(Dn) be the adjacency matrix
associated with D D can be labeled so that A(D ) is
n n n
an n x n (0,l)matrix with zeros on the diagonal,
superdiagonal, and at.an ^ (see Figure 8). We then define
D* to be a complete digraph on n vertices minus the arcs
of an npath, with A(D*) as its adjacency matrix. D* can
be labeled so that A(D*) is an n x n (0,l)matrix with
zeros on the diagonal and the superdiagonal (see Figure 9).
It is often easiest to find blocks of ones in the adjacency
matrix rather than the directed bicliques in a digraph.
24
A matrix is less congested, and can be entered into a
computer to obtain empirical results.
0 0 1 1 1 1 1
1 0 0 1 1 1 1
1 1 0 0 1 1 1
A(Dn) = .
1 1 1 1 1 ... 0 0
01 1 1 1... 1 0
Figure 8. A(Dn).
ACD*)
0 . 0 1 1 1 1 1
1 0 0 1 1 1 1
1 1 0 0 1 1 1
1 1 1 11 ... 0 0
1 1 1 1 1 ... 10
Figure 9. A(D*).
A general directed biclique covering is not
difficult to find. However, finding the minimal covering
is somewhat elusive. This makes it desirable to fit the
digraph problem into a form where it is possible to use
the existing theorems relating to clique coverings of
graphs.
25
First, we will examine the process relating Dn
to the complement of a cycle in a graph, U2 Consider
A(Dp) without the labeling acquired from Dn In this
form, it can be seen as an adjacency matrix for a bipartite
graph B on 2n vertices, as shown in Chapter I, section 3.
A(B2n) can be relabeled so that X = {1 ,3,...,2nl} and
< (N II > ,2n} . This labeling results in the following
matrix: 2n 2 4 2n2
1 ~ 0 0 1
3 1 0 0 ls
5 1 1 0 0 \
A(B2n) =
1 s
0
2nl 0 1 1 ... 1 0
Figure 10. A(B2n).
The choice of labeling the columns beginning with 2n is
arbitrary. However, this labeling provides a cycle where
(vl,v2n) does not exist in B2r. Dn has no loops (i.e.,
(Vi,Vi) is not an arc) so there are zeros down the diagonal.
The other zeros result from the removal of a cycle. The
corresponding cycle which is removed from B2n with the
given labeling is shown in Figure 11. The cycle is:
1,(1,2),2,(2,3),3,(3,4),...,(2n1,2n),2n,(2n,l),1.
26
X
2
4
6
2n
Figure 11. The bipartite graph associated with Dn.
Each edge in B2n corresponds to an arc in Dn. Therefore,
complete bipartite subgraphs (bicliques) in B2n correspond
to directed bicliques in Dn Thus, a biclique covering
for B2n is a directed biclique covering for Dn, so
bc(Dn) = bc(B2n). However, B2n is not the complement of
a cycle in a graph, so we cannot use the methods employed
by de Caen, Gregory, and Pullman [5] to generate a clique
covering for the complement of a cycle. This can be
restricted by adding all of the edges in X and Y so that X
and Y are complete subgraphs of a new graph B*n. B2n has
the following properties:
U S2n = C2n
2. c.c(C2n) < bc(B2n)+2 = bc(Dn)+2.
Property 2 was first observed by Gregory and Pullman
(personal communications). It follows from examining the
values of bc(Dn) obtained from the constructions of minimum
clique coverings of C2n. The three possibilities are
listed below.
27
1. If there exists a minimum cardinality cover of C2n
with two cliques of the form = {xm: 0 < m <_ n,
xm e X} and Cj = {ym: 0 Â£ m Â£ n, ym e Y}, then
bc(Dn) = cc(C2n)2.
2. If there exists a minimum cardinality cover of U2
with one clique of the form = {xm: 0 < m < n, xm e X}
or Cj = {ym: 0 < m < n, ym e Y} and no minimum
cardinality cover as in (1), then bc(Dn) = cc(C2n)l.
3. If there are no cliques in any minimum cardinality
cover of "C2n such as and Cj defined above, then
be(D n) = cc(C2n).
With the digraph problem expressed graph theoretically,
use can be made of the following theorem. De Caen,
Gregory, and Pullman [5] have expressed it in its current
form, and its roots go back to Erdos, Goodman, and Posa
[8] as well as SzpilrajnMarczewski [21,22].
Theorem: G is the intersection graph of a sequence T of
subsets of a kset if and only if G has a clique covering
with k or fewer members.
This theorem allows us to find the clique covering
number of "c2n by generating all 2nsequences of subsets
using the smallest kset possible. The problem of
generating these sequences is NPcomplete. In addition,
since the relationship between bc(Dn) and cc(C2n) depends
upon the nature of a minimal cardinality cover, we must
28
examine every 2nsequence generated for a fixed n in order
to ascertain the directed biclique covering number. This
is due to the possibility that the clique covering of C2n
may be obtained in all or some of the ways listed on the
previous page. If only one sequence is examined, it is
unknown whether another sequence exists which generates
a covering of B2n using a fewer number of bicliques.
Therefore, to obtain an exact value for bc(D ),
a method is needed which will eliminate all but one of
the possibilities when a single sequence is generated.
To achieve this, let C be a clique covering of C2n where
the Ci e C have the following restrictions:
1. For some a, Ca = {x.: for 0 < i < n, e X}; and
2. For some B, C6 = {ylS for 0 _< i < n, yi e V}.
With these restrictions, the other cliques form the
biclique covering of B2 Thus, the corresponding directed
bicliques cover D We now define cc(G) = k to be the
minimum k for which there exists a clique cover of
cardinality k containing C and C. This leads to the
ot p
following theorem.
Theorem 2.1.1: bc(Dn) = cc(C2n)2.
Proof: B2n can be covered with c/c('C2n)2 bicliques by
not using and C^, so bc.(Dn) Â£ cc[C2n)2. Now, there
are three possibilities: (i) bc[Dn) = cc(C2n); or
(ii) bc(Dn) = cc(C2n)l; or (iii) bc(Dn) = cc(C2n)2.
29
Case i; bc(Dn) = cc[C2n), so neither Ca nor C^
exists in a minimum cover of C^n* c^^2n^ cc^2n^+2 =
bc(Dn)+2, so cc(C2n)2 < bc(Dn).
Case ii: bc(Dn) = cc(C2n)l, so either Ca or Cg
exists in a minimum cover of ^2n* cc(C2n) < ccCc2n)+l =
bc(Dn)+2, so cc(C2n)2 < bc(Dn).
Case iii: bc(Dn)'= ccCc2n)2, so both Ca and Cg
exist in a minimum cover of U2r). cc((J2n) < ccCC2n) =
bc(On)+2, so cc(C2n) < bc(Dn)+2.
Therefore, bc(Dn) = ccCc2n)2. []
To form a sequence of length 2n for which "C2n is
the intersection graph, let be subsets of a set T for
i = 1,...,2n. Since complements of cycles are intersection
graphs of cyclically disjoint sets (see Chapter I,
Section 2), we want [f^ F2 ] to be cyclically disjoint.
Table 2 shows the relationships between elements in the
digraph, the graph, and the sequence of subsets.
In a construction similar to that of Dn, bc(D*)
can be obtained from a 2nsequence on a kset. A relabeling
of A(D*) is possible (see Figure 12) so that the matrix
represents a bipartite graph B2n on 2n vertices. Again,
the labeling of the rows and columns is chosen so that
the zeros represent a path which is easy to identify (see
Figure 13). By completing subgraphs X and Y, as for B2 ,
we obtain a graph which is the complement of a path on
30
Table 2
Relationships Between Elements in
Digraphs, Graphs, and Sets
Digraph (Dn) Graph (C2n) Set (2nsequence)
1. F2i, l
2* F2i1 l
3. k bc(Dn)=k2. cc(C2n)=k For xeF^, xe{1, ,k}.
Ga Not a directed biclique in V The clique . aeF2i_i> for l
5. Not a directed biclique in Dn * The clique . 3eF2i for 1<_iÂ£n.
6. C., l
31
ACB2V
2n 2n2 4 2
2nl 0 0 1
i c CM 1 0 0 1 1 ls
s
.
1 s
3 1 0
1 1 1
L
Figure 12. A(B2n).
X Y
1 2
*
* i
2nl o=o 2n
Figure 13. The bipartite graph associated with D*.
2n vertices, P2n* T^e ^0llwin9 theorem is a direct
result from Theorem 2.1.1 and its proof.
Theorem 2.1.2: bc(D*) = cc(P2n)2.
To obtain cc(P2r)), a 2nsequence of subsets on a
kset must be found such that P2n is the intersection
graph of that sequence. Since F2n is the intersection
32
graph of a consecutively disjoint sequence, we want
The actual construction of these biclique
coverings by generating 2nsequences will be examined
after the theoretical results, where exact values of
bc(Dn) and bc(D*) are presented for some n.
All graphs C2n and P2r which have been constructed
from A(Dn) and A(D*), respectively, have an even number
of vertices. As a result, the theorems obtained by
de Caen, Gregory, and Pullman [5] need to be modified to
use with an even number of vertices and to account for
using cc rather than cc. The next theorem is a modification
of their Theorem 3.1. Most of these results can be proven
directly using biclique covers of the digraphs; but for
the most part, the following proofs are much more compact.
They take a given cyclically or consecutively disjoint
2n sequence. By using new elements augmented by the
existing subsets* longer sequences are constructed which
are cyclically or consecutively disjoint as needed. The
proofs used in [5] have served as an inspiration and
sometimes a template for the proofs in Theorems 2.1.3 and
2.1.6. The use of cc in proofs results in an element a
in every odd subset and an element 3 / a in all even
subsets of a 2nsequence. Thus, Ca is the complete graph
using all vertices in X, and is the complete graph
using all vertices in Y. All other bicliques cover B2n>
consecutively disjoint.
33
Theorem 2.1.3: The following statements are true for n Â£ 1:
1. cc(P2n) Â£. cc^2n+2^5
2. ccC^2n+2^ cc(P2n) + 1 n ^ 2>
3. c"c^2n+2) Â£ ce(P2n)+2, n > 2;
4. cc(C4n) < c/c(P2n+2)+2;
5. cc(C4n+2) Â£ cc(P2n+2)+2.
Proof: To prove 1, since P2n is an induced subgraph of
P2n+2 on 2n vertices, it follows that, at most, the cover
fr ^2n+2 also cover "P^. Thus, cc("P2n) Â£ ccCP2n+2) *
To prove 2, let [f.^, ,F2n] be a consecutively
disjoint 2nsequence of subsets of a set T of k =.cc(P2 )
elements where a,b e T and a e F2^ b c F2^ for 1 < i < n,
Let x T, then j^F2U1 x} ,F^ F 2, F^ b ^ i > F 4, F ^ f20 3*
F2n2U*x^,F2nl,F2n,F2nlU*x^ is a consecutively
disjoint 2n+2sequence on a k+lset, where b e F^
a e F2. for 1 Â£ i < n+1. If n = 2, these subsets do not
represent a cover of P^ because cc(Pg).= cc(P4)+2. So,
cc(P2n+2^ 1 cc(P2n3+l for n / 2.
To prove 3, let [f^,...,F2 ] be a consecutively
disjoint 2nsequence of subsets on a set T of k = cc(P2n)
elements where a,b e T and a e F2^ b e F2^ for 1 Â£ i Â£ n.
For n > 2 and x,yjf T, then [f1,F2U{y},F3U{x},F4U{y},...,
F2nlU^x^ ,F2n^{b)U{x}J Â£s a cyclically disjoint
2n+2sequence on a k+2set where a e F2i 1 and b e F2i
for 1 Â£ i Â£ n+1. Thus, cc(C2n+2) Â£ cc(P2n)+2.
34
To prove 4, let [f^,...*F2n+2] be a consecutively
disjoint 2n+2sequence of subsets on a set T of k =
A ^
cc^P2n+2^ elements where a,b e T and a e f^il ^ e ^ 2i
for 1 Â£ i Â£ n+1. For n Â£ 1 and x,y Â£ T, then [F2,F3U{y},
t^U{x} .. F2n+i^^y^ ^2n+2 p2n+lb^x^ ^"4^^ ^ > F'^UCxj^]
is a cyclically disjoint 4nsequence on a k+2set where
b e F2. a e F2^ for 1 Â£ i Â£ 2n. Therefore, ecCc^n) <
cc(P2n+2)+2*
To prove 5, let [f^ F2n+2] be a consecutively
disjoint 2n+2sequence of subsets on a set T of k =
A __
cc^P2n+2^ elements where a,b e T and a e f^il ^ e F2i
for 1 Â£ i Â£ n + 1. For n Â£ 1 and x,y Â£ T, then
[F1,F2U{x},F3U{y},...,F2nU{x},F2n+1U{y>,F2n+2,F2n+1U{x},
...,F2U{y}] is a cyclically disjoint 4n+2sequence on a
k+2set where a e ^211 b e p2i ^or ^ ^ 2n+l. So,
cc^4n+2^ c^P2n+2^+2, D
The ultimate quest is what these results imply
for the digraphs Dn and D*. Because of the equality in
Theorems 2.1.1 and 2.1.2, the following corollary is a
direct consequence of the previous theorem.
Corollary 2.1.4: The following statements are true for
n _> .1:
1. be CD*) < bctD*+1)!,
2. bt(D*+1 ) Â£ bc(D*)+l, n / 2;
3. bcCDn+1) Â£ be(D*)+2, n > 2;
35
4. bcCD2n3 < bc(D*+1)+2}
5. be(D2n+1) < b^c(D*+1D+2.
The first two results give monotonicity for
bc(D.*), with the difference in the values being at most
one. This has led to a conjecture that bc(Dn) < tTc(Dn+1).
Considerable computational results supporting this
conjecture will be presented later in this section, but
as of yet, no one has been able to prove it.
The following lemma gives an additional restriction
on the construction of a cyclically disjoint sequence.
Lemma 2.1.5: If C2n is the intersection graph of a
cyclically disjoint 2nsequence [f^ ,... F2n] then F'^Fj.
for any i,j = l,...,2n, i Â£ j, and n 3.
Proof; Let "C2n be the complement of a cycle on 2n vertices
and [f1,...,F2n] be a cyclically disjoint 2nsequence on
a set T of k = cc'Cc^) elements. Consider two subsets F.
and F. of the sequence which represent vertices i and j,
respectively, in U2n* If n ^ 3, there exist at least two
edges (i,x) and (j,y) in "C2n such that (i,y) and (j,x)
are not in C^. So> and Cj*yD must be covered in
cliques C^ and C^, respectively, where f,g e T and f / g.
Thus, f e F. while f i F., and g e F. but g i F. Therefore,
J J
F^ / F. for any i,j = l,...,2n, i / j, and n :> 3. []
36
The above lemma does not apply to consecutively
disjoint sequences. In "P2 vertices 1 and 2n have n1
edges each, while the other vertices have n2 edges each.
This results in vertex 1 being adjacent to all of the
vertices vertex 3 is adjacent to, plus the additional
vertex 4. The same can be said about vertices 2n and
2n2. Therefore, it is possible that FjC F^ and fr2n2cfr2n
Results which help bound cc(P2n) and ccC^n^ are
found in the following theorem.
Theorem 2.1.6: The following statements are true for n > 1:
1. cc ^P2n+2 ^+2
2. cc(P2n) < cc(C2n) n / 2;
3. ccCt2n) < cc(P2n^+15
4. cciC^) < cc(C2n+2)+2;
5. Cc(^4n+2'1 < cc(C2n+2)+2, n > 2;
6. c"c(C2n) < CG(U2n+2)+15
7. CC(C2n+2^ < cc(C2n)+2, n / 2;
8. cc^4n+2) < cc(P2n+2>2.
Proof: To prove 1, let [f^,...,+2] a consecutively
disjoint 2n+2sequence of subsets on a set T of k =
cc (P
2n+2
) elements where a,b e T and a e F
2il
, b e F2i
for 1 <_ i <_ n+1. For n >_ 1 and x,y i T, then
[Fi,F2U{x},F3U{y},. ..,F2nU{x},F2n+iu{y} F2n+2 F2n+lU'*x^
, F,U{y}] is a consecutively disjoint 4nsequence on
37
a k+2set where a e ^il b e ^ 2i For ^n Thus,
cc(p4n^ cc^P2n+2^+2'
To prove 2, let [f^,...,F2n] be a cyclically
disjoint 2nsequence of subsets on a set T of k = cc(C2n)
elements where a,b e T and a e F^ b e F2^ for 1 <_ i _< n.
By Lemma 2.1.5, there exists an x e T such that x e F^
and x Â£ p2nl For n 3 So F2n1 ,p2nU*x^ is a
consecutively disjoint 2nsequence on a kset where
a Â£ ^21 1 b e F2^ for 1 < i < n when n ^ 3. When n = 1,
there are no edges between X and Y in and P2p, so
cc(P2n) = cc(C2n) = 2. Therefore, cc(P2n) <_ cc(C2n) for
n / 2.
To prove 3, let [f^ ,...., F2p] be a consecutively
disjoint 2nsequence of subsets on a set T of k = ce(P2n)
elements where a,b e T and a e F2^ j_, b e F2^ for 1 <_ i _< n.
P1 n p2n = {i > ap > = z fr some p. Since b e F2n and
b Â£ F^, then F2n~Z / So, for n 1 and x Â£ T, then
[/1,P2,P3^X^ >P4P5**^x^ ,P2nl ^p2pz)b{x}] a
cyclically disjoint 2nsequence on a k+lset where
a e b e F2i por 1 n* So c~c^2n^ cct^n^41*
To prove 4, we use Theorems 2.1.3(4) and 2.1.6(2)
to obtain cc(C4n) <_ cc(P2n+2)+2 1 c~c^2n+2^+2 for n >
Similarly in 5, Theorems 2.1.3(5) and 2.1.6(2)
give cc(C4n+2)'< cc(P2n+2)+2 < cc(C2n+2)+2 for n > 2.
38
For 6, Theorems 2.1.6(3), 2.1.3(1), and 2.1.6(2)
give cfc(C2n) 1 cc(P2n) + l < cc(P2n+2)+l < cc(C2n+2) + l for
n _> 1.
To prove 7, we use Theorems 2.1.3(3) and 2.1.6(2)
to obtain cc(cL,n+2) c~c^2n^+2 c^C2n^+2 ^or n ^
For n = 1, ccCc^) = cc((:2) = 0; but when n = 2, ccCc^) = 3 =
ccCc4)+3. Thus, ccCc2n+2) _< ccCc2n)+2 for n / 2.
Finally, 8 follows from Theorems 2.1.6(2) and
2.1.3(5) giving cc(P4n+2) < cc(C4n+2) < cc(P2n+2)+2 for
n >.! D
Again, from Theorems 2.1.1 and 2.1.2 we directly
obtain the following corollary which relates the previous
theorem to biclique covering numbers.
Corollary 2.1.7s The following statements are true for
n > 1:
1. bc(D*n) < bc(D*+1)+2;
2. be(D*) < bc(Dn), n / 2;
3. bc(Dn) < bc(D*)+l;
4. bc(D2n) < bc(Dn+1)+2;
5. t3cCD2n+l^) ^^Dn+i^+2> n 1 2
6. bc(Dn) < bc(Dn+1)+l;
7. bc(Dn+1) < bc(Dn)+2, n ^ 2;
8. bt(D*n+1) < bc(D* + 1)+2.
39
Results from Corollaries 2.1.4 and 2.1.7 will be
used together with computational results to obtain
logarithmic upper bounds for bc.(D ) and bc(Dn).
To conclude the list of theoretic results, Richard
Lundgren proved the following theorem. It is stated in
terms of directed biclique cover numbers since the proof
relies on theorems which apply to the adjacency matrices
of the digraphs. This theorem gives a lower bound for
bc(Dn) and bc(D*).
First, s(n) is defined as in Chapter I, section 4.
Further, an n x m nonnegative matrix. X is said to have
row containment if and only if for some i / j s x^ / 0
implies Xj^ / 0 for x^ and. Xj^ elements of X, and
1 Â£ k < m. Recall that bc(D) = rg(A(D)), the Boolean rank
of A.
Theorem 2.1.8; The following statements are true:
1. bc(Dn) > s(n);
2. bc(D*) s(nl j.
Proof; To prove 1, we use Corollary 1 of de Caen, Gregory,
and Pullman [4] Let A(Dn) be the adjacency matrix
associated with Dn. A(Dn) is without row containment, so
by Corollary 1, bc(Dn) _> s(n).
To prove 2, let A" be the (n1) x n submatrix
of A(Dn) consisting of the first n1 rows of ACDp3 Then
A' is without row containment. So, by Corollary 1 [4],
4G
rB(A") _> s(nl). Also. rB(A(D)) > r0(A*) by a result of
Gregory and Pullman [s] .. Thus, be(D*) _> s(nl). []
, It is clear from the previous theorems that the
bounds on cc(Dn) and cb(D*) are not quite sharp enough
to obtain exact results. Therefore, it has been necessary
to acquire exact values for some n by seeking the assistance
of computers. The problem of generating the longest
2nsequence of subsetson a kset has proven to be very
timeconsuming, even with computer assistance, so exact
results are still limited. i
The goal has been to generate the longest
cyclically disjoint and consecutively disjoint sequences
using elements k}, where a,b e {1k} and a" is
in every oddnumbered subset while "b." is in every even
numbered subset. This enabled the best possible cover to
be obtained without generating every sequence of length
2n on a kset in order to compare the results. The
smallest k for which a 2nsequence is generated will be
the k such that bc(D,) = k2 or bc(D*) = k2.
n n
A program to do this was written in Fortran, an
iterative language.. However, constructing a sequence of
subsets requires the recursion of trying different
sequences until one works. I owe many thanks to Curtiss
Barefoot for writing the part of the program which forces
an iterative language to handle recursion. The program
was run on both scalar and vector computers. It proved to
41
be highly vectorizable in all but the recursive portion
of its code. Sequences of length ten through twenty (even
only) were generated using all possible sizes of subsets.
As the sequences became longer, an unacceptable amount
of computer time was being used"unacceptable" meaning:
(1) hours of supercomputer time were being used to generate
one sequence; and (2) system operators take a dim view
of anyone Using that amount of time on their machine.
This being the case, a conjecture as to the optimal size
of the had to be made. Fortunately, all of the sequences
between lengths ten and twenty showed the same patterns,
depending on k. The following, then, are the restrictions
on the size of the F^ based on previous empirical data:
1. For cyclically disjoint 2nsequences, the optimal
size for F^ is:
a. (kl)/2 for every subset, for k odd;
b. k/2 alternating with (k/2)l, for k even.
2. For consecutively disjoint 2nsequences, the optimal
size for F^ is:
a. (kl)/2 for [Fj^, F 2 n i ] and ((kl)/2)+l for
F2n For k odd>
b. k/2 alternating with (k/2)l for [f^,...,F2n
with k/2 for F2n, for k even.
The proof of this conjecture has been difficult to produce,
even though it need only be shown that there exists such
a sequence using a minimum k. A similar conjecture is
42
made by de Caen, Gregory, and Pullman [5] regarding the
size of sets used in calculating ccCC2n) and cc(P2n), and
is shown in Chapter I, section 2.
The first 20sequence which could be generated
required k = 9 (shown below). Elements 1 and 5 alternate.
So, for this example we have cc("C20) = 9 and bc(DXg) = 7.
1 1 ^ ro F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F 17 F18 F19 F20
1 5 ) 2 1 3 1 4 1 A 1 2 1 3 1 3 1 2 1 5
2 7 3 5 4 5 2 5 .2 5 3 5 A 5 2 5 A 5 3 6
3 8 4 8 6 8 6 8 3 6 7 Â£ 7 6 4 Â£ 8 Â£ A 7
A 9 6 9 7 9 7 9 7 9 8 9 8 9 8 7 9 7 9 8
Each subset represents vertex i in C2Q and a vertex
with incoming or outgoing arcs in D^g. The elements
{1,...,9} are the indices of the cliques which cover C2g
and D^g. The cliques for a cc covering of "C2g are:
Cx = {1,3,5,7,9,11,13,15,17,19} which covers X;
C2 = {1,4,7,9,12,15,18};
C3 = {1,3,6,9,11,14,16,19};
C4 = {1,3,5,8,10,13,15,17,19};
C^ = {2,4,6,8,10,12,14,16,18,20}, which covers Y;
C6 = {3,5,7,10,12,14,16,18,20};
C? = {2,5,7,9,11,13,16,18,20};
C8 = {2,4,6,8,11,13,15,17,20};
C9 = {2,4,6,8,10,12,14,17,19}.
43
Cliques one and five play no part in covering
Therefore, we have the following bicliques in the directed
biclique covering of 0^:
B2 = {1, 7,9, 15} {4, 12, 18} >
B3 = u, 3,9, 11, 19}  {6, 14, 16};
8 4 = {1, 3,5, 13, 15,1.7, 19} {8,10};
8 6 = {3, 5,7} {10,12 ,14 ,16 ,18,20}
B7 = {5, 7,9, 11, 13} > {2, 16, 18,20};
B8 = {11 ,13, 15, 17} + {2, 4,6 ,8,20};
B9 = U7 ,19} {2,4,6 ,8, 10, 12,14}.
In comparison, below is listed a consecutively disjoint
20sequence on an 8set where elements 1 and 3 alternate.
Here we have cc(F20) = 8 and bc(D*g) = 6. This is one of
the apparently few places where bc(D*) / bc((Dn)*
F2 F3 F4 F5 F6 F7 F8 F9 F10 F_u F12 111 F_14 fl5 lii fiz F18 F19 F20
i 5 i 2 1 3 1 4 1 4 1 2 1 3 1 3 i 4 1 2
2 7 3 5 4 5 2 5 2 5 3 5 4 5 2 5 2 5 3 4
3 e 4 8 6 8 6 8 3 6 7 6 7 6 4 7 6 7 8 5
4 6 7 7 7 8 8 8 8 8 7
Cliques and directed bicliques for the coverings of P2g
and D*Q are obtained in a similar fashion to that of C2Q
and D1Q.
Computergenerated sequences using our conjecture
on subset size have yielded the values in Table 3.
44
Table 3
Values for s(n), bc(Dn) and t>c(D*)
for n = 1,...,53
n 2 3 4 56 79 10 1120 21 2232 33 3435 3653
s(n) 2 3 4 4 5 5 6 7 . 7 7 7 8
UC(D*) 1 3 4 5 6 6 7 7 8 8 9 9
be C D n J 0 3 4 5 6 7 7 7 a 9 9 9
These empirical results, led Richard Lundgren to obtain
the following upper bounds for bc(On).
Theorem 2.1.9s bc(D*) Â£ 2Llog2 (n2)J n >_ 18.
Proof: Inequalities '2.1.7(1) and 2.1.7(8) in conjunction
with computed values give:
bc(D*)Â£8, forl8Â£nÂ£33;
bc(D*) Â£ 10, for 34 Â£ n Â£ 65;
be(D*) Â£ 12, for 66 Â£ n Â£ 129.
Using these values and theorems, bc(D*) Â£2l_log2 (n2)J .
The major problems which are still unsolved for
this area are:
1. Is bc(Dn) monotonically nondecreasing?
2. Does a sequence of subsets exist using k elements
such that k = cc(U2n) and F^ is as conjectured?
3. The same question as number 2, but for cc(P2n).
45
4. If existence can be proved for numbers 2 and 3, can
an integer programming problem be instituted which
will find the optimal k for a given sequence length?
5. What are the exact values for bc(Dn) and bc(D*) for
all n?
The problem of monotonicity is a tricky one in
the case of b^:(D ). It is desirable to be able to use a
n
proof by induction in this case. However, a proof by
induction does not work for any characteristic of Dn
This stems from the fact that Dn does not have the
hereditary property. A digraph D has the hereditary
property if, whenever we take away an arbitrary number
of vertices and their incident arcs, the resulting digraph
has the same characteristics as D. If we take away any
m vertices and their incident arcs from D to obtain D", D'
is not the complement of a cycle. In an induction proof,
it is important to be able to compare a digraph to
one with fewer vertices, D^, and use the induction
hypothesis. But removing a vertex from does not
give D^, so induction fails. Yet, monotonicity is
something I would like to prove in the future.
Directed Biclique Partitions
The discussion of directed biclique partitions
will center around bp(D ). To understand the conjectures
and the current open problem, the relationship between
bp(D) and the real rank of A(D), rR(A(D)), must be examined.
46
As shown in Chapter I, r^+(A(D)) = tfp(D). If A(D) can
be separated into k matrices of rank one which sum to
A(D), and the elements of these rankone matrices are
nonnegative integers, k is an upper bound for rR(A(D)).
It is possible that fewer than k rankone matrices will
be needed [whose sum is A(D)) if all real numbers are
allowed as elements. Therefore:
rR(A) 1 rz+ C A).
Cases where equality hold can be found in [lo], and with
strict inequality in [ll].
The above relationship gives a lower bound on
r +(A(Dn)), and so on bp(Dn). The upper bound is n, since
bicliques using entire rows or columns can be used. When
n is odd, rR(A(DnJ) = n [l3] So, bp(Dn) = n for n odd.
bp(Dn) = n is also conjectured when n is even.
However, rD(A(D 1) = ni in this case f13. So, it must
be shown that either a partition using n1 directed
bicliques exists, or prove that it cannot.
In attempting to show that the conjecture is true,
I tried to see what would happen if any directed biclique
were removed. I used a program written by Bill Cherowitzo
to remove blocks of ones and then to take the real rank
of the remaining matrix. Whenever an odd x odd block
was removed, the real rank of the new matrix went up to n.
In the following lemma, it is shown that the real rank of
47
the matrix obtained by removing a 1 x k block of ones
will have real rank of at least n1.
Lemma 2.2.1: Let Dn be the complement of a cycle on n
vertices, and B be a 1 x k directed biclique of Dn. If
ACDn B) is the adjacency matrix obtained from the arcs of
n minus those of B, then rR(A(DnB)) >_ n1.
Proof: A(Dn~B) has only one row or column where ones
have been replaced by zeros. So, A(D* is a submatrix
of this matrix. Since rR(A(D*_^)) = n1 [l3] then
rR(A(DnB)) > n1. []
This lemma tells us that if any biclique partition
can be found using n1 directed bicliques, it will not
have a 1 x k directed biclique. If we took out a
1 x k directed biclique, rD(A(D B)) > n1 implies
rz+(A(DnB)) >_ n1, so at least n1 more bicliques would
be needed to cover the remaining arcs.
The data support the conjecture that any directed
biclique partition of Dn for n even will not have an
odd x odd directed biclique in it. A characteristic of
Dn for n even is if the rows of A(Dn) are added using
mod 2 addition, the result is the ndimensional zero
vector. If odd x odd blocks of ones are eliminated
from consideration in r +CA.(Dn)), mod 2 addition of the
rows will not give the zero vector. If mod 2 addition can
be substituted for real linear combinations of the rows,
48
n
this would imply that for Â£ airi (where r^ is the ith
i = l
row), = 0,1,1 are the only possibilities. This is
definitely not the case in a general (0,l)matrix, but
may be true in Dn.
Similarly, empirical data show that whenever an
odd x even or even x odd block of ones is removed from
A(Dn), rR(A(Dn)) = n1. If mod 2 addition can be
substituted for linear combinations of rows, this case
can also be proved true. This would further limit the
cases in the search for a directed biclique partition
using n1 directed bicliques. If rR(A(DnB)) = n1' when
an even x odd block of ones, B, is removed, since
rR^A^DnB^ ^Z+(A(D^B^, ^ would take at least n1
more bicliques for a partition of the remaining ones.
Thus, any directed biclique partition for Dn when n is
even could have only even x even directed bicliques.
y
Even though bp(Dn) has not been determined in
general for n even, we have the following result.
Theorem 2.2.2: bp(Dg) = 6.
Proof: Suppose bp(Dg) = 5. Then, by the discussion
following Lemma 2.2.1, cannot have a 1 x k directed
biclique (claw). The largest directed biclique possible
has size 2x3. If the 2x3 is used, the eighteen
remaining arcs must be partitioned by four bicliques. At
least one of these bicliques must contain more than
49
LifJ = 4 arcs. Thus, another 2x3 or 3x2 is needed.
This leaves three bicliques to partition twelve arcs, so
they must all be 2 x 2s since no l x ks are allowed.
But there are at least two isolated ones in the rows or
columns of the 2 x 3s, since three of the four ones are
already partitioned. So, these ones must go into claws.
Therefore, no partition using five bicliques exists if a
2x3 is used.
Suppose, then, a 2 x 2 is the largest biclique.
It takes = 6 of these to partition the arcs of Dg.
Therefore, bp(D6) =6. []
Since the determination of bp(Dn) still remains
a mystery for n even and greater than 6, it is desirable
to have the computer do some of the work of computation.
Previously, in section 1, it was shown that sequences of
subsets could be generated to obtain covers of Dn Here,
new constraints can be added which give a minimum directed
biclique partition.
Previously, it was possibile that an evennumbered
subset and an oddnumbered subset had two elements in
common. This forced the associated edge in B2n to be in
two bicliques, which in turn represented an arc of DR in
two directed bicliques. The following constraint is thus
mandated: If a pair of elements occurs in a subset f^i+i
then it cannot occur in a subset numbered F2j+2, fr
i,j = 0,...,nl. Along with the restrictions that
50
Fi n Fi+1 = 0 for ^ < i 1 n1, and F1 n Fp = 0, sequences
generated using these rules will give a partition of D .
Of course, it is best if not every sequence needs to be
generated. Therefore, we define cp(U2p) which is analogous
to ccCC2n)*
Definition: A cp cover of a graph H = (X,Y,E) where X and
Y are disjoint sets of vertices which comprise all of the
vertices of H, and and are complete subgraphs of
H, is a clique cover of H such that:
I. Ca and 0^, which cover the complete graphs X and Y of
H, respectively, are in the cover; and
2. No pair of vertices, x e X and y e Y, appear in more
than one clique together.
The minimum number of cliques in a cp cover of H is defined
to be cp(H) = k. For all applications of these definitions,
the set X will consist of oddnumbered integers and Y
will consist of evennumbered integers.
A
A cp cover is not a clique partition of H because
Ca and Cg will cover edges which must be included in any
other clique of size greater than two in the cover. So,
in H, some edges in X and Y may be included in more than
one clique. The added restriction of no odd and even
pair occurring in more than one clique forces the partition
of the edges between X and Y.
Theorem 2.2.4: bp(Dn) = cp(C2p)2.
51
Proof:
1. Let C be a minimum biclique partition of B2r. Since
bp(Dn) =bp(B2n
will partition
each biclique
edges in "C2n.
the edges just
added to comple
), the same number of directed bicliques
D.
Add the edges between X and Y for
of B2n* These may not be all of the
So, let Ca and be added to cover
added and those which may need to be
:e C2n. So bp(Dn) = b.p(B2n) > cp(C2n)2.
Let C be a minimum cp cover of C2r]. Since no two
cliques of c has a repeated pair of odd and even
integers, then no edge between X and Y is in more
than one clique. Because every edge is in at least
one clique, any edge between X and Y is in exactly
one clique. C and CQ are not used in the partition
cx p
of B2n, so the remaining cliques will be used in that
partition. Thus, bp(Dn) = bp(B2n) < cp(C2n)2.
Therefore, bp(Dn) =.cp(C2n)2.
Following is an example of a sequence of subsets
ch was generatec to provide a partition for V
F1 F2 F3 F4 F5 F6 F7 *" 8 F9 F10 F11 F12
1 5 1 5 1 5 1 5 1 5 1 5
2 6 2 3 7 2 3 2 4 2 6 4
3 7 4 6 8 6 7 8 6 7 8 7
and cover X and Y of C^2, respectively. Notice that
no pair in an evennumbered subset occurs in an odd
numbered subset. Ho
wever, notice that the pair 5,6 occurs
52
in three evennumbered subsets: F2, and Therefore,
edges (2,4), (2,6), and (4,6) are in cliques and C^.
This creates a cover for edges in X and edges in Y. Since
these edges are not involved in B^2 or Dg, the bicliques
formed from C2, C3, C^, Cg, C7, and Cg will partition the
edges. Following are the bicliques:
B2 = a, ,3}  {6,8, 10};
b3 = {i, ,7}  {4};
B4 = {3: ,n + U2};
B6 = ,11} > {2,4 ,6} ;
B7 = {5: ,7} + {2,10 ,12};
8 8 = {5: ,11} > {8}.
A _
No arc is covered twice; and bp(Dg) = 6 = cp(C2n)2.
This result can be extended for use in determining
the directed biclique partition number of D*. It follows
directly from Theorem 22.4.
Theorem 2.2.5: bp(D*) = cpCP2 .)2.
Using Theorems 2.2.4 and 2.2.5, cyclically or
consecutively disjoint sequences of subsets generated
using the smallest number of elements will give cpCc2 )
and cpCP2n). T^us computers can generate these sequences
to find bp(Dn) .
Not only does this concept work for Dn and D*, but
a more general theorem can be designed to find 6c(D) and
53
bp(D) for an arbitrary digraph D. First, let D be an
arbitrary digraph, and Bp be the bipartite graph such
that A(D) = A(Bp). Then let Gp be the graph obtained by
making complete graphs of X and Y in Bp. The following
theorems then hold.
Theorem 2.2.6: bc(D) = cc(Gp)2.
Proof:
1. Let D be an arbitrary digraph, and C be a minimum
biclique cover of Bp. By making the bicliques of C
into complete graphs, at best, these complete graphs
will cover the edges of Gp. If not, Ca and are
needed in addition to cover the edges of Gp. So
bc(D) = bc(Bp) j> cc(Gp)2.
2. Let C be the minimum cover of Gp. such that C and CQ
D a 0
exist. Then it takes at most the other cliques to
cover the edges of Bp. Thus, bc(D) = bc(Bp) < cc(Gp)2.
Therefore, bc(D) = bc(Bp) = ccCGp)2. []
Theorem 2.2.7: bp(D) = cp(Gp)2.
These theorems do not solve the problem of
determining bc(D) and bp(D), but they do make it possible
to start gathering empirical data. Not only can sequences
be generated, but as soon as one is, we know it is the
best possible.. It will be the best possible, given that
the sequence is generated with the minimum number of
54
elements. When a sequence is generated for the first
time using cc(Gp) = k elements (and cannot be generated
using less than k elements) or cp C G p) = k elements,
bc(D) = k2 or bp(D) = k2. There is no longer any. need
to generate every possible cover or partition in order
to find the one using the least number of directed
bicliques. In the case of an arbitrary digraph, D,
n Fj = J2f if edge (v^,Vj) is not in GQ. All oddnumbered
sets must still intersect, since X is a complete graph.
The same is also true for all evennumbered sets. The
constraints for which sets do or do not intersect must
be built into the program.
There is no known way to tell what is the optimum
size for the subsets F^. It certainly relies on the type
of digraph. One might be inclined to say that a dense
digraph would require more directed bicliques to cover
it. However, it is closely tied to the relationship
between the arcs. Take, for instance, DK, shown in
1, nl
Figure 14a. DK^ n ^ is a directed biclique, so
bcCDKj^ n_^) = 1. DK^ n_1 has nl arcs. Another digraph
with nl arcs is the cycle illustrated in Figure 14b.
Each arc is a directed biclique, and bc(DCn ^ = nl.
55
Figure 14
a. A directed biclique on n vertices.
b. A cycle on n1 vertices.
CHAPTER III
DIRECTED BICLIQUE COVERS AND PARTITIONS
OF ACYCLIC DIGRAPHS
Introduction
Another restriction to put on a digraph, D, in
order to find out bc(D) and bp(D), is to force the digraph
to be acyclic. The results in this chapter were recently
published [l2] by my advisor, J. R. Lundgren, and myself.
The three major levels of connectivity of a
digraph strongly connected, unilaterally connected, and
weakly connectedwill be used in this chapter. Let D be
a digraph. If x and y are any two vertices in V(D) such
that there exists a path from x to y and from y to x, then D
is strongly connected. If there exists a path from x to y
or from y to x, then D is unilaterally connected. When
direction is disregarded and the underlying graph is
connected, then D is weakly connected. A digraph which
is of a specific connectivity level also meets the
requirements of the lower connectivity levels. When the
word "strictly" is applied before a connectivity level
in this paper, it means the given level is the highest
level which can be used to describe the digraph. For
example, a digraph which is strictly weakly connected
57
Is weakly but not unilaterally connected. A digraph D
is acyclic if It does not contain a cycle v1,Cv^,v2),V2>
(v2,v3) .vk, (vk,v1) for e V(D).
Unilaterally Connected, Acyclic Digraphs
An acyclic, connected digraph can be viewed at
only two connectivity levels: (1) strictly unilaterally
connected, and (2) strictly weakly connected. Neither
the digraph nor any of its generated subdigraphs will be
strongly connected. If a subdigraph were strongly
connected, a cycle would have to exist: Let u,v be two
vertices in the subdigraph. There exists a path
P: = u,x1,x2, ,xk,v and a path p2 = v, wx w2, .. wm,u
since the subdigraph is strongly connected. If the x^
and w. are all unique, then p1 joined with p2 is a cycle,
and cycles are not allowed. If some w^ are equal to other
x^, then there exists one which path p^ reaches first.
Let this vertex be labeled z. Then u,x,,...,x. .,z,w.,,,
...,w >u is a cycle. Therefore, there can be no strongly
connected generated subdigraphs of an acyclic digraph.
Equality is obtained for both b'c(D) and bp[D) in the case
of a unilaterally connected, acyclic digraph, so this
case is examined first.
Theorem 3.2.1: If D is an acyclic, unilaterally connected
digraph on n > 2 vertices, then bc(D) = n1.
58
Proof: The proof is by induction. For n = 2, we have
be CD) = 1 = n1. Assume that for n = k, bc(D) = k1. Let D
be an acyclic, unilaterally connected digraph on k+1
vertices. There exists a vertex x e V(D) with only
outgoing arcs. The subdigraph O' generated by the vertices
V(D){x} is also unilaterally connected, so ttc(D") = k1.
Since we can include the arcs from x as one biclique,
be CD) be CD )+l = k.
However, there is a vertex y e VCD") which has
only outgoing arcs and.Cx,y) is an arc in D. Hence, Cx,y)
must be covered in a different biclique from those used
in covering D' so that bc('D) >_ bcCD"') + l = k.
Therefore, we have bcCD) = n1. []
We can also partition the arcs of D into n1
directed bicliques.
Theorem 3.2.2: If D is an acyclic, unilaterally connected
digraph on n > 2 vertices, then bp CD) = n1.
Proof: Let D be an acyclic, unilaterally connected digraph
on n >_ 2 vertices. Since bc(D) < bp(D), we have that
n1 _< bp(D).
There exists a vertex z e VCD) which has only
incoming arcs. Thus, there is a trivial partition
containing n1 disjoint directed bicliques, each
consisting of all the outgoing arcs of a vertex in VCD){z},
y
giving bpCD) <_ n1.
59
Therefore, we have bp(D) = n1. []
The following corollary is obtained directly from
the relationships bc(D) = rg(A(D)) and tip(D) = r +(A'(D)).
The second corollary ties the results to transitive
tournaments. A transitive tournament is an acyclic,
unilaterally connected digraph, so the result follows
immediately from Theorems 3.2.1 and 3.2.2. A matrix is
strictly right triangular if all elements on and below
the diagonal are zeros.
Corollary 3.2.3s, If A is an n x n, strictly right
triangular (0,l)matrix with ones along the super
diagonal, then rg(A) = r^+(A) = n1.
Corollary 3.2.4: If D is a transitive tournament on n > 2
vertices, then bc(D) = bp(D) = n1.
Strictly Weakly Connected,
Acyclic Digraphs
In the strictly weakly connected, acyclic digraph
case, only bounds for bc(D) and bp(D) are determined.
Here we examine those bounds and find digraphs which have
>
bc(D) and bp(D) for every value therein.
Theorem 3.3.1s If D is an acyclic, strictly weakly
connected digraph on n > 3 vertices, then t>c(D) Â£ n2.
Proof: This proof is by induction. For n = 3, we have
bc(D) = 1 <_ n2. Assume that for n = k, bc(D) Â£ k2. Let D
60
be an acyclic, strictly weakly connected digraph on k+1
vertices. There exists a vertex x e V(D) which has only
outgoing arcs. The subdigraph Degenerated by the vertices
V(D){x} has the following possibilities of connectivity:
(a) disconnected, (b) strictly weakly connected, or
(c) unilaterally connected.
Case (a); disconnected. Let E^, i = l,...,m,
m _> 2, be the m components of O', and let p^ = v(E^).
m
So 5 p. = k. Each E is at most unilaterally connected,
i = l 1 1
giving bc(E^) < p^1 tor 1 _< i _< m. Hence,
m m
bc(D") < J (p,l) = ( 1 P.Om = km,
i=l i = l
so that bc(D') < km <: k2. We know we can cover the arcs
from x with one directed biclique, so bc(D) < bc(D')+l _<
km+1 _< k1 = n2.
Case (b): strictly weakly connected. bc(D)<_kl,
so we have bc(D) <_ bc(D") + l < k1 = n2.
Case (c): unilaterally connected. Here we examine
D^and find a vertex whose removal from D instead of x gives
a subdigraph with connectivity of either Case (a) or
Case (b) above.
D' has a vertex y with only outgoing arcs and a
vertex z with only incoming arcs. Since O' is unilaterally
connected, y can reach all other vertices of D^. Vertex
61
x cannot reach all of the other vertices in D because D
is strictly weakly connected and D is unilaterally
connected. Therefore, (x,y) cannot be an arc in D. This
implies that there is no path from x to y or y to x in D.
Vertex z with only incoming arcs in D" also has
only incoming arcs in D, due to x having only outgoing
arcs before its removal. Let E be the subdigraph of D
generated by using vertices V(D){z}. Vertices x and y
are in V(E). Thus, E is strictly weakly connected or E
is disconnected. By Cases (a) and (b) then, we know that
bc(D) Â£ n2.
Therefore, by Cases (a), (b), and (c), bc(D) <_ n2.
The biclique partition number of D is similarly
bounded by using the previous proof, and the following
theorem is obtained.
Theorem 3.3.2: If 0 is an acyclic, strictly weakly
connected digraph on n Â£ 3 vertices, then bp(D) <_ n2.
Unlike the case of the unilaterally connected
digraphs examined earlier, we cannot unequivocably state
that bc(D) = bp(D) in the strictly weakly connected case.
Certainly there are occasions when this is true, but the
following example illustrates a case Where it is not.
62
Example A: Let the adjacency matrix of D, A(D), represent
an acyclic, strictly weakly connected digraph. Here,
A(D) =
3) = 4.
1 2 3 4 5 6
1 0 0 1 0 1 1
2 0 0 1 1 1 0
3 0 0 0 1 1 1
4 0 0 0 0 1 1
5 0 0 0 0 0 0
6 0 0 0 0 0 0
A minimal directed biclique covering of D is given by the
bicliques:
B
x = {(1,3),(2,3)},
B2 = {(2,4),(2,5),(3,4),(3,5)} ,
B3 = {(1,5),(1,6).,(3,5),(3,6),(4,5),(4,6)}.
Yet any partition requires four bicliques.
These results also extend to the Boolean and
nonnegative integer ranks of matrices, given in the
following corollary.
Corollary 3.3.3: If A is an n x n, strictly right
triangular matrix with at most n2 ones on the super
diagonal, then r0(A) Â£ n2 and r +(A) _< n2.
63
When bounds are found for b"b(D) and bp(D), an
interesting problem arises: Can a digraph on n vertices
be found for each of the values within the bounds? This
is known as "interpolation." In the case of a strictly
weakly connected, acyclic digraph, it is possible to find
examples for each value as illustrated in Figures 15, 16,
and 17.
ACD1)
0 1 1 1
0 0 0 0
0 s
Figure 15. A strictly weakly connected acyclic digraph
where bc(D) = bp(D) = 1.
64
Figure 16
A strictly weakly connected acyclic digraph
where be (D) = bp (D) = 2.
65
In general, for 1 = 2,...,n2, we have
A(D.)
1
2
3
i
i+1
1 2
0 1
0 0
0 0 0
3
1
1 0
0 0 0
0 0 0
0 0 0
2
3
4
i
i+1
i+2
n
... i i+1
1 1
0 0
0 0 0
0 1 0 . . .
0 0 0 . . .
n
1
0
0
6
o
Figure 17. A strictly weakly connected acyclic digraph
where bc(D) = b~p(D) = i.
Although we have found examples of digraphs where
bc(D) = bp(D) and bc(D) < top CD), these classes of digraphs
have not been characterized.
66
Results for Digraphs with Cycles
A strong component of a digraph D is a maximal
subdigraph which is strongly connected. The following
theorem uses strong components of a digraph D to give a
lower bound for bc(D) and bp(D).
Theorem 3.4.1: If D is a digraph on n > 1 vertices, and
for i = l,...,m are the m strong components of D, then
m
bc(D) > Y be(D .)
i = l
and
m
bpCD) > Y bp(D.).
i = l
Proof: Let for i = 1,. .., m be the m strong components of
a digraph D, and let B be any directed biclique in a
minimum directed biclique covering of D. Suppose B covers
arcs in two strong components, D. and D.. Say (x1,x2) is
an arc covered in and C y j_y 2 ^ an arc covered in Dj.
From the definition of a directed biclique, this implies
that (x^,y2) and (y1,x2) are arcs in D. So a path exists
from D. to D. and from D. to D.. Since they are maximal,
J J
we must have i = j. Therefore, bc(D) cannot be less than
the sum of be(D .j so
J
67
m
be CD) > Y bc(D.)
" j = l J
and similarly,
m
bp (D) > ]_ bp (D ,). ' 0
j = l J
When we examine digraphs with cycles, there are
many forms these digraphs can take. This permits us to
bound bc(D) and bp(D) only within a very wide range.
Therefore, it is instructive to find examples which attain
the lower bounds and upper bounds for the three
connectivity levels and also to solve the interpolation
problem. If D has a cycle, it is easy to see that b"c(D) _> 2
and bp(D) >_2. As mentioned in Chapter II, every arc of
a generated cycle will belong to a different directed
biclique. Thus, the cover and partition number of D must
be at least as big as the size of the largest generated
cycle. Following is a theorem which gives the bounds for
bc(D) and bp(D) when D is a digraph with cycles. The
upper bound n can be achieved, for example, by an ncycle.
Theorem 3.4.2: If D is a digraph with cycles on n _> 6
vertices, then 2 <_ be (D) _< n and 2 < bp(D) _< n.
Now it is instructive to look at interpolation
for each of the values within the bounds for each of the
connectivity levels. It is possible for a digraph to be
68
strictly unilaterally connected or strictly weakly
connected even if it has a cycle. All vertices on a cycle
form a strongly connected subdigraph, but there may be
vertices not on the cycle which can neither reach the
cycle nor be reached by the cycle.
When looking at the interpolation problem, it is
necessary to find a digraph D where bc(D) and bp(D) are
the desired values, but the values do not depend on the
number of vertices. Therefore, in the following figures
in this chapter, every digraph D is shown with n vertices,
where n is not determined. Digraphs where bc(D) = bp(D) = 2
are shown in Figures 18, 19, and 20. Figure 18 is a.
strongly connected digraph, while Figure 19 represents a
strictly unilaterally connected digraph. A strictly
weakly connected digraph where bc(D) = bp(D) = 2 is
illustrated in Figure 20. The strongly connected graph
in Figure 18 is a series of twocycles. All arcs oriented
away from vertex 1 will be in one directed biclique. The
arcs directed toward vertex 1 will be in another. These
Figure 18. Strongly connected digraph where
bc(D) = bp(D) = 2.
69
two bicliques have no arcs in common, so they serve as a
cover as well as a partition.
Figure 19. Strictly unilaterally connected digraph
where bc(D) = bp(D) = 2.
Figure 19 represents a strictly unilaterally
connected digraph. None of the vertices 1, ,n1 can
reach vertex n, but n can reach all the other vertices.
This digraph will require two directed bicliques of the
same form as those of the strongly connected digraph.
The difference will be that the directed biclique
containing arcs oriented toward vertex 1 will have one
fewer arc here.
Only one cycle is in the strictly weakly connected
digraph in Figure 20. It is possible to have twocycles
between vertex 1 and all vertices 2,...,n2 and still
have the digraph be strictly weakly connected. Vertices
n1 and n would not be able to reach each other, thus
giving the connectivity category. In this digraph we
again form, directed bicliques as in the previous two
70
Figure 20. Strictly weakly connected digraph
where bc(D) = hp(D) = 2.
examples. One directed biclique, however, will contain
only the arc (v2,v^).
In the next two figures, 21 and 22, digraphs will
be shown which reach the maximum value bc(D) = Etp(D) = n.
For a strongly connected digraph on n vertices, it has
already been mentioned that a cycle on n vertices requires
n directed bicliques for both a cover and partition.
Therefore, the remaining two connectivity categories will
be shown. Each figure has two parts. The first part
will give the digraph (a] when n is even, and the second
part will give the digraph (b) when n is odd.
The directed bicliques for the strictly
unilaterally connected digraph in Figure 21.a. will be:
1. Every arc from an oddnumbered vertex to an even
numbered vertex will form its own directed biclique.
There are ^ of these arcs.
71
1 2 3 4 n1 n
Figure 21. Strictly unilaterally connected digraph
where bc(D) = bp(D) = n.
2. Every evennumbered vertex has two arcs leaving it
(except vertex n). These two arcs from any even
numbered vertex form their own directed biclique and
(v ,v form another. There are 5 even numbers.
From the directed bicliques formed in (1) and (2), there
are ^ + = n directed bicliques in both the cover and
partition. This digraph is strictly unilaterally
connected because vertices on the far right cannot reach
vertices on the far left.
Figure 21.b. will have a similar directed biclique
structure. However, this digraph has a cycle of length
three. Therefore, the following changes are necessary:.
1. (v1,v2) and (vn,vn form their own directed
bicliques.
72
2. Every arc from an evennumbered vertex to an odd
numbered vertex forms its own directed biclique.
There are of these.
3. Every two arcs leaving an oddnumbered vertex
(excluding vertex 1 and vertex n) form a directed
biclique. There are  1 directed bicliques
containing two arcs.
From (1), (2), and (3), there are 2 + + 2^ 1 = n
directed bicliques needed to both cover and partition the
arcs in Figure 21.b.
The directed bicliques for Figure 22.a. and 22.b.
are formed similarly to those in Figure 21. However,
care must be taken since the arcs connecting the cycles
vary in direction. This is what makes the digraphs
strictly weakly connected. In Figure 22.a., for example,
vertices 1 and 2 cannot reach vertices 5 and 6; nor can 5
and 6 reach 1 and 2.
Of course, now it must be shown that every value
for bc(D) and bp(D) can be obtained between the bounds of
2 and n. So, we not only need to look at an arbitrary n,
but also an arbitrary i, 2 _< i Â£ n, such that
bc(D) = bp(DP) = i. In these examples, we examine an
adjacency matrix for the digraph D. Figure 23 shows A(D)
of a strongly connected digraph.
73
1 2 3 4 3 6 n1 n
n > 6; even
a. n even.
2
n1 n
odd.
n >_ 7; odd
Figure 22. Strictly weakly connected digraph
where bc(D) = bp (D) = n.
1 2 3 4 5 i i + 1 ... n
1 0 1 1 1 1 1 1 ... 1
2 1 0 1 0 0 0 0 ... 0
3 1 0 0 1 0 0 0 ... 0 0 3
1 i 0 0 0 0 1 0 6
i 1 0 0 0 0 0 0 ... 0
t n 1 0 0 0 0 0 0 ... 6
Figure 23. Adjacency matrix of a strongly connected
digraph where bc(D) = bp(D) = i.
74
The digraph D represented by A(D) in Figure 23
has arcs from 1 to all other vertices, and from all
vertices to 1. So any vertex can reach any other vertex
through 1. Thus, the digraph is strongly connected. The
other' arcs represented by ones down the .superdiagonal
from 2 to i1 force be CD) = tip(D) = i. The ones in
column 1 form one directed biclique, while the ones in
row 1 form another.. Each. one on the super.diagonal from
row 2 .to row i1 will form, its own; directed biclique.
This requires i2+2 = i directed bicliques. This is not
a unique cover or partition, but any others will also
require! directed bicliques.
The matrix in Figure 24 represents a strictly
unilaterally connected digraph. As in Figure 19, its
main difference with a strongly connected digraph is the
absence of an arc (in this case, (vn,vi^
1 . 2 3 4 5 ... i i + 1 ... h
l' 0 1 1 1 1 1 1 ... .1 .
2 1 0 1 0 0 0 0 ... 0
3 1 0 0 1' 0 0 .0 ... 0
1./ 1 0 0 0 0 1 0 ... Q
1 1 0. 0 0 0. ... 0 0 ... 0
n 6 0 0 Q 0 ... 0 0 . 0
Figure 24. Adjacency matrix of a strictly unilaterally
y ~y
connected digraph where.bc(D) bp(D) = i.
75
The directed bicliques for the digraph associated with
Figure 24 are formed exactly like those for the strongly
connected digraph. The directed biclique formed from
column 1 will just have one arc fewer.
The digraph given by its adjacency matrix in
Figure 25 is strictly weakly connected. Vertices n1 and
n cannot reach each other.
1 2 3 4 5 ... i1 i i+1 n1 n
1 0 1 1 1 1 . 1 1 1 1 1
2 1 0 1 0 0 . 0 0 0 0 0
3 1 0 0 1 0 ... 0 0 0 0 0
i2 i 0 0 0 0 . 1 0 0 0 6
i1 1 0 0 0 0 . 0 1 0 0 0
i 1 0 0 0 0 . 0 0 0 0 0
n1 0 0 0 0 0 . 0 0 0 0 6
n 0 0 0 0 0 . 0 0 0 0 0
Figure 25. Adjacency matrix of a strictly weakly
connected digraph where bc(D) = bp(D) = i.
If i = n1, this example would become strictly unilaterally
connected. For i = n1, remove the arc (n,nl) from
Figure 22.a. or 22.b. That will remove one directed
biclique in the cover and partition, so bc(D) = bp(D) = n1.
Specific types of digraphs which contain cycles
were examined in Chapter II. Others can be found in
76
Chapter IV, where kregular digraphs are examined. The
bounds for bc(D) and bp(D) for a strictly weakly connected
acyclic digraph and for digraphs containing cycles are
too wide to get a good idea of what is happening. It may
be possible to characterize the digraphs for a certain
cover and partition number. It would also be interesting
to see if digraphs where bt:(D) = bp(D) or bc(D) / tTp(D)
can be characterized.
CHAPTER IV
DIRECTED BICLIQUE COVERS AND PARTITIONS
OF kREGULAR DIGRAPHS
The evolution of research in the area of kregular
digraphs was discussed in Chapter I, Section 5. This
previous work raises several interesting questions:
1. Brualdi, Manber, and Ross [3] found the minimum rR(n,k)
for 1 _< k < 3, and show that rR(n,k) = rR(n,nk) for
1 _< k < n1. Since r R (n, k) < bp(n,k), it naturally
leads to the question of finding for which k
bp(n,k) = bp(n,nk}. This has proven true for all
cases studied thus far. Lundgren conjectures that
it is true for all k. In this chapter, I include his
proof for bp(n,3) = bp(n,n3).
2. For what values of n and k does bc(n,k) = bp(n,k)?
In the research done previously, two major places
have been found where there is inequality:
(a) bp(n,nl) > bc(n,nl) for n >/5; and (b) bp(n,n2) >
bt:(n,n2) for n 9. Here, evidence is provided for
an infinite sequence where equality does not hold.
3. For what values of k does tTp(n,k) = rR(n,k)? Again,
all cases studied so far have equality holding. Here
78
we show b p (n, n 3) = rR(n,n3). It also appears that
this holds for k = 4 and 5.
4. The general problem of finding t>c(n,k) and bp(n,k)
for all k.is examined further in this chapter for
k = 5. Values and bounds on bc(n,5) and bp(n,5) are
given. A conjecture is made for all n and k. In
particular, if n = qk+r with 0 < r < k, then bp(n,k)
and bc(n,k) depend on bp(k+r,k) and bc(k+r,k).
Partitions for (n,3) and (n,n3)
Recently, in our search to determine if bp(n,k) =
bp(n,nk), Lundgren proved that bp(n,3) = bp(n,n3). I
include it here both to demonstrate what is required in
this type of proof and to show its relationship to real
rank.
Theorem 4.1.1: Let z(n) = 0 if n =0 (mod 3) and z(n) = 3
otherwise. Then for all n ^ 6, b^)(n,n3) = bp(n,3) =
LjJ + z (n).
Proofs By a result of Brualdi, Manber, and Ross [3],
rR(n,k) = rR(n,nk) for 1 < k <_ n1. Since rR(n,nk) <
r^+(n,nk) = bp(n,nk), this result gives a lower bound
on the partition number.
Case i: n = 3q. Then rR(n,3) = j = q = rR(n,n3)
[10]. So, q _< r^+(n,n3). Let
79
3,3 3,3 J3,3
J3,3 3,3
ft J3,3
J3,3 ft 3,3
where A has q1 3x3 blocks in each group of three
rows. Letting each directed biclique of a partition
consist of (q1) 3^ js, it will take q directed bicliques
to partition A. This gives r^+CA) = q, so q_
Hence, r^+(n,n3) = q = r^+(n,3), and bfc(n,n3) = q =
bp(n,3).
Case ii: n = 3q+l. By previous results from
[lo] and [3] , rR(n,3) = q+3 = rR(n,n3). So,
r +(n,n3) q+3. Let
0
J
3.3
3.3
J
3,3
1 s
where the upper portion
Then r^+CA) = (3^~3 )+4 =
3,
3,3
of A
(q1)+4
ls
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
requires 3q3
= q+3, which
rows.
gives
80
q+3 Â£rz+(n,n3) Â£ q + 3. Hence, rz+(n,n3) = q+3 = r^+0,3)
and bp(n,n3) = q+3 = bp(n,3).
Case iii; n = 3q+2. By previous results from
[lo] and [3], rR(n,3) = q+3 = rR(n,n3). So,
r +(n,n3)'i> q+3. Let
3,3 J3,3 J3,3 I 1
J3,3 1
# 1 1 ls
J3,3 1
_ J3,3 1 1 ^ 1 3,3 1 + 1 0 0 1 1 0
1 0 0 1 0 1
ls 1 1 0 0 0 1 1
1 1 1 1 0 0 0
1  1 1 0 0 0
1 1
where the upper portion of A requires 3q3 rows. Then
r^+(A) = (3!3)+4 = q+3, so q+3 Â£ r^+(A) Â£ q+3. Thus,
r + (n,3) = q+3 = r +(n,n3) and bp(n,3) = q+3 = bp(n,n3).
Brualdi, Manber, and Ross [3] only calculate the
actual values of rR(n,k) = rR(n,nk) for k = 1,2,3. The
case where k = 3 was heavily used in the previous proof.
For k Â£ 4, however, the corresponding values are not
available.
81
Values where bc(n,k) = bp(n,k)
When working with general digraphs, it is not
uncommon to have the cover number strictly less than the
r
partition number. However, when trying to find a kregular
digraph with minimum cover and partition numbers, the two
almost always turn out to be the same. This can be seen
in the research by Gregory et al. [lo] for k Â£ 4 and
n = qk. The cases cited earlier for k = n1 and k = n2
show two instances when the cover and partition numbers
may not be equal.
De Caen, Gregory, and Pullman [4] have shown that
bc(n,nl) = s(n). Pritikin [l8] shows that bp(n,nl) = n.
So whenever k = n1, the cover and partition numbers can
be expected to be different. For n = 2,3,4, the value
of s(n) = n. For n > 4, s(n) is always less than n. The
difference between bc(n,nl) and bp(n,nl) becomes
larger as n gets larger because s(n) grows logarithmically.
In the case where k = 5, bc(6,5) = 4 and bp(6,5) = 6.
Here, the difference is greater than one. For n = 11,
the best possible cover number attained thus far is for
the matrix shown in Figure 26. The digraph e D(ll,5)
associated with has bcCD^) = l+s(6) = 5, and bptD^ = 7.
M2 in Figure 27 has an associated digraph D2 e D(ll,5),
where bp(02) = 6.
82
M,
0 s
0 s
0 1 1 1 1 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1i 0 1 . 1
1 1 1 1 0 1
1 1 1 1 1 0
Figure 26. Adjacency matrix of a digraph
D e D (11 ,5) with bc(D) = 5.
1 1 1 1 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 1 1 1 1 1 0
1 1 0 0 0 1 1 0 0 0 1
1 1 0 0 0 1 1 0 0 0 1
0 0 1 1 1 0 0 1 0 0 1
0 0 1 0 0 0 0 1 1 1 1
0 0 0 1 1 0 0 0 1 1 1
Figure 27. Adjacency matrix of a digraph
D e D(ll,5) where bp(D) = 6.
83
The bicliques which form the partition of M2
consist of the first three rows, the second three rows,
rows seven and eight, then each of the last three rows is
a biclique. A digraph D e D(ll,5) with tDp(D) = 5 has not
been found. It seems that although we can do one better
than bpCD^) = 7 in this case, we cannot bring the partition
number down farther than 6. This was not the case with
k = 4, because the cover and partition numbers for (5*4)
differed only by one. This leads to the following
conjecture: If we consider D(5q+1,5) for q 1,
bc(5q+l ,5) < bp(5q+l ,5). For.allq_>3, adjacency matrices
of digraphs D e D(5q+1,5) can be constructed where
bc(D) = bp(D)l. The ith ^ is placed in rows and
columns 5(il)+l through 5i, for 1 _< i <_ q1. A 6x6
5regular submatrix is then placed in the last six rows
and columns. Thus, an adjacency matrix is obtained whose
digraph D e D(5q+1,5) has bc(D) = (ql)+4 = q+3. To
obtain the partition number, (q2) J,. s can similarly
be added to M2 in Figure 27, which gives an associated
digraph D e D(5q+1,5) where bp(D) = (q2)+6 = q+4. Although
this inequality has not yet been proven, it seems to be
true. This would give an infinite sequence where the
cover and partition numbers are unequal.
In general, we believe that this conjecture is
also true for all k _> 5. The difference between bc(n,nl)
and bp(n,nl) grows larger as n does. Therefore, it seems
84
less likely that the partition number for D(kq+l,k) will
be able to equal the cover number as q becomes large.
We believe there are several infinite sequences
of examples where bp(n,k) > Bc(n,k). They are based on
the observation that for n sufficiently large, and k large
relative to n, it appears that bp(n,k) > t?c(n,k). For
example, for n _> 9, bp(n,n2) > bc(n,n2) by Barefoot et
al. [2]. Based on this, we conjecture that for k >_ 7,
bp(kq+2,k) > bc(kq+2,k). These examples have not been
encountered previously since only k < 5 has been studied
in depth.
Further results for k = 5 will be examined in the
following sections of this chapter.
Cases where bp(n,k) = rR(n,k)
In section 1 of Chapter IV, it was shown that
bp(n,n3) = ljJ+s(n) for all n ^ 6. Brualdi, Manber, and
Ross [3] also obtained that value for rR(n,n3). Other
work done in the area has failed to show any situation
where the partition number is unequal to the real rank.
Is this something which is occurring because a minimum
number is being sought? It is possible that this is the
case. Every adjacency matrix whose digraph has the minimum
partition number possesses a. real rank equal to that
number.
In the following section, 5regular digraphs will
be studied in more depth. The results there also yield
85
digraphs, Di, where bp(D^) = rR(A(D^)). However, this
provides only an upper bound for the real rank. It will
have to be proven that the real rank cannot be lower than
the partition number in these cases.
If, in fact, the partition number equals the real
rank for all k, conjectures made for bp(n,k) can be
expanded to rR(ri,k). The conjecture in the previous
section, bc(kq+l,k) < bp(kq+l,k) for k 5, would give
an infinite sequence for each k where the Boolean rank
is strictly less than the real rank. The Boolean rank
in general can be less than, equal to, or greater than
real rank. This would be a step in helping to classify
the matrices where rB(A) < rR(A).
Finding bc(n,k) and bp(n,k)
The previous sections have dealt with specific
questions surrounding kregular digraphs and matrices.
This section begins to examine the general question of
finding bc(n,k) and bp(n,k). As explained in Chapter I,
as k gets larger, casebycase proofs of the cover and
partition numbers become unwieldy. Because of this, many
of the following pages will contain upper bounds and
conjectures. Before the general case for kregular is
discussed, we will look at values and bounds for k = 5.
Since (at times) it is best to begin at the
beginning, using previous results the following values
can be obtained:
86
1. be(6,5) = s(6) = 4
bp(6,5) = 6
2. be(7,5) = 5
bp(7,5) = 5
3. be(5 q,5) = q
bp(5q,5) = q
The values for bc(8,5) and bp(8,5) are obtained
by the proof of Theorem 4.4.1. In the proof, a matrix, D,
is given where bc(D) = bp(D) = 5, which is an upper bound.
It is then shown that bc(8,5) _> 5. This forces bc(8,5)
to equal 5. Since b~c(8,5] <_ bp(8,5) and bp(8,5) <_ 5,
bp(8,5) must also equal 5. The proof that bc(8,5) > 5
hinges on a casebycase examination of the size of the
largest directed biclique in the cover. It relies on
contradictions based on assuming that bc(8,5) <_ 4.
Theorem 4.4.1: be(8,5) = bp[8,5) = 5.
Proof: The matrix in Figure 28 has r^M^) = r^+CMj) = 5.
So, bc(8,5) < 5 and bp(8,5) Â£ 5.
Suppose bc(8,5) Â£ 4. Since there are 40 arcs,
the largest biclique must contain at least ri^l = io arcs.
So the largest biclique must be no smaller than 2x5
or 5 x 2.
Let C be a largest maximal directed biclique of
a minimum cover. Place C in the upper left corner of the
87
1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0
1 1 0 0 0 1 1 1
1I 1 0 0 0 1 1 1
0 0 0 1 1 1 1 1
0 0 1 0 1 1 1 1
0 0 1 1 0 1 1 1
Figure 28. An adjacency matrix whose digraph
D e D(8,5) has bc(D) = bpCD) = 5.
matrix. The matrix will have no other ones in all of the
same rows or columns of C because C is maximal.
C cannot be a 5x5 directed biclique, because
that would leave three columns to the right of C which
must each have five ones in the last three rows. This
is impossible. Likewise, C will not be a 5x4 directed
biclique. Then there would be three columns which must
have five ones in the last four rows. Since AT is also
5regular, the case for C being a 4x5 directed biclique
follows from the preceding reasoning by interchanging the
words "row" and "column." This being true, the following
cases will prove bc[8,5) > 5 if C is i x j, which also
covers the case where C is j x i.
Case i. C is a 4x4 directed biclique. This
leaves a 4x4 area in the lower right side of A which has
88
at most four ones in each column. Therefore, up to
equivalence, the only possible configuration which yields
a 5regular digraph is given in Figure 29. The cover
number for this digraph is 6.
M4 =
'4,4
_1
Figure 29. An 8x8 5regular matrix where
C is a 4x4.
Case ii. C is a 3x5 directed biclique. The
three columns to the right of C must have five ones in
the last five rows, so the matrix also has a 5 x 3 block
of ones. in Figure 28 gives the best possible
configuration for this case, and the cover number is 5.
This arises from the remaining area being a 5x5 block
which must be 2regular, where bc(5,2) = 4. Since
reflects this, it has the minimum cover number if a 3x5
or 5x3 is the largest directed biclique.
89
Case iii. C is a 3x4 directed biclique.
There are eight ones below C and three ones to the right
of C. If two directed bicliques are used to cover these
ones, at most fifteen new arcs will be covered. This is
shown in Figure 30. If bc(8,5) <_ 4, then 401215 = 13
arcs must be covered in one more directed biclique. But
since the largest directed biclique is a 3x4 which
covers twelve arcs, this is not possible.
1 1 1 1 1 1 1 0 0 0
1 1 1 1 I 1 0 0 0
1 1 1 1 10 J 1 1 0 0
1 1 0 0 l 1 1 1
1 1 0 0 1 1 1
0 0 1 1 1 1
0 0 1 1 1 1 1 1
Figure 30. Partial construction of a matrix where
only two directed bicliques are needed
to cover the ones surrounding C (3 x 4).
Suppose three directed bicliques are used to cover
these ones. There are four columns to the right of C.
At most three of these columns will have ones in the first
three rows. So, there exists a column j which has five
ones in the last five rows. If only four directed bicliques
are used, and three are being used to cover the ones

Full Text 
PAGE 1
DIRECTED BICLIQUE COVERS AND PARTITIONS OF DIGRAPHS by Kim A. Sidwell Hefner B.A., University of Colorado at Denver, 1983 M.S., University of Colorado Denver, 1986 A dissertation submitted to the Faculty of the Graduate School of the University of in partial fulfillment of the requirements for the degree of Doctor of Philosophy Department of Mathematics
PAGE 2
This dissertation for the Doctorate of Philosophy degree by Kim A. Sidwell Hefner has been approved for the Department of Mathematics by Date i/ Z 2/ff'
PAGE 3
Kim A. (Ph.D., Applied Mathematics) Biclique Covers and Partitions of Digraphs Dissertation directed by Professor J. Richard Lundgren The theory of directed 'biclique covers and partitions is through the history of clique covers and partitions into the current research areas. The problem of finding a cover/partition of a digraph is NPcomplete, so restrictions are made to narrow the range of possible One such restriction limits the study to one type of In particular, the complement of a cycle and the complement of a path are examined. An algorithm for generating their directed and partitions is discussed. This algorithm is then generalized to work fat an arbitrary digraph. Another involves requiring the digraph to have no cycles. Bounds on the directed biclique cover and partition numbers are found for these acyclic digraphs. Also, bounds for digraphs with cycles are examined. An digraph has m incoming and m outgoing arcs. The minimum covei and numbers for a digraph, + bc(n,5) + bp(n,5), are and considered. This problem necessitates finding a 5regular digraph on n vertices which has the minimum cover and
PAGE 4
iv partition numbers. Hie types of digraphs are only restricted to being 5regular.
PAGE 5
v ACKNOWLEDGMENTS Even though a advisor should help the student think about problems, proofs, and life in g en era 1 ad v i s 0 r s a 1 s 0 s h 0 u 1 d r e c e i v e c red i t I have been extremely fortunate in having Ribhard Lundgren as my guiding light in mathematics. He has to allow me to Include him in all of the areas of dissertation where he has helped.. Therefore, I must thank him now (even before page one) for the patience, the intelligence, and the belief in me which kept me going.
PAGE 6
TABLES FIGURES CHAPTER I. II. I I I. CONTENTS . . . . . . . HISTORY . Introduction . . . Clique Covers and Partitions of Graphs Biclique Covers and Partitions of Bipartite Graphs .... Directed Biclique Covers and Partitions viii ix 1 1 3 7 of Digraphs 12 .Covers and Partitions of Regular Digraphs ..... DIRECTED BICLIQUE COVERS AND PARTITIONS OF THE COMPLEMENTS OF CYCLES AND PATHS IN A DIGRAPH .......... Directed Biclique Covers . Directed Biclique Partitions DIRECTED BICLIQUE COVERS AND PARTITIONS OF ACYCLIC DIGRAPHS Introduction . .Unilaterally Connected, Acyclic Digraphs .. Strictly Weakly Connected, Acyclic 0 i g.r a phs Results for Digraphs with Cycles 17 23 23 45 56 56 57 59 66
PAGE 7
CHAPTER IV. '!.:, __ DIRECTED B1CLIQUE COVERS PAATifiONS OF kREGULAR DIGRAPHS ...... Partitions for (n,3) and (n,n3) V a 1 u e s where bt ( n k ) bp ( n k ) Cas e s w h e r e b' p ( n 1 k ) ::: r R ( n k ) Finding b+c ( n k ) and b+p ( n k ) BIBLIOGRAPHY . vii 77 78 81 84 85 98
PAGE 8
viii TABLES Table lo Values for cc(En) and fbr n = i, o o o 28 . . . . 7 2o Relationships between elements in digraphs, graphs, and sets o o o o o o o o 30 3o Value. s for s(n), b+c.(Dn), and for n = l,ooo,53 . . 44
PAGE 9
Figure 2. 3. .4. 5. 7. 8. FIGURES A bipartite graph and its adjacency m a t r i x . Bicliques and their associated adjacency matrices ... A biclique . A digraph and its adjacency matrix . of Figure 4 and its relationship to a bipartite graph An adjacenci matrix of a digraph where + + bc(2k,n2) = s(k) and bp(2k,n2) = k An adjacency matrix of a digraph where + + bc(n,2) = bp(n,2) for odd . . . 9 10. A(B2n) . . . . . 11. 12. 13. The bipartite graph associated with Tin A C s;n) The hipartite graph associated with o* n 9 10 13 15 16 18 21 24 24 25 26 31 31 14. a. A directed biclique dn n vertices 55 b. A cycle on 55 15. A strictly weakly connected acyclic )+ digraph where bc(D) = bp(O) = l . 63 16. A strictly weakly acyclic )): d i g r a ph w he r e b c ( 0 ) = b p ( 0 ) = 2 . 64 .:' 
PAGE 10
Figure 17. A strictly weakly connected acyclic >+ digraph where bc(O) = bp(O) = i 18. strongly digraph where + + bc(D) = bp(D) = 2 . . 19. strictly unilaterally connected digraph + +. where bc(O) = bp(O) = 2 . 20. strictly weakly connected digraph + + where bc(O) = bp(O) = 2 . 21. Strictly unilaterally connected digraph "+ + where bc{O) = bp(O) = n for a. n even . . b. n odd . . . 22. Strictly weaKly connected dig.raph where b c ( 0) = b+p ( D ) = n for 23. 24. 25. 26. a. n even . . . . b. n odd . . . . Adjacency matrix of a strongly connected ?. + digraph where bc(O) = bp(O) = 2 Adjacency of a strictly unilaterally connected digraph where + + bc(D) = bp(O) = i . . Adjacency matrix of a strictly weakly digraph where + + bc{O) = bp(O) = i . Adjacency matrix of a digraph 0 E 0(11,5) X 65 68 69 70 71 71 73 7.3 73 74 75 + with bc(O) = 5 . .. 82 27. of a digraph 0 E 0(11,5) + where bp(O) = 6 . . . 82 28. An adjacency matrix whose digraph + + 0 E 0(8,5) has bc(O) = bp(O) = 5 87 29. An 8 x 8 5regular matrix where C is a 4 x 4 . . 88
PAGE 11
xi Figure 30. Partial construction of a matrix where only two directed bicliques are needed to cover the surrounding C (3 x 4) 89 31. 32. 33. 34. An matrix whose digraph + D E 0(9,5) has bc(D) = bp(D) = 5 Adjacency matrix where c is a 4 x 5 directed biclique A partial adjacency where C is a 4 x 4 and two directed bicliques cover the ones surrounding C . A partial matrix where two directed bicliques cover the ones below C . . . 91 92 93 94 Partial adjacency matrix where C is a 3 X 5 and three directed bicliques cover the ones below C 95
PAGE 12
CHAPTER I HISTORY Introduction In the history of mathematics, graph theory can be viewed as a relatively new branch. During the 1700s residents of Konigsberg, Germany, wanted to know if it was possible to take a walk in their city, cross each of their bridges exactly once, and retuin to the starting point. had islands linked to each other and the banks of the River by seveh bridges. Euler, a mathematician of that era, is credited with inventing graph theory when he solved the Konigsberg Bridge problem. He made each area of the city into a vertex of a graph. The bridges were represented by edges ftom one vertex to another. It then became the question of whether a circuit could be created beginning at a vertex, and using each edge exactly once. The answer for Konigsberg was that it could nbt be done, but a circuit which uses the edges of a graph exactly once has come to be known an Eulerian circuit. Since that time, graph theory has expanded in both theory and application. One of the appealing aspects of graph theory is that it can be applied to such areas
PAGE 13
2 as biology, engineering, operations research, and music. A problem which can be broken down into vertices and arcs or edges can be solved using theoretic techniques. Each new set of theorems in graph theory the field of application and broadens the number of problems which can be solved. The theoretic motivation for studying biclique covers and partitions of digraphs has its roots in the studies of clique covers of graphs and covers of bipartite graphs. A graph G = (V,E) is defined to be a set of vertices, v, and a set of edges, E c V x v. A bipartite graph B = (X,Y,E) has two disjoint sets of vertices, X and Y, where each edge of E occurs only between X and Y. A multigraph is a graph where more than edge is allowed between two vertices. For G = (V,E), any subset of v which has an edge between every pair of vertices in that subset is 6alled a complete subgraph, or ciigue. In a clique cover, any edge of G must be in at least one clique. The smallest number of c 1 iques to cover the edges of a graph G is known as cover number of G, and is denoted cc(G). In a clique pattition, each edge of G must be in exactly one clique. The clique number of G, is the minimum number of cliques needed to partition the edges of G.
PAGE 14
3 Similarly, biclique covers and for a bipartite graph .8 = (X,Y,E) can be defined. Any two subsets of vertices, U and Y .=. Y, where every vertex in U is adjacent to every vertex in Y and neither U nor Y is empty, is a complete bipartite subgtaph, or bicligue. The minimum number of bicliques needed to cover/partition edges of B is the bicligue cover/paztition number of B, denoted bc(B) and bp(B). After results were formed for the covers and partitions of graphs and bipartite giaphs, it was natural to try to extend these results to directed graphs (diQraphs). 5o me o f t h i s r e search i s pre sen t e d i n sections 4 and 5 of this chapter. Cligue Covers and Partitions Graphs In the past eleven years, surveys on the theory of edge coverings and partitions been presented by Orlin [17], Pullman [19], and Roberts [20]. In arlin's paper, the clique partition number is called the content of a graph, and the clique cover number is known as the Rcontent of a A large portion of Chapter II depends upon the following definition and theorems. These theorems tie set theory into the bounding and computation of the clique cover number of a graph G.
PAGE 15
4 (1) Definition: Given a family of subsets s 1 ... ,Sn' the corresponding intersection graph G has vertices ,vn such that the number of edges between vi and vj is equal to lsi n sjl. (2) Theorem (SzpilrajnMarczewski [21]): Let G be a graph with possibly multiple edges and with vertices v 1 ,vn. Then there exists a setS and a family of subsets s 1 .. ,sn of s such that lsi n sjl is equal to the number of edges in G joining vi to vj. (3) Theorem (based on the extension theorem by SzpilrajnMarczewski [22]): Let G be a graph with no multiple edges and with vertices v 1 ,vn. Then there exists a sets and a family Df subsets s 1 ,sn such that Is. n s.l > 1 if and only if v. and v. are adjacent. l J l J In (2) and (3), the elements of Scan be identified with the cliques of the graph. To see this, let a be an element of S. Suppose that S 1,s 2 ... ,s K are the subsets a a a which contain n Then each of these subsets intersects with all of th. e other subsets in this family. This implies that all possible edges exist between vertices v a 1 v a2 'v aK these vertices form a complete graph, or clique. If we look at (2), each edge is going to be in one clique. This results from Is. n s.l l J being equal to the number of edges between v and v .. l J Each of these edges is in a different clique. In (3), the minimum number of elements in any 5 satisfying the
PAGE 16
5 conditions of the theorem will be the clique cover number of G. It is the minimum number of complete graphs which cover the edges of G. Why don't subsets in (3) constitute a clique partition of G? Consider the set {5() 1 ,5() 2 .. ,5()K}. It is poisible that 5 and 5NJ. have another element, B, in ()1 ..... common since l5()i n 5()jl > 1. However, since G is not a multigraph, v()i and v()j have only one edge between them. This in the edge (v() 1,v()j) to both the clique () the clique B. Therefore, this cannot be a Further constraints which allow a clique partition to be generated using sequences. of subsets will be discussed in Chapter This settheoretic approach used by de Caen, Gregory, and Pullman [s] to generate clique covers of complements of paths and cycles in a graph. The complement of a on n vertices, En' is a complete graph, Kn' which has a simple ncycle removed. The complement of a path on n vertices, P n, is a complete graph, Kn, which has a simple path of length n1 removed. Complements of paths are the intersection graphs of consecutively disjoint subsets [F1,F2 .. ,Fn]. A sequence is consecutively disjoint if Fi n Fi+l = for i = ,n1 all other subsets intersect. If we remove a simple path of n1 from a complete graph, we can label the vertices so that the edges
PAGE 17
6 (v1,v2),(v2,v3), ... ,(vnl'vn) are the missing edges. Therefore, the subsets representing these vertices must be disjoint, and the result is a consecutively disjoint sequence of subsets. Sequences of subsets were for E4 through c28 and through P29. Similarly, complements of cycles are the intersection graphs. of cyclically disjoint subsets [F1,F 2 ,Fn]. A sequence is cyclically disjoint if Fin Fi+l,; Ia' fori= l, ,n1, and F 1 n Fn = Ia' and all other sets intersect. When an ncycle is removed from a complete graph, the vertices can be labeled so that (v1,v2),(v2,v3), ,(vnl'vn), (v1,vn) are the edges which have been removed. So the subsets representing these vertices must be eye l ically disjoint, since the (vi,vi+l) and do not exist. A problem which confronts all researchers who use the approach of generating sequences of subsets is to restrict the size of the subsets. This is a necessary restriction as n becomes large, unless there is a computer available which is dedicated only to the search for sequences of subsets. If every size of subset must be tried as every possible Fi' even computers take a great amount of time. In their paper, de Caen, Gregory, and Pullman [s] conjec;tured that if the minimum number of elements needed to cover Pn was k = 2r+l, then all subsets
PAGE 18
7 except the first and last must be of size r. This was based on work done by Meredith and Lloyd [16]. The exact values for cc(Pn+l) and cc(Cn) are given in Table 1, as calculated by de Caen, Gregory, and Pullman. n Table 1 Values for cc(Cn) and cc(Pn+1 ) for n = 1, ,28 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 2 5 5 7 6 7 6 8 7 7 7 8 7 8 7 8 28 8 cc ( P n+ 1 ) 0 1 3 4 5 5 6 6 6 6 7 7 7 7 7 7 7 7 8 8 Source: o. de Caen, 0 A. Gregory, and N. J. Pullman, Clique coverings of complements of paths and cycles, Ann. of Discrete Math., 27 (1985), p. 260. Biclique Covers and Partitions of Bipartite Graphs The early work in clique covers and partitions of graphs naturally gravitated to the study of biclique covers and partitions of graphs. Several authors, includingOrlin [11], Gregory and Pullman [11], Tuza [23], and Graham and Pollack [9] have considered this problem. 8 i c 1 i q u e co v e r s a n d p a r t it i on s o f b i p a r t i t e g rap h s play an important role in finding the directed biclique cover and partition numbers of a digraph. The relationship between the biclique cover number of both bipartite graphs
PAGE 19
8 and digraphs and the Boolean rank of (0,1)matrices is given by de Caen, Gregory, and Pullman [4]. If A is an m x n (0,1)matrix, its Boolean rank, rB(A), is the least k for which there exist m x k and k x n (0,1)matrices B and c such that A = BC (where the underlying the mat r i x m u 1 t i p 1 i c at ion i s B o o 1 e an t h at i s i t i s t he usual integer arithmetic, except 1+1 = 1). An equivalent definition for rB(A) is the minimum number of (0 1 ) r i c e s o f rank one whose Boo 1 e an sum i s A I f B = (X,Y,E) is a bipartite graph, X= {x1,x2 ... ,xm} and Y = {y1,y2 ,yn}' the adjacency matrix of B, A(B), is defined as follows: Definition: Let the rows of A(B) be labeled x 1,x2 ,xm and the coiumns of A(B) labeled y 1,y2 ,yn. Then if (v.,v.} is not an edge of B of A(B) 1 J a .. lJ if (vi,vj) is an edge of B. A ( B ) is an m x n ( 0, 1 ) matrix and b c ( B ) = r8 ( A ( B ) ) [ 4] Orlin [11] additionally proves that finding rB(A) is an NPcomplete problem. Other results on the Baolean rank of (0,1)matrices have been published by Kim [14]. Following is an example which illustrates bc(B) = rB(A(B)). In Figure 1, a bipartite graph B = (X,Y,E) is shown with its adjacency matrix, A(B). A possible biclique cover for B is:
PAGE 20
81 = 82 = 8 3 = {(1,2),(1,4),(3,2),(3,4)}, {(3,6),(5,6)}, {(1,4),(1,8),(7,4),(7,8)} 8 = 1 3 5 7 A(8) = X 2 1 1 3 1 5 0 7 0 y 4 1 1 0 1 2 4 6 8 6 0 1 1 0 9 8 1 0 0 1 Figure 1. A bipartite graph and its adjacency matrix. Another way to express these bicliques, rather than listing all of the edges in each, is: 8 1 = {1,3} + {2,4}, 82 = {3,5} + {6}, 83 = {1,7} + {4,8}. This is possible since every vertex in the first group of each b ic 1 ique is adjacent to every vertex in the second group. Every biclique in 8 corresponds to a submatrix of ones in A(8) often reterred to as a block of
PAGE 21
10 Figure 2 shows the blocks of A(B) associated with each of the bicliques. Notice that edge (1.,4) is in both B 1 s3 so these do not represent a partition. 2 4 1 :><: 2 1 [: :] 81 = A(B1 ) = 3 4 3 6 3 3 [:] 82 = 6 A(B2 ) = 5 5 4 8 1 :>< 4 1 [: :] 83 = A(B3 ) = 7 8 7 Figure 2. Bicliques and their associated adjacency matrices. Since, in Boolean arithmetic, 1+1 = 1 we see that A(B) is the sum of three m x n rank one matric::es which correspond to each one of the bicliques: !;.
PAGE 22
1 1 A(B) = 0 0 + The only place we 1 1 0 0 0 0 0 0 need 0 0 0 0 1 0 0 1 to 11 0 0 0 0 0 0 0 0 1 0 + 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 add 2 ones together is where an edge is in more than one biclique. This also illustrates why the Boolean rank df A(B) is equal to the biclique cover of B. Analogous to the biclique cover problem is the biclique partition number of a bipartite graph. This number is related to the nonnegative integer rank of A( B), r + (A(B)). rf A is an m x n (0,1)matrix, its nonnegative z integer rank, r + (A), is the least k for which there z exist m x k arid k x n matrices F and G qver Z+ providing the factorization A = FG. Results regarding bp(B) = r + (A(B)) have been found by Gregory, Jones, z and Pullman [10]. The covering obtained for the bipartite graph B in Figure 1 will not work as a partition. It will actually take four bicliques to partition the edges of B. These four bicliques .can be as follows:
PAGE 23
12 (l) B. = {1's in column i}; or 1 (2) B 1 = {1's in row i}; or (3) Bl = {1,3} + {2,4}, B2 = {3,5} + {6}, B3 = {7} + {4}, B4 = {1,7} + {8}. There are other possibilities, but none of them use fewer than four bicliques. Any partition forms a cover for a graph, even though the converse is not true. Therefore, bc(B) bp(B). Using relationships to Boolean rank and non neg a t i v e in t e g e r rank, r B ( A ( B ) ) < r + ( A ( B) ) f o 11 ow s z directly. Bipartite graphs prove to be the bridge when solving the cover/partition problems for digraphs and the analogous problems for graphs. This relationship will be examined in the following section, then further in Chapter II. Directed Covers and Partitions o Digraphs The term 11directed biclique11 has gone through a number of semant!c changes as the years have progressed. In the beginning, Lundgren and Maybee [1s] referred to these structures as cliques. This tied the idea into that of clique covers of graphs. However, the directed bicllque is more like the biclique of a rather than a clique. It is a complete directed bipartite subdigraph,
PAGE 24
13 where all arcs are oriented from the vertices in X t6 the vertices in Y. This {s shown in Figure 3. Thus, the term "biclique" was borrowed to also refer to the directed bicliques. Generally, when speaking of graphs, bicliques are taken to be undirected. If digraphs are the topic, bicliques are directed. To avoid any possible confusion, this paper will always refer to a biclique of a digraph as a directed biclique. Unfortunately, be and bp are used as the biclique cover and partition numbers for both graphs and digraphs in most papers. Recently, however, Gregory, Jones, Lundgren, and Pullman [10] introdl.lced the r + notation be and bp to denote directed biclique cover and partition numbers. That notation will be adopted here. Figure 3. A directed biclique. Actually, the journey of the terminology for directed bicliques follows the path that the research has taken: from cliques to bicliques to directed bibliques. + r The question of what bc(D) and bp(D) are for any digraph D is a large problem. Therefore, certain types of digraphs have been isolated. for study. For a tournament :on n
PAGE 25
14 vertices; Tn' Lundgren and Maybee [15] found that + + bc(Tn) = bp(Tn) = n1. Let s(n) be defined by: k s(n) = min{k: n (Lk/2J)}, where LxJ is the greatest integer less than or equal to x. The number s(n) was found to be the directed biclique cover number of the complete digraph on n vertices, DKn, by de Caen, Gregory, and Pullman [4]. Pritikin [18] used a technique due to Tvetberg [24] to show that bp(DKn) = n. Results related to the complements of cycles and paths in a [1] will be discussed in depth in Chapter II. The biclique and partition numbers for regular digraphs will be examined both in the next section and in Chapter IV. + An important relationship is that of be to be and + bp to bp. Consider the digraph D and its adjacency matrix A{D) shown in Figure 4. The rows and columns of A(D) are both labeled with the vertices of o. a = [o i f ( v i v j ) i s lJ if (vi,vj) is not an arc of D an arc of D, where ( v., v.) means that the arc is oriented from v1 1 J toward vj. Each one in the matrix A(D) represents one arc of o. This is similar to the adjacency matrix, A(B), of a bipartite graph B, since each edge
PAGE 26
. 15 1 0 = 5 2 1 2 3 4 5 1 0 1 0 0 1 2 1 0 1 0 1 A(D) = 3 1 0 0 1 1 4 0 0 0 o 0 5 0 0 0 1 0 Figure 4. A digraph and its adjacency matrix. corresponds to a one in A(8). A block of ones in A(D), say forms a directed in o. As a matter of fact, we can relabel the rows and columns in such a way (see Figure 5) that A(D) becomes the adjacency matrix of a bipartite gtaph. Since the matrix itself remains the same and each biclique of 8 is represented by block of ones, finding bc(8) and bp(B) are the same problems as finding bc(D) and t)p(D). This is can express problem ih terms of the adjacency matrix: What are the fewest number of blocks of ones needed to cover/partition the ones of A(D) (.or A ( 8 ) ) ? Hence it can be seen that b c ( B ) = b*c ( D ) and
PAGE 27
2 4 1 0 1 3 1 0 A(B) = 5 1 0 7 0 0 9 0 0 X 1 3 8 = 5 9 6 0 1 0 0 0 y 8 0 0 1 0 1 2 4 6 8 10 16 10 1 1 1 0 0 Figure 5. The adjacency matrix of Figure 4 and its relationship to a bipartite graph. + hp(B) = bp(D) since the minimum number of blocks of ones is the same in both cases. T h e d i f f e r en c e b e t we en co v e r s and par t i t i on s when looking at hlocks of ones in a matrix, still relates back to the definitions of both In a cover, an edge or arc can be in more than one biclique. This means that ones in the adjacency matrix may be in more one block. Since this is not allowed in a partition, each on e w i 11 b e found i n on 1 y on e b 1 o c k o f a b i c 1 i que part i t i on
PAGE 28
17 Covers and Partitions of Regular Digraphs 0 ne w a y o f n a r r ow i n g t he f i e 1 d for f i n d i n g be ( D ) and b+p(D) is to restrict D to being a kregular digraph. If every V of D has indegtee k and outdegree k, denoted id(v) and od(v), respectively, then Dis a kregular The adjacency matrix A(D) of a kregular digraph has k ones in each row and k ones in each co 1 u m n If a specific value for k is fixed a digraph can be found gives the minimum cover and partition numbers for kregular digraphs. A similar problem was first investigated for kregular graphs. A graph is kregular if every vertex has degree equal to k. Pullman and de Caen have results in clique coverings of regular graphs [7] and in clique of ieguiar graphs [6]. The earliest results for kregular digraphs came from Jones, Lundgren, and Maybee [13]. Let D(n,m) be the set of digraphs on n vertices which are mregular. ImportaMt theorems for the set of all mregular digraphs on n vertices in this paper include: (1) Theorem: Let q 2 be an arbitrary integer. (a) If q > 3, for each m 2, there exists an element D e: D{qm,2m) such that tip(D) = q. (b) If q = 2, for each m 2, there exists an element + D e: 0(2m,m) such that bp(D) = 2.
PAGE 29
18 (2) Theorem: If b+p(n,m) min for D D(n,m) and + n = qm, then bp(n,m) = q (3) Theorem: If b+p(n,m) ::min tJp(D) forD e: D(n,m) and + n = 2q+l, then bp(n,2) = q+2. A later paper bysarefoot, Jones, .Lundgren, and Maybee [2] further extended the theory of. kregular digraphs. This paper concentrated (n2)regular digraphs on n points. The following results were given: + ( 1 ) bc(2k,n2) = s(k). + (2) bp(2k,n2) = k. ( 3} + s(k1)+2. If n = 2k+ 1 > 9' then s(k+2) bc(n,n2) + (4) bp(2k+1,n2) = k+2. The adjacency matrix which corresponds to (1) and (2) above is in Figure 6. Each two rows or two columns of A ( 0) can be taken as a directed biclique in a partition of D Since r8(A(D)) = r8(Ik) = s(k) [11} (where Tk is the complement of the identity matrix), then b+c(D) = s(k). 00 l's DO DO A.( D) = DO 1's DO 00 Figure 6. An adjacency matrix of a digraph where + + bc(2k,n2) = s(k) and bp(2k,n2) = k. ;
PAGE 30
19 still more recently, be ( n, k) and bp (n, k) were .. solved 4 by Gregory et al. [10]. The results found in this paper are analogous to those found by Brualdi, Manber, and Ross [3] while investigating the minimum real rank of square binary kregular Barefoot et a 1 [ 2] found t he f o 11 ow in g b o u n d s for b+c ( n k ) and b+p ( n k ) : T he f o ll. o w i n g l emma g i v e s ex act v a 1 u e s fa r 0 ( n 1 ) an d O(n,2): Lemma: Far all n 1, bp(n,1) = bc(n,l) = n and for all n > 2 b+p ( n 2 ) = trc ( n 2 ) = J + 1 + ( 1 ) n + 1 Consider A(D) forD in D(n,l); it is easy to see why it will take n blacks to covet all of the ones. In A(D), eath raw and each column have a single nne, so the largest black is a 1 x 1. Since there are n ones, it will take n blocks and any cover must a partition. To understand the results for D(n,2), first consider n an even integer. The adjacency matrix of the digraph which gives the minimum cover and partition numbers would then be the complement of the matrix given in 6 (i.e., ones would become zeros, and the zeros would become ones), so will be 2 x 2 biocks of ones. Since n ( l) n+ 1 t. d + r n 1s even, 1s nega 1ve an bp = be = 1 making each
PAGE 31
20 of the 2 x 2 blocks a directed biclique in both a cover and partition. But what if n is odd? According to the lemma, directed bicliques would be needed. Let n = 2q+1, t h en J = q As s h 0 w n in F i g u r e 7 the f i r s t 2 ( q 1 ) r 0 w s and columns will contain q1 2 x 2 blocks of ones. The remaining three rows and columns must be 2regular. Since + + n bc(3,2) = bp(3,2) = 3, it wi.ll take q1+3 = L2J+2 directed bicliques to cover or partition a digraph of The following theorem gives exact values far + + bc(n,3) and bp(n,3): The are m : L e t s ( n ) = 0 i f n :: 0 ( mod 3 ) and s ( n ) = 3 otherwise. Then far all n > 3 + + n b c ( n 3) = b p ( n, 3) = L3J + s ( n) The ptaof of this theorem involves constructing a minimal example, then showing it is optimal. This construction, as well as those far D(n,l) and D(n,2), makes use of Jm an m x m submatrix of all ones. For 'm m < 4, construction of adjacency matrices which achieve + + the minimum values of bc(n,m) and bp(n,m) far their associated digraphs u s e as man y r ep 1 i c as a f J m as m, possible. In the ab6ve theorem, if n :: 0 (mad 3), say n = 3q, then q replicas of J 3 3 can be placed dawn the diagonal sa that they do nat intersect in any column or raw. Thus, there will be q bicliques. Far n
PAGE 32
'' : :!; 21 r 1 1 1 1 0 s 1 1 1 l 1 l l 1 O's 0 1 l : 1 0 1 1 1 0 J )' > :J. Figure An adjacency matrix of a digraph where r .....\.. bc(n,2) = for n odd. not congruent to 0 mod 3, q1 J3 3's can be used. This leaves either a DK4 or an element of "0(5,3) in the last four or five rows columns, Both have + + be = bp = 4. The results for are obtained similarly: Let s(n) = 0, 3, 2, or 4 according as n 0, 1, 2, or 3 (mod 4). Then foralln > 5, Theorem: .i ... b c ( n 4 ) = b"$ ( n 4 ) = L J + s (n ) bc(5,4) = 4, and b +p(5,4) = 5. The constructtons for these digraphs are analogous to those used in the previous theorem. The major problem
PAGE 33
22 with approach is that a casebycase study must be made regarding the size of possible blocks of ones, in order to show that the construction using Jm,m actuilly achieves a minimum valu' e for 6rc(n,m) and b+p(n,m). As m gets larger, the cases get even more tedious, and keeping track of all possibilities becomes an insurmountable task. There will be more di;;cussion of this problem in Chapter IV.
PAGE 34
CHAPTER I I DIRECTED BICLIQUE COVERS AND PARTITIONS OF THE COMPLEMENTS OF CYCLES AND PATHS IN A DIGRAPH Directed Bicligue Covers A natural extension of the work done by de Caen, Gregory, and Pullman [s] was to consider covers and partitions of complements of cycles and paths in a digraph. The results for directed biclique covers have published by Barefoot, Hefner, Jones, and Lundgren [1]. All work shown here that is not credited to a coauthor has been done solelf by Kim A. s. Hefner. Let D be a complete digraph on n vertices minus n the arcs of an ncycle, and A(D ) be the adjacency matrix n associated with on. D can be labeled so that A(D ) is n n an n x n ( 0 ,1 ) .mat r i x w i t h z e r o s on the d i ago n a 1 superdiagonal, and at a l (see Figure 8). We then define n' to be a complete digraph pn n vertices the arcs of an npath, with as its adjacen6y matrix. be labeled so that A(D*) is an n x n (0,1)matrix with n zeros on the diagonal and the superdiagonal (see Figure9). It is often easiest to find blocks of ones in the adjacency matrix rather than the directed bicliques in a digraph.
PAGE 35
24 A matrix is less congested, and can be entered into a computer to obtain empirical results. 0 0 1 l 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 A(Dn) = .. 1 1 1 1 1 0 0 0 1 1 1 1 1 0 Figure 8. A(Dn). 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 = 1 1 l l l 0 0 1 l 1 1 l ... 1 0 Figure 9. A general directed biclique covering is not difficult to find. However, finding the minimal covering is somewhat elusive. This makes desirable to fit the digraph into a form where it is possible to use the existing theorems relating to clique coverings of graphs.
PAGE 36
25 First, we will examine the process relating On to the complemeht of a cycle in a graph, E2n. Consider A(On) without the labeling acquired from on. In 'this form, it can be seen as an adjacency matrix for a bipartite graph & on 2n vertices, as shown in Chapter I, section 3. A(B2 n) can relabeled so that X= {1,3, ,2nl} and Y = {2,4, ,2n}. This labeling results in the following matrix: 2n 2 4 2n2 1 0 0 1 3 1 0 0 1's 5 1 1 0 0 A(B2n) = 1's 0 2n1 0 1 1 1 0 Figure 10. A(B2n). The choice of labeling the columns beginning with 2n is arbitrary. However, this labeling provides a cycle where (v 1,v2 n) does not exist in s2n. On has no loops (i.e., ( v i ; vi ) is not an arc ) so there are z e r cis down the d i ago n a l. The other zeios result from the removal of a cycle. The corresponding cycle which removed from s2 n with the given labeling is shown in Figure 11. The cycle is: 1,(1,2),2,(2,3),3,(3,4), ,(2nl,2n),2n,(2n,l),1.
PAGE 37
26 X y 1 2 3 4 5 6 2nl 2n Figure 11. The bipartite associated with on. Each edge in s 2 n corresponds to an arc in On Therefore, complete bipartite subgraphs (bicliques) in s 2 n correspond to directed in on. Thus, a biclique for s 2 n is a directed biclique covering for On, so However, s 2 is not the complement of n a cycle in' a graph, so we cannot use the methods employed by de Caen, Gregory, and Pullman [s] to generate a clique covering for the complement of a cycle. This can be restricted by adding all of the edges in X and Y so that i and Y are complete subgraphs of a new graph s;n. s;n has the following properties: 1. s;ri = c2n' Property 2 was first observed by Gregory and Pullman (personal communications). It follows from examining the + values of bc(On) obtained from the constructions of minimum clique cdverings of E2n. listed below. The three possibilities are
PAGE 38
27 1. If there exists a minimum cardinality cover of E 2 n with two cliques of the form c 1 = {xm: 0 < m n, xm E: X} and c. = {y : 0 < m < n, y E: Y}, then J m m + bc(Dn) = 2. If there exists a minimum cardinality cover of c 2 n w i t h one c 1 iq u e o f the f o r m C = { x : 0 < m < n x m E: X l l. m or c.= {y: 0 < m < n, y E: Y} and no minimum J m m cardinality cover asin (1), = ccCc2nJ1. 3. If there are no cliques in any minimum cardinality cover of c 2 n such as ci and cj defined above, then + bc(Dn) = cc(E2n). With the digraph problem expressed graph theoretically, use can be made of the following theorem. De Caen, Gregory, and P0llman [s] have expressed it in its current and its roots go back to ErdBs, Goodman, and P6sa [a] as well as [21,22]. Theorem: G is the intersection graph of a sequence T of subsets of a kset if and if G has a clique covering with k oi fewer This theorem allows us to find the c 1 ique covering number of c 2 n by generating all 2nsequences of subsets. using the smallest kset possible. The problem of generating these sequences is NPcomplete. In addition, + since the relationship between bc(D ) and cc(c2 ) depends n n upon the nature of a minimal cardinality cover, we must
PAGE 39
' 28 e x ami n e e v e r y 2 ri : s e q u en c e g e n e r at e d for a f i x e d n in o r d e r .to ascertain the directed biclique covering number. This is due to the that the clique covering of c2n may be in all or some of the ways listed on the previous page. If only one sequence is examined, it is unknown whether sequence exists which generates a covering of 8 2 using a fewer number of bicliques. n + Therefore, to obtain an exact value for bc(Dn)' a method is needed which will eliminate all but one of the possibilities when a sequence is ;;: To achieve.this, let C be a clique covering of f2 n the c. E c have the following restrictions: ]. l. For some ex, c = {X : for 0 ex 1 < i < n, X. E X}; and :1. 2. For some B, c B = { y. : for 0 1 < i < n, y. E Y}. 1 With these restrictions, the other cliques form the biclique covering of 8 2 Thus, the corresponding directed n bicliques cover on. We now define c"'c(G) = k to be the minimum k for. which there exists a clique cover of cardinality k containing Ccx and c6 This to the following theorem. Theorem 2.1.1: Pro a f: 8 2 n can be covered with c"c Cc2n) 2 bicl iques by + c c (c2n) 2. not using c and cs, so bc(Dn) < Now, there ex + cc Cc2n); are three possibilities: (i) bc(Dn) = or + cc(c2 n) 1; + (ii) bc(D ) = or (iii) bc(D ) = cc(C )2. n n 2n
PAGE 40
29 Case i: cc(c2n), so neither Ca nor Cs exists in a minimum cover of c 2 n. c"c ( c2 n) cc ( c 2 n )+2 = ..... bc(Dn)+2, so cc(E2n)2 bc(Dn). Case ii: bc(Dn) = tc(c2n)1, so either Ca or CB exists in a minimum cover of E 2 n c c ( C 2 n ) c c Cc 2 n ) + 1 = r ..... bc(Dn)+2, so cc(C2n)2 bc(Dn). Case iii: (on) = ccCc 2 n) 2, so both ca and cB ex i s t in a m in i mum c o v e r o f C 2 n C'c (c 2 n) c c ( C 2 n ) = + ..... + bc(Dn)+2, so cc(c2 n) bc(Dn)+2. Therefore, = cc(C2n)2. [] To fotm a sequence of length 2n for which c2 n is t he in t e r s e c t ion g r a ph 1 e t F i b e sub s e t s o f a s e t T f o r i = 1, ,2n. Since complements of _cycles are intersection graphs of cyclirially disjoint Chapter I, Section 2), we want [F 1 ... F 2n] to be cyclically disjoint. Table 2 shows the relationships between elements in the digraph, the graph, and the sequeAce of subsets. In a construction similar to that of D n' n can be obtained from a 2nsequence on a kset. A relabeling of A(D*) is possible (see Figure 12) so that the matrix n graph on 2n vertices. Again, the labeling of the rows and columns is so that the zeros represent a path which is easy to identify (see Figure 13). By completing subgraphs X andY, as for e2n, we obtain a graph which is the complement of a path on
PAGE 41
l. F2i' l. The clique . Clique covering of c2n" Set (2risequence) Evennumbered subsets. Oddnumbered subsets. For xe:F1 xe: { 1, ... k}. a. e: F 21 _1 f o r l
PAGE 42
2n1 2n3 A (Bin) = 3 1 2n 2n2 0 0 1 0 1's 1 1 Figure 12. X 1 3 5 1 0 1 A(B2n). y 2 4 6 2n1 o== 10 2n 31 4 2 1, s 0 0 1 0 Figure 13. The graph associated with 2n verticies, P 2n. The following theorem is a direct result from Theorem 2.1.1 and its proof. To obtain cc CP' 2 n) a 2ns equence of subsets on a must be such that is the intersection graph of that sequence. Since is the intersection
PAGE 43
32 graph of a consecutively disjoint sequence, we want [F 1 .. ,F2 n] to be consecutively disjoiht. The actual construction of these biclique coverings by generating 2nsequences will be examined after the theoretical r esu 1 t s, where exact values of ( D n ) an d b c ( D ) a r e p r e s en t e d f o r s om e n All graphs c2 n and P2 n which have been constructed from A(Dn) and respectively, have an even number of vertices. As a result, the theorems obtained by de Caen, Gregory, and Pullman [s] need to be modified to use with an even number of vertices and to account for using c c rather than cc. The next theorem is a modification of their Th.eorem 3 .1. Most of these results can be proven directly using biclique covers of the digraphs; but for the mast part, the fallowing proofs are much more compact. They take a given cycilically or consecutively disjoint 2n sequence. By using new elements augmented by the existing longer sequences are which are cyclically or consecutively disjoint as needed. The proofs used in [s] have served as an inspiration and sometimes a template for the proofs in Theorems 2.1.3 and 2.1.6. The use of cc in proofs results in an element CL ir:i every odd subset. and an element 8 f CL in all even subsets of a 2nsequence. Thus, CCL is the complete graph using all vertices in X, arid c8 is the complete graph using all vertices in Y. All other bicliques cover s2n.
PAGE 44
33 Theorem 2.1.3: The following statements are true for n > 1: 1. ccC'P 2n) < ccCP"2 n+ 2); 2. cc(P2n+2) < c"c(P 2n) + 1, n I 2. ' 3. cc c c2n+2) < ccCF' 2n)+2, n > 2 ' 4. ccCc4n) < c0c ( P 2n+2) +2; 5 ccCc4n+2) < c"c (P 2 n+ 2 ) +2. Proof: To. prove l, since is an subgraph of on 2n vertices. it follows that, at most, the cover for 2 n + 2 w i 11 also cover P 2 n Thus c c ( P 2 n ) c" c ( P 2 ri + 2 ) To prove 2, let [F 1 ,F2 n] be a consecutively disjoint 2nsequence of subsets of a set T of k = elements where a,b T and a F 2 1 b F 2 for 1 < i < n. ll Let x i T, then [F 2U{x},Fl'F2,F3U{x},F4,F5 ,F2n3 is a consecutively disjoint 2n+2sequencie on a k+1set, where b F 2il' F21 for 1 < i < n+l. If n = 2, these subsets do not represent a cover o f P 6 because c"c ( P 6 ) c c ( P 4 ) + 2 So cc(P2n+2) < cc(P2n)+l n I 2. ro prove 3, let [F 1 ,F2 n] be a consecutively d i s j o i n t 2 ns e que n ce o f s u b s e t s on a s e t T o f k = cc ( P 2 n ) el em en t s w he r e a b T and a E F 2 1 ... 1 b E F 2 1 f o r 1 i n For n i and x,y iT, then F 2 n 1 U { x } 'F 2 n { a } U { Y } { b } U { x } J is a c y c 1 i c a 11 y d i s j o in t on a k+2set a E F 21 1 and b F 2 i for l < i < n+l. Thus, cc(C2 n+ 2 ) < cc(P2n)+2.
PAGE 45
34 To prove 4, let [F 1 .. ,F 2n+2 ] be a consecutively disjoint 2n+2sequence of subsets on a set T of k = A elements where a,b E T and a E b E F 2 i for 1 i < n+l. For n >land x,y iT, then F 4 U{x}, ,F 2n+1 U{y},F 2n+2,F2n+1 U{x}, .. ,F4 U{y},F 3 U{x}] is a cyclically disjoint 4nsequence on a k+2set where b E F2i1' a E F2i for 1 < i < 2n. Therefore, cc(C4n) < cc ( 2 n + 2 ) + 2 To p r o v e 5 1 e t [ F 1 F 2 n + 2 ] b e a con s e cut i v e 1 y disjoint 2n+2sequence of subsets on a set T of k = c"'c(P2n+2 } elements where a,b e Tand a e F 2il' b E: F 2 i for 1 < i < n+L Fat n :> 1 and x,y i T, then [F1 ,F 2 U{x},F 3 U{y}, ... ,F2 nU{x},F 2n+lU{y},F2 n+Z'FZn+ 1u{x}, ,F2U{y8 is a cyclically disjoint 4n+2sequence on a where a E: F21_ 1 b E: F 2 i for 1 < i < 2n+1. So, c"c(c 4n+2 ) cc("P 2n+2)+2. [] The ultimate quest is what results imply for the digraphs D and o*. Because of the. equality in n .. n Theorems 2.1.1 and 2.1.2, the following corollary is a direct consequence of the previous theorem. 2.1.4: The following statements are true fat n > .l: + + 1. bc(o*) bc(Dn+l);, n 2. + I bc(Dn+l) < n 2 , + 3. bc(Dn+1 ) < n > 2.
PAGE 46
35 4. s. The first two results give monotonicity for b+c with the difference in the values bel. ng at mast one T h i s has 1 e d t o a c on j e c t u r e that b+c ( D n ) tJ c ( D n + 1 ) Considerable computational results supporting this conjecture will be presented later in this section, but as of yet, no one has been able to it. The following lemma gives an additional restriction on the construction of a cyclically disjoint sequence. Lemma 2. 1. 5: I f C 2 n i s t he in t e r s ec t i on g r a p h o f a cyclically disjoint 2nsequence [F 1 ,F2n], then j for any i,j = 1, .. ,2n, i .j j, and n > 3. Proof: Let c2 n be the complement of a cycle on 2n vertices and [F1 ,F2n] be a cyclically a set T of k ::: c"c(c 2n) elements. disjoint 2nsequence on Consider two subsets F. l and Fj of the sequence which represent vertices i and j, respectively, in c2n. If n 3, there exist at least two edges (i,x) and (j,y) in c2n such that (i,y) and (j,x) are not in c2n. So, (i,x) and (j,y) must be covered in cliques Cf and c respBctively, f,g e: T and fIg. g Thus, f e: F 1 while f i Fj, and g e: Fj but g iFi. Therefore, F i t... F j for any i' j = 1' '2n' i I j' and n > 3. []
PAGE 47
36 The above lemma not apply to consecutively disjoint sequences. In vertices 1 and 2n have n1 edges the other vertices have n2 edges each. This results in Vertex 1 adjacent to all of the vertices vertex 3 is adjacent to, plus the additional vertex 4 The same can be said about vertices 2n and 2n2. Therefore, it is possible that F 3c F 1 and F 2 n_ 2 c F 2n. Results which help bound cc(P2n) and c"'c(c 2n) are found in the following Theorem 2.1.6: The following statements are true for n > 1: 1. cc(P4n) < cc(P2 n+ 2)+2; 2. cc(P2n) < c"'c (c2n) n I 2. ' 3. cc(C2n) < c"'c ( P 2 n) + 1 ; 4. cc (C 4n) < cc( +2; 5. c"'c (C4n+2) < cc (c2n+2 ) +2, n > 2 ; 6. ccCc2n) < cc(c2n+2)+1; 7. c"'c (C2n .+2) < cc (C2n) +2, n I 2; 8. .. c"'c(P 4n+2) < c"'c ( P 2n+2) + 2 Proof: To prove 1, let [F 1 ,F2n+2 ] be a consecutively disjoint 2n+2sequence of subsets on a set T of k = c"'c(P 2 n+ 2 ) elements where a,b E T and a E F 2il' b E F 2 i for 1 < i < n+1. For n > 1 and x,y i T, then [F 1,F2U{x},F3U{y}, .. ,F2nu{x},F2 n+ 1U{y},F2 n+ 2,F2 n+ 1u{x}, .. F 4 U{y}] is a consecutively disjoint 4nsequence on
PAGE 48
37 a k+2set where a F 2il' b F 2 i for l < i < 2n. Thus, c"c(P4n) cc(P2 n+ 2)+2. To prove 2, let [F 1 ,F2n] be a cyclically d i s j o i n t 2 ns e q u en c e o f s u b s e t s on a s e t T o f k = c"c ( c 2 n ) e 1 em en t s where a b T and a F 2 i 1 b F 2 i for 1 ..s_ i n By 2.1.5, there exists an x T such that x F 1 and X i F2n1 for n > 3. So (F 1' ,F2n1'F2nU{x}] .is a consecutively disjoint 2nsequence on a kset where a F2i1' b F2i for 1 < i < n when n > 3. When n = 1 there are no edges between X and Y in c 2 n and P 2n' so = cc(C2n) = 2 Therefore, c"c(P2n) c"c(C2n) for n t 2. To ptove 3, let be a consecutively disjoint 2nsequence of subsets on a set T of k = c"c{P 2n) e 1 em en t s where a b T and a F 2 i 1 b F 2i for 1 i ..s_ n F 1 n F 2 n = { a1 a p } = Z f o r some p Sin c e b F 2 n an d b i F 1 then F 2nZ t So, for n 1 and x i T, then [F 1,F2,F3U{x},F4,F5U{x}, is a cyclically disjoint 2nsequence on a k+1set .where a F 2i_1 b F 2 i for 1 < i < n. So, c "c(c2n) ..s_ c "c(P2n)+l. To prove 4, we use Theorems 2w1.3(4) and 2.1.6(2) to obtain c"c(c4n) < c"c(P 2 n+2)+2 < c "c(c2 n+ 2)+2 for n 1. Similarly 5, Theorems 2.1.3(5) and 2.1.6(2) g i v e cc ( c 4 n + 2 ) ..s_ c" c ( P 2 n+ 2 ) + 2 ..s_ c" c Cc 2 n + 2 ) + 2 for n > 2
PAGE 49
38 For 6, Thenrems 2.1.6(3), 2.1.3(1), and 2.1.6(2) give c"c(c 2 n } cc(P2n)+l cc(P2n+2 )+1 c "c(c2n+2 )+1 for n > 1. To prove 7, we use theorems 2.1.3(3) and 2.1.6(2) to obtain cc(c2n+2 ) c"c(P2 n)+2 cc(c2n)+2 for n > 3. For n = 1 cc C c 4 ) = c c (c 2 ) = o ; but when n = 2 c c (c 6 ) = 3 = c c (E 4 ) + 3 T h u s c"'c Cc 2 n + 2 ) c c Cc 2 n ) + 2 f o r n J 2 Finally, 8 follows from Theorems 2 .1. 6 (2) and 2.1.3(5) giving c"'c(P4n+2 ) < cc(C4n+2 ) cc(P2n+2 )+2 for n 0 Again, from Theorems 2.1.1 Bnd 2.1.2 we directly Dbtain the following corollary which .relates the previous theorem to biclique covering numbers. Corollary 2.1.7: The following statements are true for n > 1: 1. + + be co211) < bc(On+l)+2; 2. be < be ( 0 ) n .J 2; n + bcCo*J+l; 3. bc(On) < n + + 4. bc(D2 n) bc(On+l)+2; + + 5. bc(02n+l) bc(On+ 1)+2, n > 2; + + 6. bc(On) bc(On+l)+1; + + I 7. bc(On+l) < bc(D )+2, n 2; n 8. + bc(02n+1) + bc(On+ 1)+2.
PAGE 50
39 Results from Corollaries 2.1.4 2.1.7 will be used together with computational results to obtain logarithmic upper bounds for bc(Dn) and To conclude the list of theoretic results, Richard Lundgren proved the following theorem. It is stated in terms of directed biclique cover numbers since the proof relies on theorems which apply to the adjacency matrices of the digraphs. This theorem glves a lower bound for + ) + *) bc(Dn and bc(Dn First, s(n) is defined as in Chapter I, section 4. Further, an n x m nonnegative matriK X is said to have row if and only if for some i f j : xik f 0 implies xjk f 0 for xik and xjk elements of X, and + 1 < k < m. Recall that bc(D) = r8(A(D)), the Boolean rank of A. Theorem 2.1.8; The following statements are true: 1. 2. + bc(Dn) > s(n); + bc(o*) > s(n1). n Proof: To prove 1, we use Corollary 1 of de Caen, Gregory, and Pullman (4]. Let A(Dn) be the adjacency matrix associated with on A(Dn) is without row containment, so + by Corollary 1, bc(D ) > n To prove 2, let be the (n1) x n submatrix of A(On) consisting of the first rows of A(On). Then is without row containment. So, by 1 [ 4],
PAGE 51
. .: ; :, .,.,;. 40 .:.. r 8 (A") > s(n..:l). Also: r 8(A(D)) > r 8 (A"rby a result o f G r e g o r y and Pullman '[6] T h u s l:tc ( 0 ) s ( n l ) [] It is clear from the previous theorems that the bounds on c "c(Dn) and are not quite sharp enough t o o b t a in exact r e s u lt s T her e f o r e i t has b e en n e c e s s a r y to acquire exact values for some n by seeking the assistanc: e of computers. The problem of generating the longest 2nsequence of subsetsbn kset has proven to bB very timeconsumirig, even with computer assistance, so exact results are still limited. ,.. The goal has been to generate the longest cyclically disjoint and cnnsecutively disjoint u s i n g e l em e n t s { 1 k } vi h e r e a b E: { l k } a n d a11 i s in every oddnumbered s .ubset while "b: is in every evennumbered subset. This enabled the best possible cover to be obtained without generating every sequehce of length 2n on a kset in order to compare the res.ul ts. The smallest k for which a 2risequence is generated will be .the k such that bc(Dn) = k2 _or = k2. A program to do this was written in Fortran, an iterative language. However, constructing a sequence of subsets requires the recursion of trying different sequences until one_works. I owe many thanks to Curtiss Barefoot for the part bf the program which forces iterative language to handle recursion. The was run on both scalar and vector computers. It proved tn
PAGE 52
41 be highly vector i zab le in a 11 but the recur si ve portion of its code. Sequences of length ten through twenty (even only) were generated using all possible sizes of subsets. As the sequences became longer, an unacceptable amount of computer time was being used11unacceptable11 meaning: (1) hours of supercomputer time were being used to generate one sequence; and (2) system operators take a dim view of a:nyone using that amount of time on their machine. This being the a conjecture ai to the optimal size of the F i had to be made. Fortunately, all of the sequences between. lengths ten and twenty showed the same patterns, depending on k. The following, then, are the restrictions on the size of the Fi based on empirical data: 1. For cyclically disjoint 2nsequences, the optimal size for Fi is: a. (k1)/2 for every subset, for k odd; b. k/2 alternating with (k/2)1, for k even. 2. For consecutively disjoint 2nsequences, the optimal size for Fi is: a. (k1)/2 for [F 1 ... ,F2n_1 ] and ((k1)/2)+1 for F 2n, for k odd; b. k/2 a:lternating with (k/2)1 for [Fl' ,F2n_1 } with k/2 fOr F 2n' for k even. The proof of this conjecture has been dlfficult to produce, even though it need only be shown that there exists such a sequence using a minimum k. A similar conjecture is ''.
PAGE 53
42 made by de Caen, Gregory, and Pullman [s] regarding the size of used in cc(c2 n) and cc(P2n), and is shown in I, section 2. The first 20sequence which could be generated required k = 9 (shown below). Elements 1 and 5 alternate. So f o r t h is ex amp le we h a v e c c ( C 2 0 ) = 9 an d be ( 0 1 0 ) = 7 15121314141 2735452525 3 3 8 4 8 a 6 8 3 6 1 4 9 6 9 7 9 7 9 7 9 8 2 3 5 4 5 6 7 6 9 a 9 1 2 4 8 3 5 6 7 4 B 9 2 5 6 7 1 3 4 9 5 6 7 B Each subset Fi represents vertex i in c 20 and a vertex w i t h in com i n g or o u t go in g arcs in 0 1 0 The elements {1, .. ,9} are the indices of the cliques which cover c 20 and o10 The cliques for a cc covering of c20 are: c 1 = {1t3,5)7,9,11,13,15,17,19} which covers X; c 2 = {1,4,7,9,12,15,18}; c 3 = {1,3,6,9,11,14,16,19}; c 4 = {1,3,5,8,10,13,15,17,19}; c 5 = {2,4,6,8,10,12,14,16,18,20}, which covers Y; c 6 = {3,5,7,10,12,14,16,18,20}; c7 = {2,5,7,9,11,13,16,18,20}; c8 = {2,4,6,8,11,13,15,17,20}; c9 = {2,4,6,8,10,12,14,17,19}.
PAGE 54
43 Cliques one and five play no part in covering o10 Therefore, we have the following bicliques in the directed biclique covering of o10 : 82 = {1,7,9,15} + {4,12,18}; 83 = {1,3,9,11,19} + {6,14,16}; 84 = {1,3,5,13,15,17,19} + 86 = + {10,12,14,16,18,20}; 87 = {5,j,9,11,13} + {2,16,18,20}; 8 8 = {11,13,15,17} + {2,4,6,8,20}; 89 {17,19} + {2,4,6,8,10,12,14}. In comparison, below is listed a consecutively disjoint on an 8set where elements 1 and 5 alternate. Her e we h a v e c c (P 2 0 ) = 8 and be ( 0 i 0 ) = 6 T h i s is one o f the apparently few places where /. 1 5 1 2 l 3 1 4 1 4 1 2 1 3 1 3 l 4 l 2 2 7 3 5 4 5 2 5 2 5 3 5 4 5 2 5 2 5 3 4 3 8 4 8 6 8 6 8 3 6 7 6 7 6 4 7 6 7 6 5 4 6 7 7 7 8 8 8 8 8 7 Cliques and directed bicliques for the coverings of p20 and 0 10 are obtained in a similar fashion to that of c2o and 01o Computergenerated .sequences using our conjecture on subset size have yielded the values in Table 3.
PAGE 55
n s(n) Table 3 Values for s(n), b+c(On) and for n = 1, ,53 2 3 4 56 79 10 1120 21 2232 33 3435 2 3 4 4 5 5 6 7 7 7 7 1 3 4 5 6 6 7 7 8 8 9 bc(onJ o 3 4 5 6 7 7 7 B 9 9 44 3653 8 9 9 These results. Richard Lundgren to obtain the following upper bounds for Theorem 2.1.9: 2Llog2 (n2)J, n > 18. Proof: Inequalities 2.1.7(1) and 2.1.7(8) in conjunction with computed values give: be < 8, for 18 < n < 33; be < 10, for 34 < n < 65; be < 12, for. 66 < n < 129. Using these values and theorems, < 2Llog2 (n2)J. [] The major problems which are still unsolved for this area are: 1 I s be ( oil ) mono t on ic a 11 y n o n d e c r e as i n g? 2 0 o e s a s e que n c e o f s u b s e t s e x i s t us i n g k e 1 em en t s such that k = cc("C'2 n) and IFil is as conjectured? 3. The same question as number 2, .but for cc(P2n).
PAGE 56
45 4. If existence can be proved for numbers 2 and 3, can an integer programming problem be instituted which will find the optimal k for a given sequence length? + + 5. What are the .exact values for bc(Dn) and for all n? The problem of monotonicity is a tricky one in + the case of bc(Dn). It is desirable to be able to use a proof by induction in this case. However, a proof by induction does not work for any characteristic of on. This stems from the fact that On does not have the hereditary property. A digraph D has the hereditary property if, whenever we take away an arbitrary number of vertices and their incident arcs, the resulting digraph has the same charactaristics as D. If we take away any m vertices and their incident arcs from On to obtain D ... D ... is not the complement of a cycle. In an induction pro6f, it is important to be able to compare a digraph Dk+l to one with fewer vertices, Dk, and use the induction hypothesis. But removing a .vertex from Dk+l does not give Dk' so induction fails. Yet, monotonicity is something I would like to prove in the future. Directed Bicligue Partitions The discussion of directed biclique partitions + w i 11 c e n t e r ar o u n d b p ( D n ) T o u n d e r s t and t he con j e c t u r e s and the current open problem, the relationship bp(D) and the real rank of A(D), rR(A(D)), must be examined.
PAGE 57
46 As shown in Chapter I r + ( A ( 0 ) ) = tfp ( 0 ) I f A C 0) can z be separated into k matrices of rank one which sum to A(O), and the elements of these rankone matrices are nonnegative integers, k is an upper bound for rR(A(O)). It is possible that fewer than k rankone matrices will be needed (whose sum is A(O)) if all real numbers are allowed as elements. Therefore: rR(A) < r +(A). z Cases where equality hold can be found in [10] and with strict inequality in [11]. The above relationship gives a lower bound on r Z + ( A ( 0 n ) ) an d s o on bp ( 0 n ) T he up p e r b o u n d i s n s i n c e bicliques using entire rows or columns can be used. When n is odd, rR(A(OnJ) = n [13]. So, b+p(On) = n for n odd. + bp(On) = n is also conjectured when n is even. How e v e r ; r R ( A ( 0 n ) ) = ni in t h is c as e [ 1 3] So i t m u s t be shown that either a partition using n1 directed bicliques exists, or prove that it cannot. In attempting to show that the conjecture is true, I tried to see what would happen if any directed biclique were remov ed. I used a program writ ten by Bi 11 Cheraw i tzo to remove blocks of ones and then to take the real rank of the remaining matrix. Whenever an odd x odd block was removed, the real rank of the new matrix went upton. In the following lemma, it is shown that the real rank of
PAGE 58
47 the matrix obtained by removing a 1 x k block of ones will have real rank of at least n1. Lemm$ 2.2.1: Let On be the of a cycle on n vertices, and B be a 1 x k directed biclique of On. If A(O B) is the adjacency obtained from the arcs of n on minus those of B, then rR(A(OnB)) > n1. Proof: A(O B) has only one row or column where ones n have been replaced by zeros. So, A(O* 1 ) is a submatrix nof this matrix. Since = n1 [13], then [] This lemma tells us that if any biclique partition can be found using n1 directed it will not have a 1 x k directed biclique. If we took out a 1 X k directed biclique, rR(A(OnB)) n1 implies r +(A(D B)) > n1, so at leait n1 moie bicliques would Z n be needed to cover the remaining arcs. The data support the conjecture that ariy directed biclique partition of On for n even will not have an odd x odd directed biclique in it. A characteristic of on for n even is if the rows of A(On) are added using mod 2 addition, the result is the ndimensional zero vector. If odd X odd blocks of ones are eliminated from consideration in mod 2 addition of the row s W i 11 n o t g i v e the z e r o v e c t or I f mod 2 ad d i t i on can be substituted for ieal linear combinitions rif the rows,
PAGE 59
48 n this would imply that for .l 1.=1 a.r. (where r. is the ith 1 1 1 row), a. = O,l,1 are the only possibilities. This is 1 definitely nbt the case in a general (0,1)matrix, but may be true in Dn. Similarly, empirical data show that whenever an odrl x even or even x odd block of ones is from If mod 2 addition can be substituted for linear combinations of rows, this case tan also be proved true. This would further the cases in the search for a directed biclique partition using n1 directed bicliques. If rR(A(OnB)) = n1" when an even x odd block of ones, B, is removed, since rR(A(DnB)} rz+(A{DnB)), it would take at least n1 more bicliques for a partition of the remaining ones. Thus, any directed biclique partition for D when n is n even could have only even x even directed bicliques. + Even though bp(Dn) has not been determined in general n even, we have the followirig result. + The o r em 2 2 2 : b p ( D 6 ) = 6 + Proof: suppose b p ( 06 ) = 5 Then, by the discussion following Lemma 2.2.1, o6 cannot have a 1 x k directed biclique (claw). The largest directed biclique possible has size 2 x 3. If the 2 x 3 is used, the eighteen :remaining arcs must be partitioned by four bicliques. At least one of these bicliques must contain more than
PAGE 60
49 = 4 arcs. Thus, another 2 X 3 or 3 X 2 is needed. 4 This leaves three bicliques to partition twelve arcs, so must all be 2 x 2's since no 1 x k's are allbwed. But there are at least two isolated ones in the rows or columns of the 2 x 3's, since three of the four ones are already partitioned. So, these ones must go into claws. Therefore, no partition using five bicliques exists if a 2 x 3 is used. Suppose, then, a 2 x 2 is the largest biclique. It takes = 6 of these to partition the arcs of. o6 + Therefore, bp(06 ) = 6. [] + Since the determination of bp(On) still remains a mystery for n even and greater than 6, it is desirable to have the computer do some of the work of computation. in section it was Shown that sequences of subsets could be .generated to obtain tovers of on. Here, new constraints can be added which give a minimum directed biclique partition. Previously, it was possibile that an evennumbered subset and an odd:numbered subset had two elements in common. This forced the associated edge in B 2 n to be in two bitliques, which in turn represented an arc of on in two directed bicliques. The following constraint is thus mandated: If a pair of e.lements occurs in a subset F2i+l' then it cannot occur. in a subset numbered F2j+2 for i j = 0 ... n i A 1 on g w i t h t he r e s t r i c t i on s t h at
PAGE 61
50 Fin Fi+l i n1, and F 1 n Fn = sequences generated using these rules will give a partition of On. Of course, it is best if not every needs to be generated. Therefore, we define c"p(C2n) which is analogous to c"c(c2n). Definition: A c"p cover of a graph H = (X,Y,E) where X and Y are disjoint sets of vertices which compriseall of the vertices of H, and and are complite subgraphs of _H, is a clique cover of H such that: 1. Ca and c8 which cover the complete graphs X andY of H, respettively, are in the cover; and 2. No pair of vertices, x & X and y E Y, appear in more than one clique together. The minimum number of cliques in a c"p cover of H is defined to be c"p(H) = k. For all applications of these definitions, the set X will consist of integers and Y will consist of evennumbered integers. A A cp cover is not a clique partition of H because Ca and c8 will cover edges must be included in any othet clique size greater than two in the cover. So, in H, some edges in X and Y may be included ln more than one clique. The added restriction of no odd and even pair occurring in more than one clique forces the partition of the edges between X and Y. + Theorem 2.2.4: bp(Dn) = c"p(c 2n)2.
PAGE 62
51 Proof: 1. Let C be a minimum biclique partition of s2n. Since bp(D ) = bp(B 2 }, the same of directed bicliques n n will partition On. Add the edges between X and Y for each biclique s2n. These may not be all of the edges in c2n. I So' let ca and CB be ad qed to cover the edges just! added and those which may need to be ad d e d t o c o mp 1 e t e c 2 n so b+p ( on ) = b.p ( B 2 n ) c p Cc 2 n') 2 2. Let c be a mit imum cP cover of c2n. Since no two cliques of c tas a repeated pair of odd and even I integers, then\ no edge between X and Y is in more than one clique. Because every is in at least one clique, edge X and Y is in exactly one clique cj and c6 are not used in the partition of s2n' so the cliques will be used in that partition. This, b+p(Dn) = bp(B2nl c[l(c2n)2. There fore, bJ; (On) 1 c'p (C2nl [] FolloWing ]s an example of a sequence of subsets I which was generated to provide a partition for o 6 I F 1 1 2 3 F3 F4 F5 F6 1 5 1 2 3 7 4 6 8 5 2 6 F 8 5 2 8 1 4 6 c1 and c5 cover X anr Y of c12 respectively. no pair in an evennumbered subset occurs Fl2 s 4 7 Notice that in an oddnumbered subset. However, notice that the pair 5,6 occurs
PAGE 63
52 in three evennumbered subsets: F 2 F 4 and F 6 Therefore, edges (2,4), (2,6), and (4,6) are in cliques c5 and c6 This creates a cover for edges in X and edges in Y. Since these are not involved in 812 or o6 the bicliques formed from c2 c3 c4 c6 c7 and c8 will partition the edges. Following are the bicliques: 82 = {1,3} + {6,8,10}; 83 = {1,7} + {4}; 84 = {3 '9} + {12}; 86 = {9,11} + {2,4,6}; 87 = {5,7} + {2,10,12}; 88 = {5,11} + {8}. + cp(c2n)2. No arc is covered twice; and bp(D6 ) = 6 = This result can be extended for use in determining the directed biclique partition number of It follows directly from Theorem 2.2.4. Theorem 2.2.5: = c"p(P2n)2. Using Theorems 2.2.4 and 2.2.5, cyclically or consecutively disjoint sequences of subsets genera ted using t h e smallest number of elements w i 11 give cp Cc2 n J and c p ( P 2 n ) T h u s com put e r s c an genera t e the s e s e que n c e s + to find bp(On). Not only does this concept work for on and but a more general theorem can be designed.to find i)c(D) and
PAGE 64
53 + b p ( o ) f o r an arb it r a r y d i g r a ph 0 F i r s t 1 e t o b e an arb i t r a :j:' y d i g r a ph an d B 0 b e t h e b i p a r t i te g r a p h s u c h that A(O) = A(B0). Then let G 0 be the graph obtained by making graphs of X and Y in s0 The following theorems then hold. Theorem 2.2.6: bc(O) = cc(G0)2. Proof: 1. Let 0 be an arbitrary digraph, and c be a minimum biclique cover of s0 By making the bicliques of c into complete graphs, at best, these complete graphs will cover the of G 0 If not, ca and c8 are needed in add it ion to cover the edges of G 0 So + "' bc(O) = bc(B 0 ) cc(G 0)2. 2. Let c be the minimum cover of G 0 such that Ca and c8 exist. Then it takes at most the other cliques to + "' c o v e r the e d g e s o f B 0 Thus, b c ( 0 ) = b c ( B 0 ) c c ( G 0 ) 2 Therefore, bc(B 0 ) = cc(G0)2. [] + "' Theorem 2.2.7: bp(O) = cp(G0)2. These theorems do solve the problem of + + determining bc(O) and bp(D), but they do make it possible to start gathering empirical data. Not only can sequences be generated, but as soon as one is, we know it is the best It will be the best possible, given that the sequence is generated with the minimum number of
PAGE 65
54 elements. When a sequence is generated for the first time using cc(G 0 ) = k elements (and cannot be generated using less than k elements) or cp(G 0 ) = k elements, src ( 0) = k2 or bp (D) = k2. There is no longer any need to generate every possible cover or partition in order to find the one using the least number of directed bicliques. In the case of an arbitrary digraph, D, F i n F j = llf if edge (vi' v j) is not in G 0 All oddnumbered sets must still since X is a complete graph. The same is also true for all evennumbered sets. The constraints for which sets do or do intersect must be built into the program. There is no known way to tell what ii the optimum size for the subsets Fi. It certainly relies on the type of digraph. One might be inclined to say that a dense digraph would require more directed bicliques to cover it. However, it is closely tied to the relationship between the arcs. Take, for instance, DK1 1 shown in ,nFigure 14a. DKl,nt is a directed biclique, so + bc(DKl,nl) = 1. DKl,nl has n1 arcs. Another digraph with n1 arcs is the cycle illustrated in Figure 14b. + Each arc is a directed biclique, and bc(DC 1 ) = n1. n
PAGE 66
1 2 1 3 n1 2 n a. b. Figure 14. a. A directed biclique on n vertices. A cycle on n1 vertices. 55
PAGE 67
CHAPTER III DIRECTED BICLIQUE COVERS AND PARTITIONS OF ACYCLIC DIGRAPHS Introduction Another restriction to put on a digraph, D, in + + order to find out bc(D) and bp(D), is to force the digraph to be acyclic. The results in this chapter were recently published (12} by my advisor, J. R. Lundgren, and myself. The three major levels of connectivity of a digraphstrongly connected, unilaterally connected, and weakly connectedwill be used in this chapter. Let D be a digraph. If x and y are any twa vertices in V(D) such that there exists a path from X to Y and from y to X, then 0 is strongly connected. If there exists a path from x to y or from y to x, then D is unilaterally connected. When direction is disregarded and the underlying graph is connected, then D is weakly connected. A digraph which is of a specific connectivity level also meets the requirements of the lower connectivity levels. When the II II word str1ctly is applied before a connectivity level in this paper, it means the given level is the highest level which can be used to describe the For example, a digraph which is strictly weakly connected
PAGE 68
57 is weakly but not unilaterally A digraph 0 is acyclic if it n6t contain a cycle v 1 ,Cv 1,v2J,v2 (v 2,v3 ) ... vk,(vk,v1 ) for vi E V(D). Unilaterally Connected, Acyclic Digraphs An acyclic, connected digraph can be viewed at only two connectivity levels: (1) strictly unilaterally connected, and (2) strictly connected. Neither the digraph nor any of its generated subdigraphs will be strongly connected. If a subdigraph were strongly connected, a cycle would have to exist: Let u,v be two vertices in 'the subdigraph. There exists a path p 1 = utx1,x2 ,xk,v and a path p 2 = v,w 1,w2 .. ,wm,u since the subdigraph is strongly connected. If the xi and w. J are all unique, then pl joined with p2 is a cycle, and cycles are not allowed. 1 f some w. are equal to other J X. then there exists one which path pl reaches first. 1 Let this vertex be labeled z. Then u,x1 ,xi_1,z,wj+l' ,w ,u is a cycle. Therefore, there can be no strongly m connected generated subdigraphs of an acyclic digraph. + + Equglity is obtained for both bc(D) and bp(D) 1n the case of a unilaterally connected, acyclic digraph, so this case is examined Theorem 3.2.1: If o is an acyclic, unilaterally connected + digraph on n > 2 vertices, then bc(D) = n1.
PAGE 69
58 Ptoof: The proof is by induction. For n = 2, we + bc(D) = 1 = n1. As s u me t h at f o r n = k b+c ( D ) = k 1 L e t D be an acyclic, unilaterally connected digraph on k+1 vertices. There exists a vertex x e: V(D) with only outgoing arcs. The sub digraph D ... generated by the vertices V(D){x} is also unilaterally connected, so tJ"cCD ... ) = k1. S i n C e We Can in Cl U de t he a r C S f r 0 m X aS 0 n e b i C 1 i q U e + + bc(D) < bc(D )+l = k. However, there is a vertex y e: V(D ... ) which has only outgoing arcs and (x,y) is an arc in o. Hence, (x,y) must be covered in a different biclique from those used in co v e r i n g D ... so t h t 6c CD ) b c ( D ... ) + l = k + Therefore, we have bc(D) = n1. [J We can also partition the arcs of D into n1 directed bicliques. Theorem 3.2.2: If Dis an acyclic, unilaterally connected + digraph on n > 2 vertices, then bp(D) = n1. Proof: Let D be an acyclic, unilaterally connected digraph + r on n > 2 vertices. Since be (D) bp (D), we have that + n1 < bp(D).. There exists a vertex z e: V(D) which has only incoming arcs. T h us there i s a t r i v i a 1 par t i t i on containing n1 disjoint directed bicliques, each consisting of all the outgoing arcs of a vertex in V(D){z}, + giving bp(D) n1.
PAGE 70
59 + Therefore, we have bp(D) = n1. [] The following corollary is obtained directly from + + relationships bc(D) = r 8 (A(D)) and bp(D) = r +(A(D)). z The second corollary ties the results to transitive tournaments. A trans! tive tournament is an acyclic, unilaterally connected digraph, so the result follows immediately from Theorems 3.2.1 and 3.2.2. A matrix is strictly right triangular if all elements on and below the diagonal are zeros. Corollary 3.2.3:. If A is an n x n, strictly right triangular (0,1)matrix with ones along the superdiagonal, then r 8 (A) = r +(A) = n1. z Corollary 3.2.4: If D is a transitive tournament on n > 2 + + vertices, then bc(D) = bp(D) = n1. Strictly Weakly Connected, Acyclic Digraphs In the strictly weakly connected, acyclic digraph + + case, only bounds for bc(D) and bp(D) are determined. Here we those bounds and find digraphs which have + + bc(D) and bp(D) for every value therein. Theorem 3.3.1: If 0 is an acyclic, strictly weakly connected digraph on n + > 3 vertices, then bc(D) < n2. Proof: This proof is by induction. For n = 3, we have + bc(D) = 1 < n2. Assume that for n = k, 6c(D) < k2. Let o
PAGE 71
. 60 be an acyclic, strictly weakly connected on k+l vertices. There exists a vertex x g V(O) which has only outgoing arcs. The subdigraph 0 ... generated by the vertices V(O){x} has the fallowing possibilities of connectivity: ( a ) d i s conn e c t e d ( b ) s t r i c t 1 y w ea k 1 y conn e c t e d a r (c) unilaterally connected. Case (a): disconnected. Let E., i = l, ,m, 1 m 2, be them c6mponents of D ... and let pi= lvCEi)l. m Sa p. = k. Each E1 is at most unilaterally connected, 1 1 1= + giving bc(Ei) < p.1 for 1 1 (p.1) 1 m = ( i=l Hence, p.)m = km, 1 sa that b7c(O ... ) km < k2. We know we can cover the arcs from x with ohe directed biclique, so bc(O) bc(D ... )+l km+l < k1 = n2. + ... Cas e ( b ) : s t r i c t 1 y weak 1 y conn e c t e d b c ( 0 ) k 1 +. + sa we have bc(O) bc(D ... )+l k1 = n2. Case (c): unilaterally connected. Here we examine 0 ... and find a vertex whose removal from 0 instead of x gives a subdigraph with connectivity of either Case (a) or Case (b) above. 0 ... has a vertex y with only outgoing arcs and a vertex z with only incoming arcs. Since D ... is unilaterally connected, y can reach all other vertices of D .... Vertex
PAGE 72
61 cannot reach all of .the .other vertices in D because D is strictly weakly connected and D.. is unilaterally c on n e c t e d T he r e for e ( x y ) can n o t be an arc in D T hi s implies that there is no path from x toy or y toxin D. Vertex z with only incoming arcs in D .. also has only incoming arcs in D, due to x having only outgoing arcs before its removal. Let E be the subdigraph of D generated by using vertices V(D){z}. Vertices x and y are in V(E). Thus, E is strictly weakly connected or E is By Cases (a) and (b) then, we know that + bc(D) < n2. + Therefore, by Cases (a), (b), and (c), bc(D) 2_ n2. [] The biclique partition number of D is similarly bounded by using the previous proof, and the following theorem is Theorem 3.3.2: If D is an acyclic, strictly weakly connected digraph on n > 3 vertices, then b+p(D) 2_ n2. Unlike the case of the unilaterally connected digraphs examined earlier, we cannot unequivocably state + + that bc(D) = bp(D) in the strictly weakly connected case Certainly there are occasions when this is true, but the following example illustrates a case Where it is not.
PAGE 73
62 Example A: Let the adjacency matrix of D, A (D) represent an acyclic, strictly weakly connected digraph. Here, oC:co) = 3 and D) = 4. 1 2 3 4 5 6 1 0 0 1 0 1 1 2 0 0 1 1 1 0 3 0 0 0 1 1 1 A(D) = 4 0 0 0 0 1 1 5 0 0 0 0 0 0 6 0 0 0 0 0 0 A minimal directed bic1ique covering of D is given by the bicliques: 81 = {(1,3),(2,3)}, 82 = {(2,4),(2,5),(3,4),(3,5)}, 8 3 = { ( 1 5 ) ( 1 6 ) ( 3 5 ) ( 3 6 ) ( 4 5 ) ( 4 6 ) } Yet any partition requires four bicliques. These results also extend to the Boolean and nonnegative integer ranks of matrices, given in the following corollary. Corollary 3.3.3: If A is an n x n, strictly right triangular matrix with at most n2 ones on the superdiagonal, then r 8(A) n2 and rz+(A) n2.
PAGE 74
63 When b o u n d s a r e f o un d for be ( D ) and b+p ( D } an problem arises: Can a digraph on n vertices be found for each of the values within the bounds? This is known as 11interpolation 11 In the case of a strictly weakly connected, acyclic digraph, it is possible to find examples for each as illustrated in Figures 15, 16, and 17. 2 3 n 0 1 1 1 0 0 0 0 O's Figure 15. A strictly weakly connected acyclic digraph + + where bc(D) = bp(D) = 1.
PAGE 75
64 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 O's Figure 16. A strictly weakly connected acyclic digraph + + where bc(O) = bp(D) = 2.
PAGE 76
65 IA general, for i = 2i ,n2, we have 2 3 4 i i+l i+2 Although we have found examples of digraphs where bc(D) = bp(D) and tJc(D) < tfp(D), these classes of digraphs have not been characterized.
PAGE 77
66 Results for Digraphs with Cycles A strong of a digraph D is a maximal subdigraph which is strongly tonnected. The following theorem Jses strong components of a digraph D to give a + + lower bound for bc(D) and bp(O). Theorem 3.4.1: If Q is a digraph ori n 1 and D. fori= l, are them components of D, then ]. and m (D) > l b+c ( D i) i=1 m + bp(D) > l ttp (D. ) 1 1 l.= Proof: Let Di for i = 1, ... ,m be them strong components of a digraph D, and let B be any directed biclique in a minimum directed biclique covering of D. Suppose B covers arcs in two strong components, Di and D (x1,x2 ) is J an arc covered in Di and (y1,y2 ) is an arc covered in Dj. From the definition of a directed biclique, this implies that (x1,y2 ) and (y1,x2 ) are arcs in D. So a path exists from D{ to Dj and from Dj to Since they are maximal, we must have i = j. Therefore, bc(D) cannot be less than + the sum of bc(Dj), so
PAGE 78
67 m 6c co) > .l 6ccoj) J=l and similarly, m bp(D) > l 6p(Dj). D j:l we digraphs with cycles, there are many forms these digraphs can take. This permits us to bound b1:(o) and bp(D) only within a very wide range. Therefore, it is instructive to find examples which attain the lower bounds and upper bounds for the three connectivity levels and also to solve the interpolation problem. If D has a cycle, it is easy to see that bc(D) 2 + and bp(D) > 2. As mentioned in Chapter II, every arc of a generated cycle will belong to a different directed biclique. Thus, the cover and partition number of D must be at least as big as the sizeof the largest generated cycle. Following is theorem which gives the bounds for + + bc(D) and bp(D) when D is a digraph with cycles. The upper bound n can be achieved, for example, by an ncycle. Theorem 3.4.2: If D is a digraph with cycles on n > 6 + + vertices, then 2 bc(D) n and 2 bp(D) n. Now it is instructive to look at for each of the values within the bounds for each of the connectivity levels. It is possible for a digraph to be
PAGE 79
68 strictly unilaterally. connected or strictly weakly connected even if it has a cycle. All vertices on a cycle form a strongly connected subdigraph, but there may be vertices not on the cycle which can neithet reach the cycle nor be reached by the cycle. When lookin. g at the problem, it is + + necessary to find a digraph D where bc(D) and bp(D) are the desired values, but the values do not depend on the number of vertices. Therefore, in the following figures in this chapter, every digraph D is shown with n vertl.ces, w her e n i s not de t e r m i n e d D i g r a ph s w he r e b7c ( 0 ) = b7p ( 0 ) = 2 are shown in Figures 18, 19, and 20. Figure 18 is a strongly connected digraph, while Figure 19 represents a strictly unilaterally connected digraph. A strictly weak 1 y connected digraph where b c ( D ) = b7p ( D J = 2 is illustrated in Figure 20. The strongly connected graph in Figure 18 is a series of twocycles. All arcs oriented away from vertex 1 wiil be in one directed biclique. The arcs directed toward vertex 1 will be in another. These 2 1 3 n Figure 18. Strongly connected digraph where + r bc(D) = bp(D) = 2.
PAGE 80
69 two bicliques have no arcs in common, so they serve as a cover as well as a partition. 2 3 1 n1 n Figure 19. Strictly unilaterally connected digraph where bc(D) = bp(D) = 2. Figure 19 represents a strictly unilaterally connected digraph. None of the vertices 1, nl can reach vertex n, but n can reach all the other vertices. This digraph will require two directed bicliques of the same form as those of the strongly connected digraph. The difference will be that the directed biclique containing arcs oriented toward 1 will have one fewer arc here. Only one cycle is in the strict 1 y weakly connected digraph in Figure 20. It is possible to have twocycles between vertex 1 and all vertices 2, ,n2 and still have the digraph be strictly weakly Vertices n1 and n would not be able to reach each dther, thus giving the connectivity category. In this digraph we again form directed bicliques as in the previous two
PAGE 81
2 1 3 n Figure 20. Strictly weakly connected digraph where = = 2. 70 examples. One directed biclique, however, will contain only the arc Cv2,v1). In the next two figures, 21 and 22, digraphs will be shown which reach the maximum value bt(D) = tfp(D) = n. a strongly connected digraph on n vertices, it has already been mentioned that a cycle on n vertices requires n directed bicliques for both a cover and partition. Therefore, the remaining two connectivity categories will be shown. Each figure has two parts. The first part will give the digraph (a) when n is even, and the second part will give the digraph (b) when n is odd. The directed bicliques for the strictly unilaterally connected digraph in Figure 2l.a. will be: 1. Every arc from an oddnumbered vertex to an numbered vertex will form its own directed biclique. There are of these arcs.
PAGE 82
71 1 2 3 4 n1 n n > 4; even a. n even. 2 n1 n n > 5; odd b. n odd. Figure 21. Strictly unilaterally connected digraph + + where bc(D) = bp(D) = n. 2. Every evennumbered vertex has two arcs leaving it (except vertex n). These two arcs from any evennumbeied vertex form their own directed biclique and (v ,v 1 ) form another. n n. n There are 2 even numbers. From the directed formed in (1) and (2), there n n are 2 + 2 = n directed bicliques 1n both the cover and partition. This digraph is strictly unilaterally connected because vertices on the far right cannot reach vertices on the far left. Figure 21. b. will have a similar directed biclique structure. However, digraph has a cycle of length three. Therefore, the following changes are necessary: 1. Cv1,v2 ) and (vn,vn_1 ) form their own directed bicliques.
PAGE 83
72 2. Every arc from an evennumbered vertex to an oddnumbered vertex forms its own directed biclique. There are of these. 3. Every two arcs leaving an oddnumbered vertex (excluding vertex 1 and vertex n) form a directed biclique. There are n1 21 directed bicliques conta!ning two arcs. From (1), (2), and (3), there are 2 + n1 + n1 1 = n 2 2 directed bicliques needed to both cover and partition the arcs in Figure 21.b. The directed bicliques for Figure 22.a. and 22.b. are formed similarly to those in Figure 21. However, care must be taken since the arcs connecting the cycles vary in direction. This is what makes the digraphs strictly weakly connected. In Figure 22. a. for example, vertices 1 and 2 cannot reach vertices 5 and 6; nor can 5 and 6 reach 1 and 2. Of course, now it must be shown that every value for and bp(D) can be obtained between the bounds of 2 and n. So, we not only need to look at an arb;trary n, but also an arbitrary i, 2 < i < n, such that + + bc(D) = bp(DP) = i. In these examples, we examine an adjacency matrix for digraph D. Figure 23 shows A(D) of a strongly connected digraph.
PAGE 84
73 1 2 3 4 5 6 n1 n n > 6; even a. n even. 2 6 7 n1 n n > 7; odd b. n odd. Figure 22. Strictly weakly connected digraph + + where bc(O) = bp(D) = n. 1 2 3 4 5 i i+1 n 1 0 1 1 1 1 1 1 1 2 1 0 1 0 0 0 0 0 3 1 0 0 1 0 0 0 0 3
PAGE 85
74 The digraph 0 repiesented by Figure 23 has arcs from 1 to all other vertices, .and from all vertices to 1. So any vertex can reach any,other vertex through 1. Thus, the digraph is strongly cqnnected. The other ,arcs rep. r es en ted by ones down the i agonal f r om 2 t o i....: 1 f o r c e b ( 0 ) = b p ( D ) = i .. Th e on e s in column 1 form one directed biclique, while the ones in \ row 1 form another Each. one on the supe. r .diagonal from row 2 .to row i1 will form its own dire'cted biclique. This iequires i2+2 = i directed This is not a unique cover or partition, but any others will also require i bicliques. The rna t r i x i n Fig u r e 2 4 r e p r e s en t s a s t r i c t 1 y un ly connected digraph. As in. F1gure 19, its . main with a connected is absence of an arc (in this (vn,vl)) ... ,' 1 2 3 4 5 i i+1 h 1 0 1 1 1 1 1 1 ... 1 2 1 0 1 0 0 0 0 a .. 3 1 0 0 1 0 ... 0 0 o 3
PAGE 86
75 The directed bicliques for the digraph associated with Figure 24 are formed exactly like those for the strongly connected digraph. The directed biclique formed from column 1 will just have one arc fewer. The digraph given by its adjacency matrix in Figure 25 is strictly connected. Vertices n1 and n cannot reach each other. 1 2 3 4 5 i1 i i+l n1 n 1 0 1 1 1 1 1 1 1 1 1 2 1 0 1 0 0 0 0 0 0 0 3 1 0 0 1 0 0 0 0 0 0 3
PAGE 87
76 Chapter IV, where kregular digraphs are examined. The b o u n d s for b c ( 0 ) an d b p ( 0 ) f o r a s tr i c t 1 y w e a k 1 y c on n e c t e d digraph and for digraphs containing cycles are wide to get good idea of what is happening. It may be possible to characterize the digraphs for a certain cover and partition number. It would also be interesting to see if digraphs where bc(O) = srp(O) or bc(O) I tJp(D) can be characterized.
PAGE 88
CHAPTER IV DIRECTED BICLIQUE COVERS AND PARTITIONS OF kREGULAR DIGRAPHS The evolution of research in the area of kregular digraphs was discussed in Chapter I, Section 5. This previous work raises interesting questions: 1. Brualdi, Manber, arid Ross [3] found the minimum rR(n,k) for 1 k 3, and show that rR(n,k) = rR(n,nk) for + 1 < k < n1. Since rR(n,k) bp(n,k), it naturally leads to the question of finding for which k + + bp(n,k) = bp(n,nk). This has proven true for all cases studied thus far. Lundgren conjectures that it is true for all k. In this chapter, I include his + + proof for bp(n,3) = bp(n,n3). _,_ + 2. For what values of n and k does = bp(n,k)? In the research done previously, two major places have be en f o u n d w he r e t h e r e i s in e qua 1 i t y : + + + (a) bp(n,n1) > bc(n,n1) for n and (b) bp(n,n..2) > + bc(n,n2) for n 9. Here, evidence is provided for an infinite sequence where equality does not hold. 3. + For what values of k does bp(n,k) = rR(n,k)? Again, all cases studied so far have equality holding. Here
PAGE 89
78 + we show bp(n,n3) = rR(n,n3). It also appears that this holds for k = 4 and 5. of finding + ttp ( n, k) 4. The general problem bc(n,k) and for all k is examined further in this chapter for k = 5. Values and bounds + bp(n,5) on bc(n,5) and are given. A conjecture is made for all n and k. In particular, if n = qk+r with 0 < r < k, then tp(n,k) and b ( n k ) depend on b p ( k + r k ) and b+c (k + r k ) Partitions for (n,3) and (n,n3) Recently, in our search to determine if tJp ( n, k) = + + + bp(n,nk), Lundgren proved that bp(n,3) = bp(n,n3). I include it here both to demonstrate what is required in this type of proof and to show its relationship to real rank. Theorem 4.1.1: Let z(n) = 0 if n : 0 (mod 3) and z(n) = 3 otherwise. + + Then for all n 6, bp(n,n3) = bp(n,3) = LjJ +z ( n) Proof: By a result of Brualdi, Manber, and Ross [3], rR(n,k) = rR(n,nk) for 1 < k < n1. Since rR(n,nk) + r +(n,nk) = bp(n,nk), result gives a bound z on the partition number. [ 10 J Case i: n = 3q. So, q < r +(n,n3). Let z
PAGE 90
rows. Letting each directed biclique of a partition co ri s i s t o f ( q 1 ) J 3 3 s, i t w i 11 t a k e q d i r e c t e d b i c 1 i que s to partition A. This gives r +(A)= q, so q < r +(ri,n3) < q. z z Hence, r +(n,n3) = q = r +(n,3), and bp(n,n3) = q = z z + bp(n,3). Case ii: n = 3q+l. By previous results from [10] and [3], rR(n,3) = q+3 = rR(n,n3). So, r +(n,n3) > q+3. Let z I 1 'S I J3' 3 : A = J3,3 J3,3 ,3 : ,0l001 0 0 1 0 1' s l I 0 0 0 1 I 1 0 0 0 where the upper pdrtion of A requires 3q3 rows. Then rz+(A) = (33 )+4 = (q1)+4 = q+3, which gives
PAGE 91
80 q + 3 < r + ( n n3 ) < q + 3 Hence rz + ( n n3 ) = q + 3 = r + ( n 3 ) z z + + and bp(n,n3) = q+3 = bp(n,3). Case iii: n = 3q+2. By previous results from [10} and [3], rR(n,3) = q+3 = rR(n,n3). So, r > q+3. Let z A = ... I J3,3 I I I I I I J3, 3 1 1's J3,3 J3,3 03,3 I .+1's 1 0 0 1 1 0 I o o 1 0 1 I 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 where the upper portion of A requires 3q3 rows. Then r +(A)= ( 393 3)+4 = q+3, so q+3 < r +(A)< q+3. Thus, z z + + r + ( n 3 ) = q + 3 = r + ( n n3 ) and b p ( n 3 ) = q + 3 = b p ( n n3 ) z z D Brualdi, Manber) and Ross [3] only calculate the actual values of rR(n,k) = rR(n,nk) for k 1,2,3. The case where k = 3 was heavily used in the previous proof. For k 4, however, the corresponding values are not available.
PAGE 92
81 + + Values where bc(n,k) = bp(nik) When working with general digraphs, it is not uncommon to have the cover strictly less than the partition number. However, when trying to find a kregular digraph with minimum cover and partition numbers, the two always turn out to be the same. This can be seen in the research by Gregory et al. [ 10 J for k < 4 and n = qk. The cases cited earlier for k = n1 and k = n2 show two instances when the cover and partition numbers may not be equal. De Caen, Gregory, and Pullman [4] have shown that be ( n n 1 ) = s ( n ) P r it i k in [ 18 J show s that b7p ( n n 1 ) = n So whenever k = n1, the cover and partition numbers can be expected to be different. For n = 2,3,4, the value of s(n) = n. For n > 4, s(n) is always less than n. The difference between + bc(n,n1) and becomes 1 a r g e r as n gets 1 a 1' g e r because s C n ) grows 1 o gar it h mica 11 y In the case where k = 5, b7c(6,5) = 4 and b7p(6,5) = 6. Here, the difference is greater than one. For n = 11, the best possible cover number attained thus far is for the matrix shown in Figure 26. The o 1 E 0(11,5) + + associated w1th M 1 has bc(o1 ) = l+s(6) = 5, and bp(D 1 ) = 7. M 2 in Figure 27 has an associated digraph o 2 E 0(11,5), + where bp(D2 ) = 6.
PAGE 93
82 J5 5 D's I +I D 1 1 1 1 1 I M1 = I 1 D 1 1 1 1 I I 1 1 D 1 1 1 D's I I 1 1 1 D 1 1 1 1 1 1 D 1 1 1 1 1 1 D Figure 26. Adjacency matrix of a digraph 0 E: 0(11,5) with 6rc(D) = 5. 1 1 1 1 1 D D D D D D 1 1 1 1 1 D D D D D D 1 1 1 1 1 D D D D D D 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 M2 = 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 D 1 1 0 D 0 1 0 D 1 1 1 0 D 1 D 0 1 D 0 1 0 0 0 D 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 Figure 27. Adjacency matrix of a digraph 0 E: 0(11,5) + where bp(O) = 6.
PAGE 94
83 The bicliques which form the partition of M 2 consist of the first three rows, the _second three rows, rows seven and eight, then of the last three rows is a biclique. A digraph D 0(11,5) with bp(D) = 5 has not been found; It seems that although we can do one better + than b p ( 0 1 ) = 7 in this case we cannot bring the partition number down farther than 6. This was not the case with k = 4, because the cover and partition numbers for differed only by one. This leads to. the following conjecture: If we consider D(5q+1,5) for q > 1, + + bc(5q+1,5) < bp(5q+l,5). For all q 3, adjacency matrices of digraphs De: D(5q+1,5) can be constructed where + + bc(O) = bp(D)1. The ith J5 5 is placed in rows and columns 5(11)+1 through 51, for 1 i q1. A 6 x 6 5regular submatrix is then placed in the last six rows and columns. Thus, an adjacency matrix is obtained whose + digraph D e: 0(5q+1,5) has bc(D) = (q1)+4 = q+3. To obtain the partition number, (q2) J 's can similarly 5,5 be added to M 2 in Figure 27, which gives an associated d i g r ap h D e D ( 5 q + 1 5 ) w he r e b p ( D ) = ( q2 ) + 6 = q + 4 A 1 t h o ugh this inequality has not yet proven, it seems to be true. This would give an infinite sequence where the cover and partition numbers are unequal. In general, we believe that this conjecture is + a 1 so true for a 11 k > 5 The difference between b c ( n n 1 ) + and bp(n,n1) grows larger as n does. Therefore, it seems
PAGE 95
84 less likely that the partition number for will be able to equal the cover number as q becomes We believe there .are several infinite sequences o f ex amp 1 e s w h e r e b+p ( n k ) > b+c ( n k ) They a r e b as e d on the observation that for n sufficiently large, and k large relative to n, it appears that b+p(n,k) > t)c(n,k). For + + example, for n 9, bp(n,n2) > bc(n,n2) by Barefoot et a 1 [ 2 J Bas e d on t h is we con j e c tu r e that for k > 7 + + bp(kq+2,k) > bc(kq+2,k). These examples have not been encountered previously since only k < 5 has been studied in depth. Further results for k = 5 will be examined in the following sections of this chapter. + Cases bp(n,k) = rR(n,k) In section 1 of Chapter IV, it was shown that bp(n,n3) = for all n > 6. Brualdi, Manber, and Ross [3] also obtained that value for rR(n,n3). Other work done in the area has failed to show any situation where the partition number is unequal tb the real rank. Is this something which is occurring because a minimum number is being sought? It is possible that this is the easeL Every adjacency matrix whose digraph has the minimum partition number possesses a real rank equal to that number. In the following section, 5regular digraphs will be studied in depth. The results there also yield
PAGE 96
85 digraphs, oi, where bp(Di) rR(A(Oi)). However, this provides only an upper bound for the real rank. It will have to be proven that the real rank cannot be lower than the partition number in these ases. If, in fact, the partition number equals the real r an k f o r a 11 k co n j e c t u res mad e f o r bp ( n k ) c an b e expanded to rR(n,k). The conjecture in the previous + + bc(kq+l,k) < bp(kq+l,k) for k 5, would give an infinite for each k where the Boolean rank is strictly less than the real rank. The Boolean rank in general can be less than, to, or greater than real rank. This would be a step in helping to classify the matrices where r 8(A) < rR(A). + + Finding bc(n,k) and bp(n,k) The previous sections have dealt with specific questions surrounding kregular digraphs and matrices. This section begins to examine the general question of + + finding bc(n,k) and bp(n,k). As explained in Chapter I, as k gets larger, casebycase proofs of the cover and partition numbers become unwieldy. Because bf this, many of the following pages will contain upper bounds and conjectures. Before the general case for kregular is discussed, we will look at values and bounds for k = 5. Since (at times) it is best to begin at the beginning, using previous results the following values can be obtained:
PAGE 97
86 1. + bc(6,5) = s(6) = 4 + bp(6,5) = 6 + bc(7,5) = 5 2. + bp(7,5) = 5 + bc(5q,5) = q 3. + bp(5q,5) = q The v a 1 u e s for b+c ( 8 5 ) and bp ( 8 5 ) a r e o b t a in e d by the proof of Theorem 4.4.1. In the proof, a matrix, o, i s given w her e tJc ( 0 ) = tJp ( 0 ) = 5 w h i c h i s an up p e r b o u n d It is then shown that bc(8,5) 5. This forces b+c(8,5) + + + to e qua 1 5 S i n c e b c ( 8 5 ) b p ( 8 5 ) and b p ( 8 5 ) _:: 5 bp(8,5) must also equal 5. The proof that b+c(8,5) 5 hinges on a casebycase examination of the size of the largest directed biclique in the cover. It relies on contradictions based on assuming that b1:(8,5) < 4. Theorem 4.4.1: + + = bp(B,5) = 5. Proof: The matrix M 3 in Figure 28 has r6 (M 3 ) = r +(M3 ) = 5. z + + So, bc(8,5) 5 and bp(8,5) .:: 5. + suppose bc(8,5) .:: 4. Since there are 40 arcs, 40 the largest biclique niust contain at least r41 = 10 arcs. So the largest biclique must be no smaller than 2 x 5 or 5 x 2. Let C be a largest maximal directed biclique of a minimum cover. Place C in the upper left corner of the
PAGE 98
87 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 M3 = 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 Figure 28. An adjacency matrix whose digraph + + 0 e: 0(8,5) has bc(D} = bp(D) = 5. matrix. The matrix will have no other ones in all of the same rows or columns of C because C is C cannot be a 5 x 5 directed biclique, because that would leave three columns to the right of C which must each have five ones in the last three rows. This is impossible. Likewise, C will not be a 5 x 4 directed biclique. Then there would be three columns which must have five ones in the last four rows. Since AT is also 5regular, the case for C being a 4 x 5 directed biclique follows from the preceding reasoning by interchanging the words 11rOW11 and 11Column.11 This being true, the following + cases will prove bc(8,5) > 5 if C is i x j, which also covers the case where C is j x i. Case i. c is a 4 x 4 directed biclique. This leaves a 4 x 4 area in the lower right side of A which has
PAGE 99
88 at most four ones in each column. Therefore, up to e q u i v a 1 en c e the on 1 y p o s s i b 1 e con f i g ur a t i on which y i e 1 d s a 5regular digraph is given in Figure 29. number for this is ( 11 I I 1 I 1 I 1 ______ 1 1 1 I I I I I 1 I I The cover Figure 29. An 8 x 8 5regular where C is a 4 x 4. Case ii. C is a 3 x 5 directed biclique. The three columns to the right of C must have five ones in the last five rows, so the matrix also has a 5 x 3 block of ones. M 3 in Figure 28 gives the best possible configuration for this case, and the cover number is 5. This arises from the area being a 5 x 5 block which must be 2regular, where 6c ( 5 ,2) = 4. Since M 3 reflects this, it has the minimum cover number if a 3 x 5 or 5 x 3 is the largest directed biclique.
PAGE 100
89 Case iii. c is a 3 x 4 directed biclique. There are eight ones below c and three ones to the right 0 f c. If two directed bicliques are used to cover these ones, at most fifteen new arcs w ill b e c o v e r e d This is shown in Figure 30. If b+c(8,5) .:: 4' then 401215 = 13 arcs must be tovered in ona more directed biclique. But since the largest directed biclique is a 3 4 which covers twelve arcs, this is not possible. 1 1 1 1 I 1 o o o I 1 1 1 1 1 1 o o o I 1 1 1 110 1 0 0 ________ _)_ ____ 1 1 1 o o I 1 I 1 1 o o 1 1 I 0 0 1 1 I 1 0 0 1 1 I 1 I I Figure 30. Partial construction of a matrix where only two directed bicliques are needed to cover the ones surrounding C (J x 4). Suppose three directed bic1iques are used to cover these ones. There are four to the right of c. At most three of these columns will have ones in the first three rows. So, there exists a column j which has five ones in the last five rows. If only four directed bicliques are used, and three are being used to cover the ones
PAGE 101
90 directly below and the.ones to the right of C, these three directed bicliques must also cover the ones in column j. At least two directed bicliques are needed to cover the ones to the right of c. These bi6liques will not cover column j, since there are no ones in common. So the last directed must cover these ones and also ones under c. But there can be no place under C which has ones in the last five rows. Therefore, the cover number must be greater than 4. Case iv. C is a 2 x 5 directed biclique. There are 40 arcs with at most 10 arcs per directed biclique. Since C is the largest, if a cover can be obtained using four directed bicliques, each directed biclique must be a 2 x 5 or 5 x 2 and the cover must be a partition. But there is no way to put 2 x 5 and 5 x 2 blocks of ones together to form a 5regular matrix. So the cover number must be greater than 4. Thus, by Cases iiv, bt(8,5) > 5. Therefore, bc(8,5) = 5, and bc(8,5) < bp(8,5) < 5 gives bp{8,5) = 5. D A similar proof which gives bc(9,5) = bp(9,5) = 5 follows. The larger value for n provides more possibilities for the arrangement of the adjacency matrices.
PAGE 102
91 + + Theorem 4.4.2: bc(9,5) = bp(9,5) = 5. Proof: The matrix M5 showM in Figure 31 has r 8(M5 ) = + + r +(M5 ) = 5. So, bc(9,5) 5 and bp(9,5) 5. z 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 M5 = 1 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 l l 1 l 0 0 0 0 1 1 1 1 l Figure 31. An adjacency matrix whose digraph 0 E 0(9,5) + has bc(O) = bp(O) = 5. Let c be a largest maximal directed biclique in a cover. c in the upper left corner of the adjacency matrix. C cannot be a 5 x 5 directed biclique, because the four columns to the right of C would then have five ones in the last four rows. + Suppose that bc(9,5) < 4. As in the proof of Theorem 4.4.1, proofs of the nonexistence of an i x j directed biclique will also eliminate the possibility of having j x i directed bicliques. There are 45 arcs which must be covered in at most 4 directed bicliques.
PAGE 103
92 So the largest must be at least size = 12. only candidates for C bf size 3 x 4 and above will be considered. Case i. C is a 4 x 5 directed biclique. Then the four columns to the right of C must have five ones in the last five rows. Therefore, Figure 32 gives the ohly possible formation for the adjacency matrix, and its cover number is 6. 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 l 1 1 1 0 0 0 0 M6 = l 0 0 0 0 l 1 l 1 0 1 0 0 0 1 l 1 l 0 0 1 0 0 l l 1 l 0 0 0 1 0 l l 1 1 0 0 0 0 1 l l 1 1 Figure 32. Adjacency matrix where c is a 4 X 5 directed biclique. Case ii. C is a 4 x 4 directed biclique. Then there are four ones below C and four ones to the right of C. At least two directed bicliques are required to cover these ones.
PAGE 104
93 Suppose two directed bicliques areused. Figure ::33 gives a partial representation of one way the matrix must look. The ones below C can only use two rows, and the ones to the right of C use just two columns. So, the maximum number of new arcs covered is 4+4+2 = 10. This leaves 451610 = 19 arcs to be covered in one more directed biclique. This cannot be done since the largest directed biclique covers only sixteen arcs. 1 1 1 1 1 1 1 1 1 1 1 1 I I I I I I 1 1 0 o 0 1 1 1 1 1 I o 1 t 1 1 o o 1 1 o 1 1 I I 0 1 Figure 33. A partial adjacency matrix where C is 4 x 4 and two directed bicliques cover the ones surrounding c. Now suppose three directed bicliques are used to cover the ones C. The ones to the right of C are in at most four columns. So, there exists a column j which has ones only in the last five rows. The ones below Care in at most four rows. So, there is a row i which has no ones in the first four columns. Therefore, element
PAGE 105
1 1 1 1 1 I I 1 1 1 1 1 I D's I 1 1 1 1 1 1 1111_1_t __ l 1 1 I 1 1 1 I 1 1 1 1 1 I 1 1 1 1 1 1 I I 1 Figure 35. Partial adjacency matrix where C is a 3 x 5 and three directed bicliques cover the ones below c. 95 three additional directed bicliques are used. Therefore, + bc(9,5) > 5 in this case. Case iv. c is a 3 x 4 directed biclique. C has three to the right of it, and eight ones below it. It takes at least two directed bicliques to cover these ones (see Figure 30 in the proof of Theorem 4.4.1 for construction). These two directed bicliques will cover at most fifteen new arcs. This leaves 451215 = 28 arcs to cover in one more, but the most it is possible to cover is twelve. Now suppose three directed bicliques are needed. The ones to the right of c take at most three columns. So there exists a column j which has ones only in five of the last six rows. The ones to the right of C will be
PAGE 106
96 covered in at least two directed bicliques. These directed bicliques do not contain column j. So the last directed biclique must cover the five ones in column j plus of the ones under c. But there are only two ones per column under c. Therefore, it will take more than the three directed bicliques which cover the ones surrounding C to cover all of the ones in the lower right corner. Thus, the cover number must be at least 5. Hen c e by the p r e c e d in g case s b+c ( 9 5 ) > 5 w h i c h gives = 5. Also, since bc(9,5) 5, bp(9,5) = 5. D In section 2 of this chapter, current upper bounds + + for bc(11,5) and bp(ll,5) were given. The conjectures for the cover and partition numbers of D(5q+1,5) stem from the belief that there exists a q where adding a J 5 5 to a matrix of 0(5(q1)+1,5) gives at least as good a cover or partition as any other arrangement. Because the difference between trc ( n, n1) and tfp ( n, n1) grows rapidly as n becomes large, it seems that the conjecture for the case of k = 5 can be exterided to arbitrary k: + bc(qk+l,k) = q1+s(k+l), k > 1; bp(qk+1,k) = k > 1. So b+c ( q k + 1 k) < b+p ( q k + 1 k ) for k > 5 The preceding conjecture is based on augmenting a matrix having minimum cover and partition numbers, with q1 or q2 Jk k's. We
PAGE 107
97 conjecture that this augmentation is optimal. Using this construction as a foundation, the following conjecture applies to digraphs where bc(k+i,k) = tfp(k+i,k) for 2 < i < k: = ql+bc(k+i,k), k > i; bp(qk+i,k) = q!+bp(k+i,k), k > L A proof of the above conjecture must be done without using cases. Even for k = 6, there are 3 6 possible directed biclique sizes. After the cover and partition numbers have been found when k = 5 for any n, the time for casebycase studies must come to an end. A new approach must be found which will solve the problem of directed biclique cover and partition numbers for all kregular digraphs.
PAGE 108
[1] [5] [6] [a] [ 10 J BIBLIOGRAPHY C. Barefoot, K 0.. S. Hefner, K. F. Jones, and J. R. Lundgren, Biclique covers of the complements of cycles and paths in a digraph, Congressus Numerantium, 53 (1986), 133147. C. Barefoot, K. F. Jones, J. R. Lundgren, and J. s. Maybee, Biclique covers of regular digraphs, Congressus Numerantium, 53 (1986), 147154. R. A. Brualdi, R. Manber, and J. A. Ross, On the minimum rank of regular classes of matrices of zeros and ones, Journal of Comb. Theory, Series A, 41(1) ( 1986)' 3249. D. de Caen, D. A. Gregory, and N. J. Pullman, The Boolean rank of zeroone matrices, Proceedings of the 3rd Car. Conf. Comb. and Camp. (1983), 169173. D. de Caen, D. A. Gregory, and N. J. Pullman, Clique coverings of complements of paths and cytles, Ann. o f D i s crete Math 2 7 ( 19 8 5 ) 2 57 2 6 8 D. de Caen and N. J. Pullman, Clique coverings of graphs I: Clique partitions of regular graphs, Utilitas Mathematica, 19 (1981), 177205. D. de Caen and N. J._Pullman, Clique coverings of grQphs III: Clique coverings of regular graphs, Congressus Numerantium, 29 (1980), 795808. P. Erdos, A. w. Goodman, and L. P6sa, The representation of a graph by set. inter sections, Can. J. Math., 18 (1966), 106112. R. Graham and H. Pollack, On the addressing problem for loop switching, Bell System Technical Journal, 50 (1971), 24952519. D. A. Gregory, K. F. Jones, J. R. Lundgren, and N. J. Pullman, Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices, to appear.
PAGE 109
[14] [ 16] [17 J [ 19] 99 D A G reg o r y and N J P u 11m an Semi r i n g rank : Boolean rank and nonnegative factoiizations, J. Comb. Infor. and System Sciences, 8(3) (1983), 223233. K. A. S. Hefnet and J. R. Lundgren, Biclique covers and p a r t i t ions o f ac y c 1 i c digraphs Con g r e s s us Numerantium, to appear. K. F. Jones, J. R. Lundgren, and J. s. Maybee, Clique covers of digraphs II, Congressus Numerantium, 48 (1985), 211218. K. H. Kim, Boolean Matrix Theory and Applications, Marcel Dekker, Inc. ( 1982). J. R. Lundgren and J. S. Maybee, Clique covers of digraphs, Research Report, University of Colorado at Denver (1984). G. H. J. Meredith and E. K. Lloyd, The footballers of Croam, J. Comb. Theory, Ser. B, 15 (1973), 161l66 J. Orlin, Contentment in graph theory: graphs with cliques, Indag. Math., 39 406424. Covering. (1977), D. Pritikin, Applying a proof of Tverberg to complete bipartite decompositions of digraphs and multigraphs, to appear. N. J. Pullman, Clique coverings of graphsA survey, Proceedin s of the Xth Australian Conference on Combinatorial Mathematics, Adelaide 1982 (Lecture Notes in Math. 1036, SpringerVerlag, Berlin, 1983, 7285.) F. S. Roberts, Applications of edge coverings by cliques, Discrete Appl. Math., 10 (1985), 93109. E. SzpilrajnMarczewski, Sur deux des classes d'ensembles, Fund. Math., 33 (i945), 303307. E. SzpilrajnMarczewski, Sur !'extension de l'ordre partie!, Fund. Math., 16 (1930), 386389. z. Tuza, Covering of graphs by complete bipartite subgraphs; Complexity of 0l matrices, Combinatorica, 4(1) 111116.
PAGE 110
100 [24] H. Tverberg, On the decomposition of Kn into complete bipartite graphs, J. Graph Theory, 6 (1982), 493494.

