Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

On dominating sets of maximal outerplanar graphs

Full text
Author(s):
Campos, C. N. [1] ; Wakabayashi, Y. [2]
Total Authors: 2
Affiliation:
[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] Univ Sao Paulo, Inst Math & Stat, BR-05508090 Sao Paulo - Brazil
Total Affiliations: 2
Document type: Journal article
Source: DISCRETE APPLIED MATHEMATICS; v. 161, n. 3, p. 330-335, FEB 2013.
Web of Science Citations: 13
Abstract

A dominating set of a graph is a set S of vertices such that every vertex in the graph is either in S or is adjacent to a vertex in S. The domination number of a graph G, denoted gamma(G), is the minimum cardinality of a dominating set of G. We show that if G is an n-vertex maximal outerplanar graph, then gamma (G) <= (n + t)/4, where t is the number of vertices of degree 2 in G. We show that this bound is tight for all t >= 2. Upper-bounds for gamma(G) are known for a few classes of graphs. (C) 2012 Elsevier B.V. All rights reserved. (AU)