pith. sign in

arxiv: 2603.02625 · v3 · submitted 2026-03-03 · 🧮 math.CO · cs.DM

An Upper Bound for the Double Domination Number in Maximal Outerplanar Graphs

Toru Araki This is my paper

Pith reviewed 2026-05-15 17:42 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords double domination numbermaximal outerplanar graphsupper boundgraph domination
0
0 comments X

The pith

Maximal outerplanar graphs have double domination number at most (n+k)/2

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that every maximal outerplanar graph G on n vertices satisfies an upper bound on its double domination number. The bound states that the smallest set S where every vertex is dominated by at least two members of S has size at most (n+k)/2. Here k counts the pairs of consecutive vertices along the outer cycle whose graph distance is at least 3. The result supplies a complete proof for a bound that an earlier paper had stated but not fully established. Readers care because the bound directly limits how many vertices are needed to achieve double coverage in these triangulated planar graphs.

Core claim

For any maximal outerplanar graph G with n vertices, the double domination number gamma times 2 of G is at most (n+k)/2, where k equals the number of pairs of consecutive vertices on the outer cycle whose distance is at least 3. The argument proceeds by constructing a double dominating set whose size respects this formula and thereby confirms the bound after an earlier proof attempt was shown to be incomplete.

What carries the argument

The parameter k, which tallies pairs of consecutive outer-cycle vertices at distance at least 3 and is added to n before halving, to produce the stated upper bound on the double domination number.

If this is right

  • The size of any minimum double dominating set is controlled by the total number of vertices plus the number of distant consecutive pairs on the outer cycle.
  • The bound holds uniformly for every maximal outerplanar graph, including those with many internal triangles.
  • When k is small the bound approaches n/2, while larger k loosens the bound in graphs with more spread-out outer-cycle pairs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar counting arguments on outer cycles could produce bounds for other domination variants such as triple domination in the same graph class.
  • The formula may guide linear-time algorithms that build double dominating sets by selecting vertices according to the positions of those k pairs.

Load-bearing premise

The graph must be maximal outerplanar, so that every internal face is a triangle and the outer face is a simple cycle, and k must be counted exactly from the distances between consecutive vertices on that cycle.

What would settle it

A single maximal outerplanar graph whose smallest double dominating set exceeds size (n+k)/2 would disprove the bound.

Figures

Figures reproduced from arXiv: 2603.02625 by Toru Araki.

Figure 1
Figure 1. Figure 1: The situation that was missing from the proof. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Lemma 3.3. Shaded triangles are internal triangles. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Claim 3.4. Possible triangles adjacent to [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Claim 3.6. Possible triangles adjacent to [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Claim 3.7. Possible triangles adjacent to [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Claim 3.8. Possible triangles adjacent to [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Case 1 and Case 2. Possible situations when [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Case 1-3. Possible situations when ds = 1 and dt = 4. The shaded triangle is an internal triangle corresponding to t. The gray vertices are in a double dominating set S [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Case 1-4. Possible situations when ds = 1 and dt = 6. The shaded triangle is an internal triangle corresponding to t. The gray vertices are in a double dominating set S. For [PITH_FULL_IMAGE:figures/full_fig_p011_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Case 2-1. Possible situations when ds = dt = 2. The shaded triangle is an internal triangles corresponding to t. The gray vertices are in a double dominating set S. For both cases, let G′ = G − {v1, v2, v3, v4, v5}. Note that u1 is bad in G and is good in G′ . Then G′ has n − 5 vertices and k ′ ≤ k − 1 bad vertices, and a minimum double dominating set S ′ of G′ satisfies |S ′ | ≤ (n ′ + k ′ )/2 ≤ (n + k −… view at source ↗
Figure 11
Figure 11. Figure 11: Case 2-2. Possible situations when ds = 2 and dt = 4. The shaded triangle is an internal triangle corresponding to t. The gray vertices are in a double dominating set S. For [PITH_FULL_IMAGE:figures/full_fig_p013_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Case 2-3. Possible situations when ds = 2 and dt = 6. The shaded triangle is an internal triangle corresponding to t. The gray vertices are in a double dominating set S. |S| = |S ′ | + 4 ≤ (n + k)/2, a contradiction. For [PITH_FULL_IMAGE:figures/full_fig_p014_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Case 3-1. Possible situations when ds = 4 and dt = 4. The shaded triangle is an internal triangle corresponding to t. The gray vertices are in a double dominating set S [PITH_FULL_IMAGE:figures/full_fig_p015_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Case 3-2. Possible situations when ds = 4 and dt = 6. The shaded triangle is an internal triangle corresponding to t. The gray vertices are in a double dominating set S. For [PITH_FULL_IMAGE:figures/full_fig_p015_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Case 4. Possible situations when ds = 6 and dt = 6. The shaded triangle is an internal triangle corresponding to t. The gray vertices are in a double dominating set S. vertices and k ′ ≤ k − 1 bad vertices since u5 is a good vertex in G′ . Thus, a minimum double dominating set S ′ of G′ satisfies |S ′ | ≤ (n ′ + k ′ )/2 ≤ (n + k − 9)/2, and S ′ includes u4, u6, v6 and v8 since degG′ u5 = degG′ v7 = 2. The… view at source ↗
read the original abstract

In a graph $G$, a vertex dominates itself and its neighbors. A subset $S$ of vertices of $G$ is a double dominating set of $G$ if every vertex is dominated by at least two vertices in $S$. The double domination number $\gamma_{\times 2}(G)$ of $G$ is the minimum cardinality of a double dominating set of $G$. In this paper, we prove that, for a maximal outerplanar graph $G$, the double domination number $\gamma_{\times 2}(G)$ is at most $(n+k)/2$, where $k$ is the number of pairs of consecutive vertices on the outer cycle but at distance at least 3. Although this bound was previously proposed by Abd Aziz, Rad and Kamarulhaili (A note on the double domination number in maximal outerplanar and planar graphs, RAIRO Operations Research, 56 (2022) 3367--3371), their proof was found to be incomplete. In this paper we establish the validity of this result by providing a complete proof.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for a maximal outerplanar graph G on n vertices, the double domination number satisfies γ_{×2}(G) ≤ (n + k)/2, where k counts the pairs of consecutive vertices on the outer cycle whose graph distance is at least 3. The argument is a complete inductive proof that proceeds by ear removal, carefully tracking the evolution of both n and k under the reduction; it repairs the incomplete proof given by Abd Aziz, Rad and Kamarulhaili (2022).

Significance. The result supplies a clean, parameter-free combinatorial upper bound on double domination in the well-studied class of maximal outerplanar graphs. The inductive scheme that maintains the auxiliary parameter k alongside n is a technical strength, as it yields a direct, falsifiable bound without fitted constants or external assumptions. The completion of the earlier argument also clarifies the structural role of the outer cycle in domination problems for this graph family.

minor comments (2)
  1. [Abstract] Abstract: the phrasing “pairs of consecutive vertices on the outer cycle but at distance at least 3” is slightly ambiguous; a parenthetical reminder that “consecutive” refers to adjacency on the boundary cycle while distance is measured in G would remove any possible misreading.
  2. [Section 2] Section 2: the formal definition of k should explicitly state whether the counted pairs are ordered or unordered and whether the distance threshold is strict (>2) or non-strict (≥3).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the positive recommendation to accept. The referee's summary correctly identifies the main contribution: a complete inductive proof, via ear removal, of the bound γ_{×2}(G) ≤ (n + k)/2 for maximal outerplanar graphs.

Circularity Check

0 steps flagged

No circularity; inductive combinatorial proof is self-contained

full rationale

The paper establishes the bound γ_{×2}(G) ≤ (n+k)/2 via a direct inductive argument on maximal outerplanar graphs that proceeds by ear removal while explicitly tracking the evolution of both n and the parameter k (defined from outer-cycle distances). No equation or step reduces the claimed upper bound to a fitted quantity, a self-citation, or an ansatz imported from prior work by the same authors; the previous incomplete proof is cited only as motivation, not as a load-bearing lemma. The derivation therefore remains independent of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on standard definitions and properties of maximal outerplanar graphs (triangulated outer cycle, every internal face a triangle) that are taken from prior literature; no new free parameters or invented entities are introduced.

axioms (1)
  • standard math Every maximal outerplanar graph on n ≥ 3 vertices has exactly 2n-3 edges and n-2 internal triangular faces.
    Invoked implicitly when counting vertices and boundary pairs; this is a textbook fact about outerplanar triangulations.

pith-pipeline@v0.9.0 · 5483 in / 1150 out tokens · 37616 ms · 2026-05-15T17:42:27.715155+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    N. A. Abd Aziz, N. J. Rad, H. Kamarulhaili, A note on the double domina- tion number in maximal outerplanar and planar graphs, RAIRO Operations Research 56 (5) (2022) 3367–3371

    work page 2022

  2. [2]

    Y. Aita, T. Araki, Secure total domination number in maximal outerplanar graphs, Discrete Applied Mathematics 353 (2024) 65–70

    work page 2024

  3. [3]

    Araki, I

    T. Araki, I. Yumoto, On the secure domination numbers of maximal outerplanar graphs, Discrete Applied Mathematics 236 (2018) 23–29

    work page 2018

  4. [4]

    Blidia, M

    M. Blidia, M. Chellalia, T. W. Haynes, Characterizations of trees with equal paired and double domination numbers, Discrete Mathematics 306 (16) (2006) 1840–1845

    work page 2006

  5. [5]

    C. N. Campos, Y. Wakabayashi, On dominating sets of maximal outerplanar graphs, Discrete Applied Mathematics 161 (2013) 330–335

    work page 2013

  6. [6]

    Dorfling, J

    M. Dorfling, J. H. Hattingh, E. Jonck, Total domination in maximal outerplanar graphs, Discrete Applied Mathematics 217 (2017) 506–511

    work page 2017

  7. [7]

    Hajian, N

    M. Hajian, N. J. Rad, A new lower bound on the double domination number of a graph, Discrete Applied Mathematics 254 (2019) 280–282

    work page 2019

  8. [8]

    Harant, M

    J. Harant, M. A. Henning, On double domination in graphs, Discussiones Math- ematicae Graph Theory 25 (2005) 29–34

    work page 2005

  9. [9]

    Harary, T

    F. Harary, T. W. Haynes, Double domination in graphs, Ars Combinatoria 55 (2000) 201–213. 17

    work page 2000

  10. [10]

    T. W. Haynes, S. T. Hedetniemi, M. A. Henning (eds.), Topics in Domination in Graphs, vol. 64, Springer, Cham, 2020

    work page 2020

  11. [11]

    T. W. Haynes, S. T. Hedetniemi, M. A. Henning (eds.), Structures of Domina- tion in Graphs, vol. 66, Springer, Cham, 2021

    work page 2021

  12. [12]

    T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Domination in Graphs: Core Concepts, Springer Monographs in Mathematics, 2023

    work page 2023

  13. [13]

    T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998

    work page 1998

  14. [14]

    T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998

    work page 1998

  15. [15]

    M. A. Henning, Graphs with large double domination numbers, Discussiones Mathematicae Graph Theory 25 (2005) 13–28

    work page 2005

  16. [16]

    M. A. Henning, P. V. Maniya, D. Pradhan, Disjunctive domination in maximal outerplanar graphs, Discrete Applied Mathematics 385 (2026) 24–61

    work page 2026

  17. [17]

    Lemanska, E

    M. Lemanska, E. Rivera-Campo, R. Ziemann, R. Zuazua, P. Zylinski, Convex dominating sets in maximal outerplanar graphs, Discrete Applied Mathematics 265 (2019) 142–157

    work page 2019

  18. [18]

    Lema´ nska, R

    M. Lema´ nska, R. Zuazua, P.˙Zyli´ nski, Total dominating sets in maximal outer- planar graphs, Graphs and Combinatorics 33 (2017) 991–998

    work page 2017

  19. [19]

    L. R. Matheson, R. E. Tarjan, Dominating sets in planar graphs, European Journal of Combinatorics 17 (1996) 565–568

    work page 1996

  20. [20]

    Tokunaga, Dominating sets of maximal outerplanar graphs, Discrete Applied Mathematics 161 (2013) 3097–3099

    S. Tokunaga, Dominating sets of maximal outerplanar graphs, Discrete Applied Mathematics 161 (2013) 3097–3099

    work page 2013

  21. [21]

    Zhuang, Q

    W. Zhuang, Q. Zheng, Double domination in maximal outerplanar graphs, Open Mathematics 20 (2022) 1082–1088. 18

    work page 2022