Disjunctive domination in maximal outerplanar graphs

2025

Read Disjunctive domination in maximal outerplanar graphs (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-07186.txt.

Description

Michael Henning, Paras Maniya and Dinabandhu Pradhan prove a bound on disjunctive domination in maximal outerplanar graphs. A disjunctive dominating set is a set of vertices such that each outside vertex either sits next to the set or has at least two set members at distance two. The smallest size of such a set is the graph's disjunctive domination number.

For a maximal outerplanar graph with at least seven vertices, they bound that number using the total vertex count plus the count of degree-two vertices. The bound takes a floor form with a factor of two ninths. They also show the bound is sharp, meaning some graphs meet it exactly and no lower general bound can hold.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-07186

Browse the full library · About the Tower of Babel