pith. sign in

arxiv: 1903.12292 · v1 · pith:JN7FY5JWnew · submitted 2019-03-28 · 🧮 math.CO

Partial domination of maximal outerplanar graphs

classification 🧮 math.CO
keywords iotaverticesdominationfracsizeclassicalgraphgraphs
0
0 comments X
read the original abstract

Several domination results have been obtained for maximal outerplanar graphs (mops). The classical domination problem is to minimize the size of a set $S$ of vertices of an $n$-vertex graph $G$ such that $G - N[S]$, the graph obtained by deleting the closed neighborhood of $S$, is null. A classical result of Chv\'{a}tal is that the minimum size is at most $n/3$ if $G$ is a mop. Here we consider a modification by allowing $G - N[S]$ to have isolated vertices and isolated edges only. Let $\iota_1(G)$ denote the size of a smallest set $S$ for which this is achieved. We show that if $G$ is a mop on $n \geq 5$ vertices, then $\iota_{1}(G) \leq n/5$. We also show that if $n_2$ is the number of vertices of degree $2$, then $\iota_{1}(G) \leq \frac{n+n_2}{6}$ if $n_2 \leq \frac{n}{3}$, and $\iota_1(G) \leq \frac{n-n_2}{3}$ otherwise. We show that these bounds are best possible.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.