Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||On dominating sets of maximal outerplanar graphs|
|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.|
|Editor:||Elsevier Science Bv|
|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.