In this REU site project, six students will work on problems arising in graph theory and its application to computer science. Research involving five themes will be open to the students. They are: Ramsey-minimal graphs for matching; Menger path systems; efficient graph labelings and embeddings; frequency of an induced subgraph and automata networks. All students will be provided with the necessary background, insuring that the proposed problems in these areas will be within the reach of undergraduates. The study of Ramsey-minimal graphs relates to coloring of graphs in two colors in ways that cannot be achieved by any subgraphs and the number of possible such decompositions. Menger path systems analyze graphs in which the number of paths which connect each pair of vertices is given, while graph labeling is concerned with symplectic embeddings or representations of graphs in possibly larger graphs in Euclidean spaces. Automata networks are models of computer networks used in the analysis of parallel algorithms and parallel processing systems which have particular application to neural networks, associative memories and learning.
