Title:
Convexity in Graphs
Date:
Thursday, November 25, 2010 at 1:00pm
Location:
E2-304 EITC Building, University of Manitoba Fort Garry Campus
Speaker:
Ortrud Oellermann
Department of Mathematics and Statistics
University of Winnipeg
Abstract:
Abstractions of properties that hold for convex sets in Euclidean space have been defined and studied for a variety of structures. In the case of graphs, convex sets are usually defined in terms of an `interval’ type; the most well-known being the shortest path intervals and induced path intervals. The respective convexities are referred to as the geodesic and monophonic convexities. For a given graph convexity, those properties possessed by (closed and bounded) convex sets in Euclidean space do not in general hold for the corresponding convex sets. Instead the goal is to find structural characterizations of those graphs for which these properties hold. These graphs frequently belong to the class of perfect graphs. We survey results that are known for the geodesic and monophonic convexities and discuss more recently studied convexities that are defined in terms of Steiner trees and minimal trees.
Cost:
This will be a free event.
Contact:
If you would like additional information or if you might be interested in presenting a seminar, please contact Steph Durocher or the Department of Computer Science.
