2019/03/28 by Borg, Peter, Kaemawichanurat, Pawaton · 2 citations
#05C10 #05C35 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.12292
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á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 ι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 ≥ 5 vertices, then ι1(G) ≤ n/5. We also show that if n2 is the number of vertices of degree 2, then ι1(G) ≤ (n+n2)/(6) if n2 ≤ (n)/(3), and ι1(G) ≤ (n-n2)/(3) otherwise. We show that these bounds are best possible.