Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-Ichi Tokunaga
Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-Ichi Tokunaga
Theory and Applications of Graphs
An annulus triangulation G is a 2-connected plane graph with two disjoint faces f1 and f2 such that every face other than f1 and f2 are triangular, and that every vertex of G is contained in the boundary cycle of f1 or f2. In this paper, we prove that every annulus triangulation G with t vertices of degree 2 has a dominating set with cardinality at most ⌊ \frac{|V(G)|+t+1}{4} ⌋ if G is not isomorphic to the octahedron. In particular, this bound is best possible.