{'fraction_non_alphanumeric': 0.04840711625982623, 'fraction_numerical': 0.02254861398427803, 'mean_word_length': 3.6714975845410627, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Domination Number of Triangulated Discs

Let G be a 3-connected triangulated disc such that the boundary cycle C of the outer face is an induced cycle of G and G −C is a tree. In this paper we prove that γ(G) ≤ n+2 4 , which gives a partial solution for the conjecture that the same inequality holds for any 3-conneced triangulated disc. We also show related conjectures.


Introduction
For a graph G = (V(G), E(G)) and v ∈ V(G), let N G (v) denote the set of all the vertices which are adjacent to v in G, and let , and let S G denote the induced subgraph of G induced by S . For S ⊂ V(G) and v ∈ V(G), we say S dominates v if v ∈ N G [S ]. If D ⊂ V(G) dominates all the vertices of G, then D is said to be a dominating set of G. The domination number of G, denoted γ(G), is defined as the minimum cardinality of a dominating set of G. A plane graph G is said to be a triangulated disc if G is 2-connected and all its faces are triangles except for the outer (infinite) face. The boundary cycle of the outer face of G is said to be the outer cycle of G and is denoted C(G). G − C(G) is said to be an inner subgraph of G and is denoted In(G). An l-coloring is a function is dominated by the set of all the vertices of color i (i = 1, 2, ..., l), then we say v is dominated by color i.
In 1996, Matheson and Tarjan [2] proved that any triangulated disc G with n vertices satisfies γ(G) ≤ n 3 . They also conjectured that γ(G) ≤ n 4 for every n-vertex maximal planar graph G with sufficiently large n. Note that we need two vertices to dominate the six vertices of the octahedron graph, and there also exists a 11-vertex maximal planar graph with γ(G) = 3 > 11 4 ( Fig. 1), therefore we cannot omit the condition that n is sufficiently large. In 2010, King and Pelsmajer [7] proved that the conjecture of Matheson and Tarjan holds for maximal planar graphs with a maximum degree 6. In 2013, Campos and Wakabayashi [1] and Tokunaga [3] independently proved γ(G) ≤ n+t 4 for each nvertex outerplanar graph G with n ≥ 3 having t vertices of degree 2. In 2016, Li, Zhu, Shao, and Xu improved the upper bound in Refs. [1], [3] by showing γ(G) ≤ n+k 4 , where k is the number of pairs of consecutive 2-degree vertices with a distance of at least 3 on the outer cycle.
In Ref. [3], the author gave a simple proof by showing that G   has a proper 4-coloring such that each vertex except those with degree two is dominated by all the four colors, and a similar method is also applied to other related problems [4], [5]. Moreover, the author conjectured as follows. Figure 2 shows that the upper bound in Conjecture 1 is sharp. Note that the inner subgraph of the graph in Fig. 2 is a path. There are many graphs satisfying the equality in Conjecture 1 whose inner subgraphs are trees. In this paper, we prove the following theorem.

Proof of Theorem 1
To prove Theorem 1, we show the following lemma.  4-coloring f such that each vertex of G − v is dominated by all the four colors except the vertices of N G (v).

Lemma 1 Suppose G is an n-vertex triangulated disc such that In(G) is a tree and C(G) is an induced cycle of G, and let
To prove Lemma 1, let us introduce the following notation. For an l-coloring f of graph G and v ∈ V(G), let Since T 1 , T 2 are trees and C(G 1 ), C(G 2 ) are induced cycles of G 1 , G 2 , respectively, both G 1 and G 2 satisfy the assumption of Lemma 1. Thus by induction hypothesis, G 1 − x has a proper 4-coloring f 1 such that each vertex of G 1 − x is dominated by all the four colors except u, x 1 , w , and G 2 − v has a proper 4-coloring f 2 such that each vertex of G 2 − v is dominated by all the four colors except We can make f 1 (y) = f 2 (y) for y ∈ V(

Other Conjectures
If we weaken the assumption of 3-connectivity in Conjecture 1 to δ(G) ≥ 3, then the upper bound in Conjecture 1 appears to change as follows. Conjecture 2 Suppose G is an n-vertex triangulated disc satisfying δ(G) ≥ 3, then γ(G) ≤ 3 11 n . Figure 6 shows that the upper bound in Conjecture 2 cannot be improved.
Though there is still a gap between Conjecture 1 and Theorem 1, if the following conjecture is true, then Conjecture 1 holds for 4-connected maximal planar graphs. Conjecture 3 Suppose G is a 4-connected n-vertex maximal planar graph. Then V(G) can be divided into S 1 , S 2 such that S 1 G , S 2 G are a maximal outerplanar graph and a tree, respectively.
Note that if we delete all the edges connecting two vertices of S 1 in the above conjecture, we get a graph satisfying the assumption of Theorem 1.
Shin-ichi Tokunaga received his Ph.D. from Tokyo University of Science in 1996. He is currently an associate professor at College of Liberal Arts and Sciences, Tokyo Medical and Dental University. His research interest is planar graphs and geometric graphs. c 2020 Information Processing Society of Japan