pith. sign in

arxiv: 1907.07910 · v1 · pith:LUUIVASZnew · submitted 2019-07-18 · 💻 cs.DS · cs.DM· math.CO

On the m-eternal Domination Number of Cactus Graphs

V\'aclav Bla\v{z}ej , Jan Maty\'a\v{s} K\v{r}i\v{s}\v{t}an , Tom\'a\v{s} Valla This is my paper

Pith reviewed 2026-05-24 19:42 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO
keywords cactus graphsm-eternal domination numberChristmas cactus graphsdominationgraph algorithmseternal dominationeviction attacks
0
0 comments X

The pith

On Christmas cactus graphs the three variants of the m-eternal domination number are equal and can be computed in linear time.

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

The paper studies the minimum number of guards needed to defend a graph against an infinite sequence of attacks, where each attack is answered by moving one guard from an adjacent vertex. It examines three modeling variants of this number on cactus graphs: one that allows multiple guards on the same vertex, one that forbids stacking, and one that adds eviction attacks requiring defense. For the subclass of Christmas cactus graphs, where each vertex lies in at most two cycles, the paper establishes that the three variants yield identical values. It supplies a linear-time algorithm to compute this common value and proves a new upper bound that applies to arbitrary cactus graphs.

Core claim

For Christmas cactus graphs the three variants of the m-eternal domination number are equal and can be computed by a linear-time algorithm; a new upper bound holds for general cactus graphs.

What carries the argument

The m-eternal domination number, defined as the smallest set of guards that can respond indefinitely to attacks by moving a single guard along an edge to the attacked vertex.

If this is right

  • The three modeling variants produce the same numerical value on every Christmas cactus graph.
  • That common value admits an exact linear-time algorithm on Christmas cactus graphs.
  • Every cactus graph satisfies a new explicit upper bound on its m-eternal domination number.

Where Pith is reading between the lines

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

  • The equality result may allow direct transfer of algorithmic techniques developed for one variant to the other two on graphs with bounded cycle overlaps.
  • The linear-time procedure could serve as a template for similar guarding problems on outerplanar graphs or series-parallel graphs.
  • The new upper bound may be used to derive approximation guarantees for the m-eternal domination number on larger families of graphs that contain cactus subgraphs.

Load-bearing premise

The attack process is modeled as an infinite adversarial sequence in which each attack must be answered by exactly one guard moving from an adjacent vertex, and the structural definitions of cactus and Christmas cactus graphs impose no further hidden restrictions.

What would settle it

A single Christmas cactus graph on which any two of the three m-eternal domination numbers differ would falsify the equality claim.

Figures

Figures reproduced from arXiv: 1907.07910 by Jan Maty\'a\v{s} K\v{r}i\v{s}\v{t}an, Tom\'a\v{s} Valla, V\'aclav Bla\v{z}ej.

Figure 1
Figure 1. Figure 1: Decomposition of G into H and I We will create a strategy which keeps the invariant that in all its configura￾tions either v is occupied by a guard or the pair of vertices u and w are evicted. This will ensure that whenever v is not occupied due to the strategy of H need￾ing a guard from v to defend other vertices of H, the strategy of I will be in a configuration where no guard can traverse the {u, w} edg… view at source ↗
Figure 2
Figure 2. Figure 2: Two cases which can happen while evicting an edge on a cycle. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Decomposition of G into K and I. Lower bound: Now we show that Γ ∞ m (G) ≥ Γ ∞ m (I) + 1. Assume that we have an optimal strategy for m-eternal guard configuration on G. Note that we can obtain I by contracting {u, v} and {x, v} while adapting the strategy as shown in Lemma 3. We obtain a strategy for I which uses exactly Γ ∞ m (G) guards. Additionally, we see that if u is to be dominated in G there needs … view at source ↗
Figure 4
Figure 4. Figure 4: Contraction of G edges and removal if a K guard The only case when the guard on {u, v} needed to move from {u, v} to G \ {u, v} is when he was immediately substituted, i.e., x → v and v → y moves were performed. The contraction transforms this move to x → x and x → y, however, in I the guard from x can move directly to y not using the guard on {u, v}. Since we have a stationary guard at x which is not crit… view at source ↗
Figure 5
Figure 5. Figure 5: Merging strategies for I and C3k into a united strategy for G. Let us divide the attacks on G into ones which target the vertices and edges of C3k and the rest which target vertices and edges present in I. If the cycle configuration changed while defending an attack, we will simulate the vertex attack on v if v 0 is occupied, or the eviction of v if either x 0 or y 0 is occupied. On the other hand if confi… view at source ↗
Figure 6
Figure 6. Figure 6: Situation in the graph G in the case of Reduction 3. On the left is the graph G before edge contraction. On the right is the resulting graph I after the edges have been contracted. Having a proof of the exact bound for C3k in hand, let us discuss that the same argument works for C3k−1. The upper bound can change in a way that it is possible for the C3k−1 strategy to occupy x 0 and y 0 at the same time, and… view at source ↗
Figure 7
Figure 7. Figure 7: Adding a guard on {x, x0 } and {y, y0 } suffices to defend the bull subgraph. Lower bound: Let us contract all edges of the K subgraph of G to obtain I and alter the configurations in accordance to Lemma 3. We note that the vertex v 0 inherited all the guards of the original K0 which must contain at least 2 guards in all configurations. Two guards from K0 will be stationary at v 0 and are not necessary for… view at source ↗
Figure 8
Figure 8. Figure 8: The bull subgraph is contracted to v 0 and contains 2 guards who are no longer necessary. Let the 3-pan graph be a K3 with one leaf attached. Reduction 6 Let G be a Christmas cactus graph and C be a cycle on three vertices {v, x, y}, let x 0 be a leaf in G, such that x 0 connects to x and v is connected to the rest of the graph (no other edges are incident to C). The C∪{x 0} is a 3-pan graph. Remove {x, x0… view at source ↗
Figure 9
Figure 9. Figure 9: Adding a guard at x, x0 and changing behavior of the guard who originally occupied either y or v yields a strategy for G. Lower bound: Let us contract the edges of K0 in G resulting in a single vertex y 0 in I, see [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Since one guard is always present at either [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Process performed dur [PITH_FULL_IMAGE:figures/full_fig_p014_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Mutually traversable configura￾tions of optimal strategies for all elemen￾tary graphs except of cycles. Theorem 2. Let G be a Christmas cactus graph. Then Γ ∞ m (G) = γ∞ m (G) = γ∞ me(G). Proof. A Christmas cactus graph G always contains either a leaf or a leaf cycle. This will be shown by contradiction. If all vertices have degree at least two and each cycle has at least two neighboring blocks then the c… view at source ↗
Figure 13
Figure 13. Figure 13: Decision tree for choosing a proper reduction [PITH_FULL_IMAGE:figures/full_fig_p015_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Process of transforming a cactus G by contracting red edges to produce G 0 and subsequently duplicating red vertices for each black connected component to get Op(G). Theorem 3. The m-eternal domination number of a cactus graph G is bounded by γ ∞ m (G) ≤ X H∈Op(G) [PITH_FULL_IMAGE:figures/full_fig_p016_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Simulating attacks to get the right amount of guards on each red vertex. [PITH_FULL_IMAGE:figures/full_fig_p017_15.png] view at source ↗
read the original abstract

Given a graph $G$, guards are placed on vertices of $G$. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum number of guards such that the graph can be defended indefinitely. In this paper we study the m-eternal domination number of cactus graphs, that is, connected graphs where each edge lies in at most two cycles, and we consider three variants of the m-eternal domination number: first variant allows multiple guards to occupy a single vertex, second variant does not allow it, and in the third variant additional "eviction" attacks must be defended. We provide a new upper bound for the m-eternal domination number of cactus graphs, and for a subclass of cactus graphs called Christmas cactus graphs, where each vertex lies in at most two cycles, we prove that these three numbers are equal. Moreover, we present a linear-time algorithm for computing them.

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 / 3 minor

Summary. The paper studies three variants of the m-eternal domination number on cactus graphs (connected graphs in which each edge lies in at most two cycles). It establishes a new upper bound that holds for all cactus graphs. For the subclass of Christmas cactus graphs (each vertex lies in at most two cycles), it proves that the three variants coincide and supplies a linear-time algorithm based on a structural decomposition and dynamic-programming recurrence.

Significance. If the proofs and algorithm are correct, the work supplies both a tight characterization for Christmas cactus graphs and an efficient computation method, strengthening the algorithmic theory of eternal domination parameters on graphs of bounded treewidth-like structure. The explicit recurrence and linear-time claim are concrete strengths.

minor comments (3)
  1. The abstract states the existence of proofs and a linear-time algorithm but does not indicate the running-time analysis or the precise form of the recurrence; a one-sentence pointer to the relevant section would improve readability.
  2. Notation for the three variants (multiple occupancy, single occupancy, eviction) is introduced only in the abstract; consistent symbols should be defined at first use in §2 or §3.
  3. The upper-bound statement for general cactus graphs is not accompanied by a matching lower-bound example or tightness discussion; adding one sentence in the introduction would clarify its strength.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation of minor revision. The assessment correctly identifies the main contributions: the new upper bound on m-eternal domination for general cactus graphs, the equality of the three variants on Christmas cactus graphs, and the linear-time algorithm via structural decomposition and dynamic programming. No specific major comments were raised.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives its upper bound, equality result for Christmas cactus graphs, and linear-time algorithm via explicit structural decomposition into cycles and a dynamic-programming recurrence on the graph class. These steps are defined directly from the standard m-eternal domination rules and the cactus/Christmas-cactus definitions; no parameter is fitted and then renamed as a prediction, no self-citation supplies a load-bearing uniqueness theorem, and no ansatz is smuggled in. The central claims therefore remain independent of their own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definitions of graphs, cycles, and the m-eternal domination process; no free parameters, ad-hoc constants, or new postulated entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of undirected graphs, cycles, and the m-eternal domination process with guard movement along edges.
    The paper invokes these background notions to define the problem and the graph classes.

pith-pipeline@v0.9.0 · 5733 in / 1217 out tokens · 20093 ms · 2026-05-24T19:42:44.422025+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

12 extracted references · 12 canonical work pages

  1. [1]

    de Souza, and Orlando Lee

    Andrei Braga, Cid C. de Souza, and Orlando Lee. The eternal dominating set problem for proper interval graphs. Information Processing Letters , 115(6):582– 587, 2015

    work page 2015

  2. [2]

    Burger, Ernest J

    Alewyn P. Burger, Ernest J. Cockayne, W. R. Gr¨ undlingh, Christina M. Mynhardt, Jan H. van Vuuren, and Wynand Winterbach. Infinite order domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing , 50:179–194, 2004

    work page 2004

  3. [3]

    van Bommel

    Stephen Finbow, Margaret-Ellen Messinger, and Martin F. van Bommel. Eternal domination on 3 × n grid graphs. Australasian Journal of Combinatorics , 61:156– 174, 2015

    work page 2015

  4. [4]

    Hedetniemi, and Stephen T

    Wayne Goddard, Sandra M. Hedetniemi, and Stephen T. Hedetniemi. Eternal se- curity in graphs. Journal of Combinatorial Mathematics and Combinatorial Com- puting, 52:169–180, 2005

    work page 2005

  5. [5]

    Gupta, Der-Tsai Lee, and Joseph Y.-T

    Udaiprakash I. Gupta, Der-Tsai Lee, and Joseph Y.-T. Leung. Efficient algorithms for interval graphs and circular arc graphs. Networks, 12(4):459–467, 1982

    work page 1982

  6. [6]

    Graph Theory

    Frank Harary. Graph Theory. Addison-Wesley Publishing Company, Inc., 1969

    work page 1969

  7. [7]

    Henning, William F

    Michael A. Henning, William F. Klostermeyer, and Gary MacGillivray. Bounds for the m-eternal domination number of a graph. Contributions to Discrete Math- ematics, 12(2), 2017

    work page 2017

  8. [8]

    Klostermeyer and Gary MacGillivray

    William F. Klostermeyer and Gary MacGillivray. Eternal dominating sets in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing , 68:97–111, February 2009

    work page 2009

  9. [9]

    Klostermeyer and Christina M

    William F. Klostermeyer and Christina M. Mynhardt. Protecting a graph with mobile guards. Applicable Analysis and Discrete Mathematics , 10, 07 2014

    work page 2014

  10. [10]

    Some results on greedy embeddings in metric spaces

    Tom Leighton and Ankur Moitra. Some results on greedy embeddings in metric spaces. Discrete & Computational Geometry , 44(3):686–705, Oct 2010

    work page 2010

  11. [11]

    Depth-first search and linear graph algorithms

    Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146–160, 1972

    work page 1972

  12. [12]

    van Bommel and Martin F

    Christopher M. van Bommel and Martin F. van Bommel. Eternal domination numbers of 5 × n grid graphs. Journal of Combinatorial Mathematics and Com- binatorial Computing , 97:83–102, 2016

    work page 2016