Article ID Journal Published Year Pages File Type
4648416 Discrete Mathematics 2009 9 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,