Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649124 | Discrete Mathematics | 2010 | 10 Pages |
Abstract
In 1996, Matheson and Tarjan conjectured that any nn-vertex plane triangulation with nn sufficiently large has a dominating set of size at most n/4n/4. We prove this for graphs of maximum degree 6.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Erika L.C. King, Michael J. Pelsmajer,