| DATE: | Tuesday, December 5th |
| TIME: | 10:00 AM - 11:00 AM |
| PLACE: | McConnell 320 |
| TITLE: | Measuring Connectivity in Graphs |
| SPEAKER: | Bruce Reed, Universite de Paris VI |
A graph is a set of vertices and an adjacency relation which indicates which pairs of vertices are joined by an edge. Thus, graph theory is essentially the study of connectivity. How then does one measure the connectivity of graph?
The classical theory of graph connectivity has important applications in diverse fields of mathematics, computer science, operations research, and many other sciences. We will briefly present the fundamental notions of this theory and some of their applications.
This classical theory, although extremely fruitful, does not capture the kind of connectivity that will concern us. It focuses on local properties rather than global ones. The goal of the talk is to introduce the audience to a connectivity invariant which measures global connectivity.
The study of this connectivity measure has proven very fruitful. Indeed
this new measure may be as fundamental as the well-known classical notion
of k-connectivity. We will present some of the theory that has developed
around this definition and mention some of the many results obtained by
applying this theory.