Disjunctive domination in maximal outerplanar graphs Thanks: Research supported in part by the South African National Research Foundation under grant number 129265 and the University of Johannesburg Thanks: Corresponding author. Abstract A disjunctive dominating set of a graph G G is a set D ⊆ V ⁡ ( G ) D\subseteq V(G) such that every vertex in V ⁡ ( G ) ∖ D V(G)\setminus D has a neighbor in D D or has at least two vertices in D D at distance 2 2 from it. The disjunctive domination number of G G , denoted by γ 2 d ​ ( G ) \gamma_{2}^{d}(G) , is the minimum cardinality of a disjunctive dominating set of G G . In this paper, we show that if G G is a maximal outerplanar graph of order n ≥ 7 n\geq 7 with k k vertices of degree 2 2 , then γ 2 d ​ ( G ) ≤ ⌊ 2 9 ​ ( n + k ) ⌋ \gamma_{2}^{d}(G)\leq\left\lfloor\frac{2}{9}(n+k)\right\rfloor , and this bound is sharp. Keywords: Domination; disjunctive domination; maximal outerplanar graphs AMS subject classification: 05C69 1 Introduction All the graphs considered in this paper are finite, simple, and undirected. For a graph G , we use V(G) and E(G) to denote the vertex set and the edge set of G , respectively. Two vertices u and v of G are adjacent if uv\in E(G) . Two adjacent vertices are called neighbors . The open neighborhood N_{G}(v) of a vertex v in G is the set of neighbors of v , while the closed neighborhood of v is the set N_{G}[v]=\{v\}\cup N_{G}(v) . The degree of a vertex v in G is the number of vertices adjacent to v in G , and is denoted by \deg_{G}(v) , and so \deg_{G}(v)=|N_{G}(v)| . A vertex of degree 1 in G is called a leaf (and also called a pendant vertex in the literature). The distance between vertices u and v in G is the minimum length of a path between u and v , and is denoted by d_{G}(u,v) . For a given positive integer l , we use the notation [l] to denote the set \{1,2,\ldots,l\} . A rooted tree T distinguishes one vertex r called the root . Let T be a tree rooted at vertex r . For each vertex v\neq r of T , the parent of v is the neighbor of v on the unique (r,v) -path, while a child of v is any other neighbor of v . A descendant of v is a vertex u\neq v such that the unique (r,u) -path contains v . Thus, every child of v is a descendant of v . We let C(v) and D(v) denote the set of children and descendants, respectively, of v , and we define D[v]=D(v)\cup\{v\} . The maximal subtree rooted at v is the subtree of T induced by D[v] , and is denoted by T_{v} . A diametrical vertex of T is a leaf that belongs to a longest path in T . In this paper, we study planar graphs. A plane embedding of a planar graph G is an embedding of G in a plane such that the edges of G do not intersect each other except at the endpoints. A planar graph with a plane embedding is called a plane graph . A triangulated disk or near-triangulation is a 2 -connected plane graph all of whose interior faces are triangles. A maximal outerplanar graph G , abbreviated mop , is a plane graph such that all vertices lie on the boundary of the outer face (unbounded face) and all inner faces are triangles. Throughout our discussion, we refer to inner faces of a maximal outerplanar graph as triangles. Two faces are adjacent if they share a common edge. A triangle of G that is not adjacent to the outer face is called an internal triangle of G . An edge on the outer face (unbounded face) is called an outer edge of G , while any other edge of G is called a diagonal of G . A region R\,\colon v_{1}v_{2}\ldots v_{k} of G is a maximal outerplanar subgraph of G such that one outer edge of R is diagonal of G and all other outer edges of R are outer edges of G . For an edge e=xy of G , the contraction of an edge e of G is the graph obtained from G by deleting x and y (and all incident edges), adding a new vertex v , and adding edges between v and each vertex in (N_{G}(x)\cup N_{G}(y))\setminus\{x,y\} . Lemma 1 ( [ 16 ] ) . If H is obtained by the contraction of an outer edge e in a mop G of order n\geq 4 , then H is also a mop. A set D\subseteq V(G) is a dominating set of G if every vertex in V(G)\setminus D is adjacent to at least one vertex in D . The domination number of G , denoted by \gamma(G) , is the minimum cardinality among all dominating sets of G . Domination and its variants are well-explored topics in graph theory, with existing literature thoroughly reviewed in [ 9 , 10 , 11 , 12 ] . Goddard, Henning, and McPillan introduced the concept of disjunctive domination in graphs inspired by distance domination and exponential domination. In a graph G , a set S\subseteq V(G) is called a disjunctive dominating set , abbreviated 2DD-set, if every vertex in V(G)\setminus S is adjacent to a vertex in S or has at least two vertices in S at distance 2 from it. A vertex x in G is said to be disjunctive dominated by the set S if it is adjacent to at least one vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive domination number of G , denoted by \gamma_{2}^{d}(G) , is the minimum cardinality among all disjunctive dominating sets of G . A 2DD-set of cardinality \gamma_{2}^{d}(G) is called a \gamma_{2}^{d} -set of G . The concept of disjunctive domination in graphs has been examined in [ 5 , 13 , 14 , 15 , 18 ] . In this paper, we study disjunctive domination in planar graphs. The study of domination in maximal outerplanar graphs has been extensively studied since 1975. In a seminal paper [ 6 ] , Chvátal showed that the domination number of a maximal outerplanar graph of order n is at most n/3 . Campos and Wakabayashi [ 4 ] demonstrated that for a mop G of order n , \gamma(G)\leq\left\lfloor\frac{1}{4}(n+k)\right\rfloor , where k is the number of vertices with degree 2 . Tokunaga independently confirmed this result in [ 17 ] . For additional variants of domination in maximal outerplanar graphs, we refer the reader to the references [ 1 , 2 , 3 , 7 , 8 ] . 2 Main result Since every dominating set is a disjunctive dominating set of a graph G , we note that \gamma_{2}^{d}(G)\leq\gamma(G) . In particular, for a mop G of order n with k vertices of degree 2 , we infer that \gamma_{2}^{d}(G)\leq\gamma(G)\leq\left\lfloor\frac{1}{4}(n+k)\right\rfloor . A natural problem is to determine whether this bound on \gamma_{2}^{d}(G) can be improved, and if so, what is a tight bound in the sense that it is achievable for mops. Our main result is the following improved upper bound on the disjunctive domination number of a mop. Theorem 1 . If G is a mop of order n\geq 7 with k vertices of degree 2 , then \gamma_{2}^{d}(G)\leq\left\lfloor\frac{2}{9}(n+k)\right\rfloor . We proceed as follows. In Section 3 , we present observations of maximal outerplanar graphs and present preliminary lemmas on the disjunctive domination number of a mop. Thereafter in Section 4 , we present a proof of our main result, namely Theorem 1 . In Section 5 , we present examples that demonstrate the tightness of the given bound. 3 Preliminary results and lemmas In the following, we present properties of maximal outerplanar graphs, which are well-known or easy to observe. Observation 1 . If G is a mop of order 5 , then there exists a vertex adjacent to all other vertices of G . Observation 2 . If G is a mop of order n where 5\leq n\leq 8 and if v_{1}v_{2}\ldots v_{n}v_{1} represent the boundary of the outer face of G , then \{v_{i},v_{i+4}\} is a 2DD-set of G for any i\in[n] , where i+4 is calculated modulo n . Observation 3 . Let G be a mop of order n\geq 4 and let v_{1}v_{2}\ldots v_{n}v_{1} represent the boundary of the outer face of G . If v_{i}v_{j} is a diagonal of G , where i\left\lfloor\frac{2}{9}(n+k)\right\rfloor . Among all such mops G , let G be chosen to have minimum order n\geq 13 where as before G has k vertices of degree 2 . By the minimality of G , if G^{\prime} is a mop of order n^{\prime} where 7\leq n^{\prime}\left\lfloor\frac{2}{9}(n+k)\right\rfloor . Furthermore, if G^{\prime} is a mop of order n^{\prime} where 7\leq n^{\prime}