Dominating Sets in Triangulations
Hong Liu
Department of Applied Mathematics
Illinois Institute of Technology
We are concerned with the dominating set in some triangulated graphs. A dominating set for a graph G=(V,E) is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge. The domination number is the number of vertices in a smallest dominating set for G. As a well-known topic, the upper bounds of domination number have been found for various graph classes related to triangulations. We improve the upper bound for triangulations on the plane with most of its vertices of degree 6 and extend it to some triangulations on orientable surfaces.