Dominating Sets for Outerplanar Graphs
Resource type
Author/contributor
- Pinciu, Val (Author)
Title
Dominating Sets for Outerplanar Graphs
Abstract
Abstract:- We provide lower and upper bounds for the domination numbers and the connected domination numbers for outerplanar graphs. We also provide a recursive algorithm that finds a connected domination set for an outerplanar graph. Finally, we show that for outerplanar graphs where all bounded faces are 3-cycles, the problem of determining the connected domination number is equivalent to an art gallery problem, which is known to be NP-hard. Key-Words:- dominating sets, star forests, outerplanar graphs, art gallery 1
Publication
International Conference on Applied Mathematics
Date
2004
Pages
49
Citation Key
pop00138
Extra
tex.type: Proceedings paper
Citation
Pinciu, V. (2004). Dominating Sets for Outerplanar Graphs. International Conference on Applied Mathematics, 49.
Link to this record