Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/75652
Title: | Partial domination of maximal outerplanar graphs |
Authors: | Borg, Peter Kaemawichanurat, Pawaton |
Keywords: | Mathematics Logic, Symbolic and mathematical Set theory Hypergraphs |
Issue Date: | 2020 |
Publisher: | Elsevier BV |
Citation: | Borg, P., & Kaemawichanurat, P. (2020). Partial domination of maximal outerplanar graphs. Discrete Applied Mathematics, 283, 306-314. |
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á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, and n2 is the number of vertices of degree 2, then ι1(G) ≤ n/5 and ι1(G) ≤ { n+n2 6 if n2 ≤ n3, n−n2 3 otherwise. We also show that these bounds are best possible. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/75652 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Partial_domination_of_maximal_outerplanar_graphs_2020.pdf Restricted Access | 395.92 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.