On certain spanning subgraphs of embeddings with applications to domination |
| |
Authors: | Michael D Plummer Xiaoya Zha |
| |
Institution: | a Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA b Department of Mathematical Sciences, Middle Tennessee State University, Murfreesboro, TN 37132, USA |
| |
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 n vertices can be dominated by a set of no more than n/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: | Dominating set Domination number Embedding Surface Klein bottle Torus Triangulation Representativity Spanning subset |
本文献已被 ScienceDirect 等数据库收录! |
|