✦ LIBER ✦

Dominating sets in triangulations on surfaces

✍ Scribed by Tatsuya Honjo; Ken-ichi Kawarabayashi; Atsuhiro Nakamoto

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 194 KB
Volume: 63
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20401

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a graph and let S⊂V(G). We say that S is dominating in G if each vertex of G is in S or adjacent to a vertex in S. We show that every triangulation on the torus and the Klein bottle with n vertices has a dominating set of cardinality at most \documentclass{article}\usepackage{amssymb}\footskip=0pc\pagestyle{empty}\begin{document} $\frac{n}{3}$ \end{document}. Moreover, we show that the same conclusion holds for a triangulation on any non‐spherical surface with sufficiently large representativity. These results generalize that for plane triangulations proved by Matheson and Tarjan (European J Combin 17 (1996), 565–568), and solve a conjecture by Plummer (Private Communication). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 17–30, 2010

📜 SIMILAR VOLUMES

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

Note on irreducible triangulations of su

Note on irreducible triangulations of surfaces

✍ Atsuhiro Nakamoto; Katsuhiro Ota 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 302 KB 👁 1 views

## Abstract In this paper, we shall show that an irreducible triangulation of a closed surface __F__^2^ has at most __cg__ vertices, where __g__ stands for a genus of __F__^2^ and __c__ a constant. © 1995, John Wiley & Sons, Inc.

Three Moves on Signed Surface Triangulat

Three Moves on Signed Surface Triangulations

✍ Shalom Eliahou; Sylvain Gravier; Charles Payan 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 206 KB

We consider finite triangulations of surfaces with signs attached to the faces. Such a signed triangulation is said to have the Heawood property if, at every vertex x, the sum of the signs of the faces incident to x is divisible by 3. For a triangulation G of the sphere, Heawood signings are essenti

Set domination in graphs

✍ E. Sampathkumar; L. Pushpa Latha 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ = (__V, E__) be a connected graph. A set __D__ ⊂ __V__ is a __set‐dominating set__ (sd‐set) if for every set __T__ ⊂ __V__ − __D__, there exists a nonempty set __S__ ⊂ __D__ such that the subgraph 〈__S__ ∪ __T__〉 induced by __S__ ∪ __T__ is connected. The set‐domination number

Diagonal Flips of Triangulations on Clos

Diagonal Flips of Triangulations on Closed Surfaces Preserving Specified Properties

✍ Richard Brunet; Atsuhiro Nakamoto; Seiya Negami 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 445 KB

Consider a class P of triangulations on a closed surface F 2 , closed under vertex splitting. We shall show that any two triangulations with the same and sufficiently large number of vertices which belong to P can be transformed into each other, up to homeomorphism, by a finite sequence of diagonal

Diagonal Flips in Triangulations on Clos

Diagonal Flips in Triangulations on Closed Surfaces with Minimum Degree at Least 4

✍ Hideo Komuro; Atsuhiro Nakamoto; Seiya Negami 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 365 KB

It will be shown that any two triangulations on a closed surface, except the sphere, with minimum degree at least 4 can be transformed into each other by a finite sequence of diagonal flips through those triangulations if they have a sufficiently large and same number of vertices. The same fact hold