Student Poster on Conjectures of Graffiti.pc

Student: Iride Gramajo National Conference: SACNAS (Society for the Advancement of Chicanos and Native Americans in the Sciences) Science & Science Policy: Constructing an Inclusive Paradigm, October 2004, Austin, Texas
Advisor: Ermelinda DeLaViña
Poster title: Lower Bounds for the Matching Number of Bipartite Graphs
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)