[Discrete-math-seminar] Friday, Sept 21, 3pm

[Hemanshu Kaul]

Hello all,

Michael Pelsmajer will give a talk this Friday, September 21 at 3pm in
IIT. Details are given below.

Hope you can make it.

Hemanshu


Website: http://www.math.iit.edu/academics/sem_coll.html#RGsem . 

Venue: 103, E1
Time: 3pm, Friday September 21

Title: Dominating Sets in Triangulations

Speaker: Michael J. Pelsmajer, IIT

Abstract:

In 1996, Matheson and Tarjan conjectured that any n-vertex triangulation
with n sufficiently large has a dominating set of size at most n/4.  We
prove this for graphs of maximum degree 6.

All terminology will be introduced from scratch, with plenty of
examples, so this talk should be suitable for undergraduates.  However,
if you just can't wait:  A triangulation is a graph drawn on the plane
so that every face is a triangle.  A subset of vertices S of a graph G
is a dominating set if every vertex of G is either (i) in S or (ii)
adjacent to some vertex of S. 

This is joint work with Erika L. C. King from Hobart and William Smith
Colleges.