0 KB455 KB77 KB200820252011Liu, HongPelsmajer, Michael J.številka:1letnik:4str. 177-204COBISSID:16266329ISSN:1855-3966URN:URN:NBN:SI:doc-5DK09PKVenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneadominacijska množicadominating setgrafi na ploskvahgraph theorygraphs on surfacesneorientabilna ploskevnestisljiv cikelnon-contractible cyclenon-orientable surfaceteorija grafovtriangulacijatriangulationDominating sets in triangulations on surfaces|A dominating set ?$D \subset V(G)$? of a graph ?$G$? is a set such that each vertex ?$v \in V(G)$? is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any ?$n$?-vertex plane triangulation has a dominating set of size at most ?$n/3$?, and conjectured a bound of ?$n/4$? for ?$n$? sufficiently large. King and Pelsmajer recently proved this for graphs with maximum degree at most 6. Plummer and Zha (2009) and Honjo, Kawarabayashi, and Nakamoto (2009) extended the ?$n/3$? bound to triangulations on surfaces. We prove two related results: (i) There is a constant ?$c_1$? such that any ?$n$?-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most ?$n/6 + c_1$?. (ii) For any surface ?$S$?, ?$t \ge 0$?, and ?$\epsilon > 0$?, there exists ?$c_2$? such that for any ?$n$?-vertex triangulation on ?$S$? with at most ?$t$? vertices of degree other than 6, there is a dominating set of size at most ?$n(1/6 + \epsilon) + c_2$?. As part of the proof, we also show that any ?$n$?-vertex triangulation of a non-orientable surface has a non-contractible cycle of length at most ?$2\sqrt{n}$?. Albertson and Hutchinson (1986) proved that for ?$n$?-vertex triangulation of an orientable surface other than a sphere has a non-contractible cycle of length ?$2\sqrt{2n}$?, but no similar result was known for non-orientable surfacesTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije