m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs

Federico Cor\`o; Giacomo Paesani; Neeldhara Misra; Saraswati G. Nanoti; Tiziana Calamoneri

REVIEW 4 major objections 5 minor 26 references

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read m-Eternal domination is NP-hard on bipartite diameter-four and split graphs; on four infinite regular grids, eternal domination needs no more guards than ordinary domination.

desk verdict Three of the four grid theorems are solid; the hexagonal-grid proof is genuinely broken, and the Italian-domination reduction has gaps a referee will not overlook. read the letter →

arxiv 2507.09283 v1 pith:EC6Z4CYK submitted 2025-07-12 cs.DM cs.CCcs.DSmath.CO

Tiziana Calamoneri , Federico Corò , Neeldhara Misra , Saraswati G. Nanoti , Giacomo Paesani This is my paper · ORCID

classification cs.DMcs.CCcs.DSmath.CO MSC 05C6905C5768Q17

keywords m-eternaldominationeternalgameRomanItalianNP-hardnesssplitgraphsbipartiteinfinitegrids

open problems P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies the m-eternal domination game, where a defender places guards on a graph and must keep the guarded vertices a dominating set while repelling an infinite sequence of attacks; each turn the attacker names a vertex and the defender moves any number of guards one edge, with one guard landing on the attacked vertex. On finite graphs, the paper proves that the decision problems for m-eternal domination, m-eternal Roman domination, and m-eternal Italian domination, together with their connected variants, are NP-hard even on very restricted graph classes: bipartite graphs of diameter four for the first, and split graphs for the Roman and Italian versions. On four infinite regular grids—square, octagonal, hexagonal, and triangular—the paper constructs a single dominating set that is strongly optimal and also an m-eternal dominating set, so these grids can be defended forever with exactly as many guards as ordinary domination requires. The interest is that eternal defense can be achieved at no extra cost in guarding density on these natural infinite graphs, while the finite problem remains computationally hard in narrow classes.

What carries the argument

The carrying mechanism for the hardness results is a two-step template: first, show that if a graph has a connected dominating set $Z$, then an extra floating guard turns a static dominating configuration into an eternal one (for Roman domination, two guards on each vertex of $Z$ plus one floating guard; for Italian domination, the support of an Italian dominating function plus one floating guard). Then reduce from Dominating Set by building an auxiliary graph—bipartite for Theorem 1, split for Theorems 2 and 3—where the extra construction forces a winning guard configuration to encode a dominating set of the original graph. For the grids, the central object is a strongly optimal dominating set, a set $S$ such that every vertex's closed neighborhood intersects $S$ in exactly one vertex; the closed neighborhoods of $S$ partition the grid. The guard response is a combinatorial translation (or, for the hexagonal grid, a parity-split movement) that carries $S$ to another translate of itself or to a set that is claimed to be another strongly optimal dominating set, preserving the partition property.

What would settle it

On the hexagonal grid, apply the exact movement prescribed in Theorem 6 to an attack and inspect every vertex's closed neighborhood; finding a single vertex whose closed neighborhood contains two guards after the move would falsify the assertion that the set remains a strongly optimal dominating set. On the finite side, a polynomial-time algorithm for m-eternal domination on bipartite graphs of diameter four, or for the Roman or Italian variants on split graphs, would contradict the NP-hardness theorems unless P=NP.

Watch

Extended reading notes

Core claim

For the infinite grids, the central discovery is that there exist vertex subsets $S$ whose closed neighborhoods partition the vertex set—the paper calls such sets strongly optimal dominating sets—and that the same $S$ is an m-eternal dominating set. For the square, octagonal, hexagonal, and triangular grids, the guard-movement strategy is: when a vertex not in $S$ is attacked, every guard moves along the same pattern (a translation for the square, octagonal, and triangular grids; a two-part movement splitting the two parity classes for the hexagonal grid), and the resulting configuration is again a strongly optimal dominating set. Consequently $\gamma_\infty(T_4)=\gamma(T_4)$, $\gamma_\infty(T_8)=\gamma(T_8)$, $\gamma_\infty(T_3)=\gamma(T_3)$, and $\gamma_\infty(T_6)=\gamma(T_6)$ in the strong-optimality sense. In finite graphs, the paper establishes NP-hardness: m-Eternal Domination is NP-hard on bipartite graphs of diameter four via a reduction from Dominating Set, and m-Eternal Roman Domination and m-Eternal Italian Domination are NP-hard on split graphs via related reductions that also cover the connected variants.

Load-bearing premise

The load-bearing premise is the assertion in the hexagonal-grid proof that after the parity-split guard movement the guards still occupy a strongly optimal dominating set, a claim the proof states without a coordinate-by-coordinate check.

Editorial extensions

If this is right

If the reductions are correct, the m-eternal domination number, m-eternal Roman domination number, and m-eternal Italian domination number cannot be computed in polynomial time unless P=NP, even when inputs are restricted to bipartite graphs of diameter four (for m-eternal domination) or to split graphs (for the Roman and Italian variants).
On each of the four infinite grids, ordinary domination number and m-eternal domination number coincide in the strong-optimality sense, so no extra guards are needed for eternal defense compared with static domination.
The connected variants are as hard as the non-connected ones on the same graph classes, because the constructed configurations remain connected throughout the winning strategies.
The strongly optimal dominating sets provide a uniform upper bound on guard density for square, octagonal, hexagonal, and triangular grids, and by the injection-based optimality lemma these sets are at least as good as any other dominating set.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension is to verify coordinate by coordinate that the parity-split response on the hexagonal grid preserves the strong-optimality partition; if it does, the same strategy pattern gives a template for other periodic grids with two-color vertex partitions.
The reductions are likely transferable to any graph class where Dominating Set or Italian Domination is hard and where the auxiliary graph can be built; the bipartite-diameter-four and split classes are chosen because they make the encoding clean, not because the technique is specific to them.
The strongly optimal sets for the four grids are all periodic patterns, so one could compute the exact m-eternal domination density for every finite rectangular region cut from these grids and compare with the known $O(n+m)$ gaps for finite square grids.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my read on 2507.09283. The paper splits into two halves. The infinite-grid work is uneven: square, octagonal, and triangular grids are done cleanly, while the hexagonal grid case is broken as written. The complexity half has plausible hardness results, but two of the three reductions have gaps a referee will not overlook.

Credit where it's due. The 'strongly optimal' perfect-code framework is fine; Lemma 1 is a standard injectivity argument and it's correct. For T4, T8, and T6 the sets are genuine perfect codes and the defense is an honest translation of the entire guard set by the attack vector, so the invariant survives a single attack and all later attacks. Those three theorems look correct. Lemmas 2-4 (floating-guard upper bounds, connected versions included) are also correct. The citation pattern is appropriate—the relevant split-graph and finite-grid prior work is acknowledged.

Where it breaks. Theorem 6, the hexagonal grid, has a real flaw, and the stress-test note is right. The response to an upward attack sends S⊢ up by (0,1) and S⊣ down by (0,-1). Writing S = L ∪ (L-(1,0)), the new set is (L+(0,1)) ∪ (L-(1,1)), which is not a translate of S: any translation would require (0,2) ∈ L, and the lattice generated by (2,2) and (3,-1) does not contain (0,2). So the assertion 'the new position is a translation' is false, the post-attack configuration is never shown to be dominating, and the strategy cannot be iterated. The right-attack case has the same defect. The result may be salvageable—spot checks show the post-attack set locally looks like a perfect code—but the paper supplies neither the verification nor an invariant, so Theorem 6 is unproved as written.

The complexity proofs need work too. Theorem 1's reverse direction asserts, in one sentence, that a configuration with exactly one guard on P and one on w can be forced by attacking a P vertex. That needs an argument: a defender could keep guards off P and dominate P through w, and the attack dynamics have to force the guard on w to move. Probably repairable. Theorem 3's forward direction is more serious: the natural copy of an Italian function of G on A, with zeros on B, need not be an Italian dominating function of H—if f(vi)=1 and all G-neighbors are zero, the corresponding B-vertex has neighbor-sum 1. There is also a parameter mismatch (the instance is stated with k+1, the forward proof uses weight k), and the reverse direction assumes a guard in B without justification. Theorem 2's pigeonhole argument, by contrast, is essentially fine.

Bottom line: researchers working on domination games get real value from the three grid theorems and the reduction ideas, but as submitted this needs major revision. I'd send it to a referee—the hex case and the Italian reduction merit careful scrutiny—but I would not cite it in its current form.

Referee Report

4 major / 5 minor

Summary. This paper studies the m-eternal domination game and two weighted variants (Roman and Italian) in the m-eternal setting. The authors give polynomial-time reductions from Dominating Set and Italian Domination to show NP-hardness of m-Eternal Domination on bipartite graphs of diameter four (Theorem 1), m-Eternal Roman Domination on split graphs (Theorem 2), and m-Eternal Italian Domination on split graphs (Theorem 3). For infinite square, octagonal, hexagonal, and triangular grids, they exhibit strongly optimal dominating sets (perfect codes) and attempt to show that these sets are also m-eternal via translation or piecewise-movement strategies (Theorems 4-7). The paper introduces the notion of strong optimality for infinite graphs and proves that every strongly optimal dominating set is optimal (Lemma 1).

Significance. The results would be useful additions if the proofs are completed: the three NP-hardness theorems target natural restricted graph classes, and the grid constructions connect perfect codes with m-eternal domination in a clean way. Lemma 1 is correct, and the square, octagonal, and triangular grid constructions (Theorems 4, 5, and 7) are concise and appear sound because they use genuine translations. The reduction ideas in Theorems 1-3 are standard and plausible. However, several central proofs have load-bearing gaps: the reverse direction of Theorem 1 is not established, the forward direction of Theorem 3 applies Lemma 4 to an object that may not satisfy its hypotheses, the reverse direction of Theorem 3 assumes an unjustified initial configuration, and the hexagonal-grid defense in Theorem 6 does not produce the claimed translate and has no iterability argument. Because these gaps affect the main claims of the paper, substantial revision is needed.

major comments (4)

[Section 3, Theorem 1 (reverse direction)] The reduction's reverse direction depends on reaching a configuration in which P and w each have exactly one guard, and the proof claims that such a configuration can be obtained after attacking an unguarded vertex of P. This is not demonstrated and is false as stated: an attack on a vertex p in P must be answered by a guard moving from w to p, since w is the only neighbor of p, so the guard is removed from w; if P already contained guards, the result need not have exactly one guard on P. The case where every vertex of P is already guarded is also not addressed. Since the construction of the dominating set S of G requires the bound k on the number of guards outside P union {w}, this gap is load-bearing for the equivalence of the instances.
[Section 3, Theorem 3 (forward direction)] The forward direction invokes Lemma 4 with tf = k, but no Italian dominating function on H of weight k with connected support is actually defined. The natural choice f'(u_i) = f(v_i) and f' = 0 on B is not always Italian on H: a B-vertex w_i^{(j)} may see only one neighbor with value 1 (for example, if f(v_i) = 1 and v_i has no positive neighbor), giving neighbor-sum 1; and if the support of f has size 1, A-vertices outside the support also have neighbor-sum 1. Thus the claimed upper bound gamma_infty_I(H) <= k + 1 is not established by the argument given.
[Section 3, Theorem 3 (reverse direction)] The reverse direction assumes 'an initial configuration of k+1 guards such that B contains at least one guard.' This assumption is not justified: a winning strategy with k+1 guards might begin with all guards on A, since the Italian condition on B-vertices can be satisfied entirely from A. The proof needs to show that such an initial configuration can be chosen without loss of generality, or it must handle configurations with no guard in B.
[Section 4, Theorem 6] The prescribed piecewise guard movements do not produce a translate of S. In the first listed case, with s = (i*, j*) in S_even and attacked vertex v = (i*, j*+1), the rule sends even-parity guards by (0,1) and odd-parity guards by (0,-1). Writing S = L union (L-(1,0)) with L generated by (2,2) and (3,-1), the resulting set is (L+(0,1)) union (L-(1,1)), which is not a translate of S; no single translation can map both cosets correctly because L does not contain (0,2). The sentence 'The new position of the guards is a translation of S by one unit in the same direction' is therefore false. Moreover, the paper gives no invariant showing that the resulting configuration is dominating or that the strategy can be iterated for subsequent attacks, since the next attack occurs on a configuration not known to have the form of S. This leaves the m-eternal claim for the hexagonal grid unproved.

minor comments (5)

[Section 4, Theorem 6] The notation for the two parity classes is inconsistent: the text uses the same symbol (or near-identical symbols) for both S-sub-* and S-sub-* sets. Use S_0 and S_1, or another clearly distinguishable pair, throughout the proof.
[Section 3, Theorem 1] The sentence 'and that the considered configuration is not part of a winning strategy, a contradiction' is grammatically incomplete and should be rewritten; the missing logical dependency makes the reverse direction even harder to follow.
[Section 3, Theorem 3] There is a typo in 'm-Eternal Italiam Domination'; also, the definition of B in the construction is missing a closing brace and should be written as B = { w_i^{(j)} : 1 <= i <= n and 1 <= j <= n+2 }.
[Section 2.3] The definition of 'at least as good' via existence of an injective map is nonstandard and could be clarified by stating explicitly that it is a cardinality comparison; as written it is easy to confuse with a map between vertex sets of the graph.
[Throughout] Several grammatical slips should be corrected, for example 'the guards moves as follows', 'for every ... the guard on ... move to', and 'contains n+2 copies of V' instead of 'contain n+2 copies'. These do not affect the mathematics but should be fixed in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reasoning found: the NP-hardness reductions start from independent Dominating Set and Italian Domination problems, and the infinite-grid constructions are self-contained definitions and verification arguments.

full rationale

I walked the paper's derivation chain and found no step where a claimed result is equivalent to its input by construction. The hardness reductions in Theorems 1-3 are standard Karp-style reductions from Dominating Set and Italian Domination; the forward directions use constructive upper bounds (Lemmas 2-4) and the reverse directions argue directly from a hypothetical winning configuration to a dominating or Italian-dominating function on the source graph. Lemma 1 proves that strong optimality implies optimality directly from Definition 5, without assuming the conclusion. The infinite-grid proofs define the sets S explicitly, assert and partially verify the partition condition |N[s]∩S| = 1, and base the m-eternal strategy on translations of S, which is a self-contained invariant. The only self-citation is reference [6], used in Section 2.3 as an example of a density-based approach in related work; it is not load-bearing for any theorem. The reviewer-flagged issue in Theorem 6, where the two parity classes move by different vectors yet the proof calls the result a translation, is a potential correctness gap, not a circularity: it does not reduce a claimed derivation to its own inputs. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new entities or fitted parameters. Its central claims rest on standard graph theory background and on the correctness of the explicit coordinate-based constructions. The main unproved load-bearing step is the hexagonal grid movement in Theorem 6; the ledger records that as an ad hoc assumption.

assumptions (3)

standard math Dominating Set is NP-complete (Garey and Johnson, cited as [14]).
Used as the source problem in all three NP-hardness reductions (Theorems 1, 2, 3).
domain assumption The infinite grids are invariant under the translations used in the eternal strategies, so a translated copy of a strongly optimal dominating set remains a dominating set.
Theorems 4, 5, and 7 rely on the fact that shifting the entire guard set by the attack direction preserves the dominating property; this follows from translation invariance of the grids but is not stated explicitly.
ad hoc to paper In Theorem 6, the piecewise movement of guards (one parity class upward, the other downward) maps the strongly optimal set S to another dominating set.
This is the key step for the hexagonal grid. The paper asserts the new configuration is a translation of S and hence dominating, but the described movement is not a single translation and the preservation property is not proved.

how reviews work

0 comments

Cite this review

Pith. "Pith review of m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs." pith.science (2026). https://pith.science/paper/EC6Z4CYK

@misc{pith2026250709283,
  author       = {Pith},
  title        = {Pith review of: m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EC6Z4CYK}},
  note         = {Machine review of arXiv:2507.09283}
}

read the original abstract

We study the m-Eternal Domination problem, which is the following two-player game between a defender and an attacker on a graph: initially, the defender positions k guards on vertices of the graph; the game then proceeds in turns between the defender and the attacker, with the attacker selecting a vertex and the defender responding to the attack by moving a guard to the attacked vertex. The defender may move more than one guard on their turn, but guards can only move to neighboring vertices. The defender wins a game on a graph G with k guards if the defender has a strategy such that at every point of the game the vertices occupied by guards form a dominating set of G and the attacker wins otherwise. The m-eternal domination number of a graph G is the smallest value of k for which (G,k) is a defender win. We show that m-Eternal Domination is NP-hard, as well as some of its variants, even on special classes of graphs. We also show structural results for the Domination and m-Eternal Domination problems in the context of four types of infinite regular grids: square, octagonal, hexagonal, and triangular, establishing tight bounds.

Figures

Figures reproduced from arXiv: 2507.09283 by the authors.

**Figure 2.** The construction for the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** The construction for the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: On the left, graph T4 and, on the right, graph T8. In both figures, the black vertices represent the dominating set S described in the proof of Theorems 4 and of 5, respectively, while the shadowed zones represent how vertices of S dominate their neighbors, thus creati…

**Figure 5.** Figure 5: The graph T3. In both figures, the black vertices represent the dominating set S described in the proof of Theorem 6, while the shadowed zones represent how vertices of S dominate their neighbors, thus creating a partition of the vertices of the graph. On the left, th…

**Figure 6.** Figure 6: The graph T6. In both figures, the black vertices represent the dominating set S described in the proof of Theorem 7, while the shadowed zones represent how vertices of S dominate their neighbors, thus creating a partition of the vertices of the graph. On the left, th…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 22 canonical work pages

[1]

Bard, S., Duffy, C., Edwards, M., Macgillivray, G., Yang, F.: Eternal domination in splitgraphs.JournalofCombinatorialMathematicsandCombinatorialComputing 101, 121–130 (2017)

work page 2017
[2]

Methuen, London (1962)

Berge, C.: The theory of graphs and its applications. Methuen, London (1962)

work page 1962
[3]

Journal of Combinatorial Mathematics and Combinatorial Computing 97(83), 102 (2016)

van Bommel, C.M., van Bommel, M.F.: Eternal domination numbers of 5× n grid graphs. Journal of Combinatorial Mathematics and Combinatorial Computing 97(83), 102 (2016)

work page 2016
[4]

Contributions to Discrete Mathematics 2(2) (2007)

Bonato, A., Hahn, G., Wang, C.: The cop density of a graph. Contributions to Discrete Mathematics 2(2) (2007)

work page 2007
[5]

Journal of Combinatorial Mathematics and Combinatorial Computing50, 179–194 (2004)

Burger, A.P., Cockayne, E.J., Grundlingh, W., Mynhardt, C.M., van Vuuren, J.H., Winterbach, W.: Infinite order domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing50, 179–194 (2004)

work page 2004
[6]

(Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs

Calamoneri, T., Corò, F.: (Eternal) vertex cover number of infinite and finite grid graphs. arXiv preprint arXiv:2209.05102. A short version is available in the Proc. of ICTCS 20233587, 104–109 (2022)

work page Pith review arXiv 2022
[8]

A Note on Roman \{2\}-domination problem in graphs

Chen, H., Lu, C.: A note on roman 2-domination problem in graphs. arXiv preprint arXiv:1804.09338 (2018)

work page Pith review arXiv 2018
[9]

Discrete mathematics278(1-3), 11–22 (2004).https://doi.org/ 10.1016/J.DISC.2003.06.004

Cockayne,E.J.,DreyerJr,P.A., Hedetniemi,S.M.,Hedetniemi,S.T.:Romandomi- nation in graphs. Discrete mathematics278(1-3), 11–22 (2004).https://doi.org/ 10.1016/J.DISC.2003.06.004

work page doi:10.1016/j.disc.2003.06.004 2004

Show all 26 references

[10]

Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)

2012
[11]

RAIRO - Operations Research 57(4), 1905–1912 (2023)

Fernández, Lara, Leoni, Valeria: New complexity results on roman 2-domination. RAIRO - Operations Research 57(4), 1905–1912 (2023). https://doi.org/10. 1051/ro/2023049

2023
[12]

Australasian Journal of Combinatorics61, 156–174 (2015)

Finbow, S., Messinger, M., van Bommel, M.: Eternal domination in3 × n grids. Australasian Journal of Combinatorics61, 156–174 (2015)

2015
[13]

Australasian Journal of Combinatorics76, 1–23 (2020)

Finbow, S., van Bommel, M.F.: The eternal domination number for3 × n grid graphs. Australasian Journal of Combinatorics76, 1–23 (2020)

2020
[14]

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)

1979
[15]

Journal of Combinatorial Mathematics and Combinatorial Computing 52(01) (2005)

Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T.: Eternal security in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing 52(01) (2005)

2005
[16]

Utilitas Mathematica91, 47–64 (2013)

Goldwasser, J., Klostermeyer, W.F., Mynhardt, C.: Eternal protection in grid graphs. Utilitas Mathematica91, 47–64 (2013)

2013
[17]

SIAM Journal on Discrete Mathematics25(3), 1443–1453 (2011)

Gonçalves, D., Pinlou, A., Rao, M., Thomassé, S.: The domination number of grids. SIAM Journal on Discrete Mathematics25(3), 1443–1453 (2011). https: //doi.org/10.1137/11082574

2011 doi
[18]

Pure and applied mathematics, CRC press (2013)

Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of domination in graphs. Pure and applied mathematics, CRC press (2013)

2013
[19]

Discrete Ap- plied Mathematics 217, 557–564 (2017).https://doi.org/10.1016/J.DAM.2016

Henning, M.A., Klostermeyer, W.F.: Italian domination in trees. Discrete Ap- plied Mathematics 217, 557–564 (2017).https://doi.org/10.1016/J.DAM.2016. 09.035

2017 doi
[20]

Australasian Journal of Combinatorics45, 235–250 (2009) 18 T

Klostermeyer, W.F., Mynhardt, C.M.: Edge protection in graphs. Australasian Journal of Combinatorics45, 235–250 (2009) 18 T. Calamoneri et al

2009
[21]

Theoretical ComputerScience 794,27–46(2019)

Lamprou, I., Martin, R., Schewe, S.: Eternally dominating large grids. Theoretical ComputerScience 794,27–46(2019). https://doi.org/10.1016/J.TCS.2018.09. 008

2019 doi
[22]

Journal of Combinatorial Optimization 26(3), 608–619 (2013)

Liu, C.H., Chang, G.J.: Roman domination on strongly chordal graphs. Journal of Combinatorial Optimization 26(3), 608–619 (2013). https://doi.org/10.1007/ S10878-012-9482-Y

2013
[23]

Acta Informatica61, 357–382 (2024)

Mahendra Kumar, R., Sadagopan, N.: A closer look at hamiltonicity and domi- nation through the lens of diameter and convexity. Acta Informatica61, 357–382 (2024). https://doi.org/10.1007/s00236-024-00461-z

2024 doi
[24]

Contributions to Discrete Mathematics12(1) (2017)

Messinger, M.E.: Closing the gap: Eternal domination on3×n grids. Contributions to Discrete Mathematics12(1) (2017)

2017
[25]

Electronic Notes in Discrete Mathematics 50, 77–82 (2015)

Nascimento, S., Sampaio, R.: Roman domination in subgraphs of grids. Electronic Notes in Discrete Mathematics 50, 77–82 (2015). https://doi.org/10.1016/J. ENDM.2015.07.014

2015 doi
[26]

In: Colloquium Publications

Ore, O.: Theory of graphs. In: Colloquium Publications. American Mathematical Society (1962)

1962
[27]

ReVelle, C.: Can you protect the roman empire? Hopkins Magazine49(2), 40 (1997)

1997

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Bard, S., Duffy, C., Edwards, M., Macgillivray, G., Yang, F.: Eternal domination in splitgraphs.JournalofCombinatorialMathematicsandCombinatorialComputing 101, 121–130 (2017)

work page 2017

[2] [2]

Methuen, London (1962)

Berge, C.: The theory of graphs and its applications. Methuen, London (1962)

work page 1962

[3] [3]

Journal of Combinatorial Mathematics and Combinatorial Computing 97(83), 102 (2016)

van Bommel, C.M., van Bommel, M.F.: Eternal domination numbers of 5× n grid graphs. Journal of Combinatorial Mathematics and Combinatorial Computing 97(83), 102 (2016)

work page 2016

[4] [4]

Contributions to Discrete Mathematics 2(2) (2007)

Bonato, A., Hahn, G., Wang, C.: The cop density of a graph. Contributions to Discrete Mathematics 2(2) (2007)

work page 2007

[5] [5]

Journal of Combinatorial Mathematics and Combinatorial Computing50, 179–194 (2004)

Burger, A.P., Cockayne, E.J., Grundlingh, W., Mynhardt, C.M., van Vuuren, J.H., Winterbach, W.: Infinite order domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing50, 179–194 (2004)

work page 2004

[6] [6]

(Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs

Calamoneri, T., Corò, F.: (Eternal) vertex cover number of infinite and finite grid graphs. arXiv preprint arXiv:2209.05102. A short version is available in the Proc. of ICTCS 20233587, 104–109 (2022)

work page Pith review arXiv 2022

[7] [8]

A Note on Roman \{2\}-domination problem in graphs

Chen, H., Lu, C.: A note on roman 2-domination problem in graphs. arXiv preprint arXiv:1804.09338 (2018)

work page Pith review arXiv 2018

[8] [9]

Discrete mathematics278(1-3), 11–22 (2004).https://doi.org/ 10.1016/J.DISC.2003.06.004

Cockayne,E.J.,DreyerJr,P.A., Hedetniemi,S.M.,Hedetniemi,S.T.:Romandomi- nation in graphs. Discrete mathematics278(1-3), 11–22 (2004).https://doi.org/ 10.1016/J.DISC.2003.06.004

work page doi:10.1016/j.disc.2003.06.004 2004