| Abstract: This presentation is a summary of
an undergraduate research project in graph theory, which involved resolving
lower bound conjectures on the matching number of bipartite graphs. The
matching number of a graph is defined as the cardinality of a largest subset
of the edges such that no two edges have a vertex in common. A graph is
bipartite if its vertex set can be partitioned into two disjoint sets, X and
Y, such that their union is the vertex set of the graph and each edge of the
graph has exactly one endpoint in each of the sets. One main objective of
this project was to obtain a collection of lower bounds involving only
degrees and distances of graphs, which collectively predict the matching
number of bipartite graphs. The conjectures resolved in this project were
generated by a computer program called Graffiti.pc, which was designed by my
project advisor, Dr. Ermelinda DeLaViņa. We present a summary of the
collection of lower bounds thus far, a couple of which were found in texts
and research papers, but most of which we resolved as mathematical
applications of Hall's Marriage Theorem and Berge's M-Augmenting Path
Theorem.
Research Abstracts SACNAS-Volume 1, p. 173, (2004) |
