Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/67618
Type: Artigo de periódico
Title: On dominating sets of maximal outerplanar graphs
Author: Campos, CN
Wakabayashi, Y
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.
Subject: Dominating set
Domination number
Outerplanar graph
Planar graph
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.dam.2012.08.023
Date Issue: 2013
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.