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.
|