Seminario Interdipartimentale di Algoritmica
 

Monday, April 6th, 2009, 12:00 noon
Isomorphism theorems for even cycles and even cuts in graphs
Bertrand Guenin, University of Waterloo, Ontario
   
DI - Department of Computer Science, Via Salaria 113
Seminar room, third floor

Abstract

A seminal result of Whitney characterizes when two graphs have the same cycle space (or equivalently the same cut space): namely, this occurs exactly when one graph can be obtained from the other by repeatedly rearranging the graph along one and two vertex cut sets in a special way. We generalize this result to even cycles in signed graphs as well as to even cuts in grafts.

This is joint work with Irene Pivotto and Paul Wollan.