Narodna in univerzitetna knjižnica, Ljubljana (NUK)
Naročanje gradiva za izposojo na dom
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi
  • Dominating sets in triangulations on surfaces
    Liu, Hong, matematik ; Pelsmajer, Michael J.
    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 surfaces.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 4, no. 1, 2011, str. 177-204)
    Vrsta gradiva - članek, sestavni del
    Leto - 2011
    Jezik - angleški
    COBISS.SI-ID - 16266329

    Povezava(-e):

    http://amc.imfm.si/index.php/amc/article/view/200
    Digitalna knjižnica Slovenije - dLib.si

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 4, no. 1, 2011, str. 177-204)

loading ...
loading ...
loading ...

Vnos na polico