McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at