Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648416 | Discrete Mathematics | 2009 | 9 Pages |
Abstract
We prove the existence of certain spanning subgraphs of graphs embedded in the torus and the Klein bottle. Matheson and Tarjan proved that a triangulated disc with nn vertices can be dominated by a set of no more than n/3n/3 of its vertices and thus, so can any finite graph which triangulates the plane. We use our existence theorems to prove results closely allied to those of Matheson and Tarjan, but for the torus and the Klein bottle.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael D. Plummer, Xiaoya Zha,