Dominating Sets inducing Large Components in Maximal Outerplanar Graphs
| Autor: | Simone Dantas, Dieter Rautenbach, José D. Alvarado |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Domination analysis
Generalization 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics Set (abstract data type) Integer 010201 computation theory & mathematics Dominating set Outerplanar graph FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Order (group theory) Component (group theory) Geometry and Topology Combinatorics (math.CO) Mathematics |
| DOI: | 10.48550/arxiv.1511.08713 |
| Popis: | For a maximal outerplanar graph $G$ of order $n$ at least $3$, Matheson and Tarjan showed that $G$ has domination number at most $n/3$. Similarly, for a maximal outerplanar graph $G$ of order $n$ at least $5$, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that $G$ has total domination number at most $2n/5$ unless $G$ is isomorphic to one of two exceptional graphs of order $12$. We present a unified proof of a common generalization of these two results. For every positive integer $k$, we specify a set ${\cal H}_k$ of graphs of order at least $4k+4$ and at most $4k^2-2k$ such that every maximal outerplanar graph $G$ of order $n$ at least $2k+1$ that does not belong to ${\cal H}_k$ has a dominating set $D$ of order at most $\lfloor\frac{kn}{2k+1}\rfloor$ such that every component of the subgraph $G[D]$ of $G$ induced by $D$ has order at least $k$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|