×

Dominating sets inducing large components in maximal outerplanar graphs. (English) Zbl 1405.05130

In this paper, the authors introduce the concept of the \(k\)-component domination number of a graph \(G\). For some positive integer \(k\) and a graph \(G\), a set \(D\) of vertices of \(G\) is a \(k\)-component dominating set if every vertex in \(V(G) - D\) has a neighbor in \(D\) and every component of the subgraph \(G[D]\) of \(G\) induced by \(D\) has order at least \(k\). The minimum cardinality, denoted by \(\gamma_k(G)\), of a \(k\)-component dominating set of \(G\) is called the \(k\)-component domination number of a graph \(G\). The authors showed that if \(k\) and \(n\) are positive integers with \(n \geq 2k + 1\) and \(G\) is a maximal outerplanar graph of order \(n\) then \(\gamma_k(G) \leq \lceil \frac{kn}{2k + 1}\rceil\) if \(G \in \mathcal{H_k}\); \(\gamma_k(G) \leq \lfloor \frac{kn}{2k + 1}\rfloor\) if \(G \not \in \mathcal{H_k}\), where the detailed definition of \(\mathcal{H_k}\) was given in the paper.
Reviewer: Rao Li (Aiken)

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv