pith. sign in

arxiv: 2606.27175 · v1 · pith:IDX2RSKBnew · submitted 2026-06-25 · 🧮 math.CO

Signed Total Roman Domination and Domatic Numbers: Degree Three and Complete Multipartite Graphs

Arie M. C. A. Koster , Lutz Volkmann , Moritz Wehrmann This is my paper

Pith reviewed 2026-06-26 03:27 UTC · model grok-4.3

classification 🧮 math.CO
keywords signed total Roman domination numbersigned total Roman domatic numbercubic graphscomplete multipartite graphsNP-completenessopen packing number2-tuple total domination numbersigned total domination number
0
0 comments X

The pith

Having a degree-3 vertex determines a graph's signed total Roman domatic number.

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

The paper relates the signed total Roman domination number of cubic graphs to their open packing number, 2-tuple total domination number, and signed total domination number. These relations produce sharp bounds and establish NP-completeness results for all four invariants. It demonstrates that the signed total Roman domatic number of any graph is fixed once the graph contains a degree-3 vertex. This fact, together with earlier results, shows the associated decision problem is solvable in polynomial time for graphs whose maximum degree is at most three and NP-complete otherwise. Exact values of both the domination and domatic numbers are obtained for complete multipartite graphs.

Core claim

For cubic graphs the signed total Roman domination number is related to the open packing number, the 2-tuple total domination number, and the signed total domination number; these relations give sharp bounds and prove that computing each of the four numbers is NP-complete. The signed total Roman domatic number of an arbitrary graph is completely determined by the presence or absence of a degree-3 vertex. Consequently the decision problem for the domatic number lies in P when the maximum degree is at most three and is NP-complete when the maximum degree exceeds three. Despite their simple structure, the signed total Roman domination and domatic numbers can be computed exactly for every comple

What carries the argument

The signed total Roman dominating function f mapping vertices to {-1,1,2} that satisfies the neighborhood-sum condition and the adjacency condition for negative values, together with families of such functions whose pointwise sums are at most 1.

If this is right

  • The signed total Roman domination number of cubic graphs satisfies sharp bounds expressed via the open packing number, the 2-tuple total domination number, and the signed total domination number.
  • Computing the signed total Roman domination number, the open packing number, the 2-tuple total domination number, and the signed total domination number is NP-complete even when restricted to cubic graphs.
  • The signed total Roman domatic number of any graph is fixed by the existence of a degree-3 vertex.
  • The decision problem for the signed total Roman domatic number is solvable in polynomial time precisely when the maximum degree is at most three.
  • The decision problem for the signed total Roman domatic number is NP-complete when the maximum degree exceeds three.
  • Signed total Roman domination and domatic numbers admit exact determinations on all complete multipartite graphs.

Where Pith is reading between the lines

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

  • The degree-based separation into polynomial and NP-complete cases may indicate a general pattern for other Roman-style domination parameters.
  • Exact formulas on complete multipartite graphs supply test instances that could be used to evaluate heuristics for the general case.
  • The four invariants become interchangeable for complexity purposes on cubic graphs once the relations are established.

Load-bearing premise

Having a degree-3 vertex determines a graph's signed total Roman domatic number for all graphs.

What would settle it

A polynomial-time algorithm that computes the signed total Roman domatic number for graphs whose maximum degree is four or greater would falsify the NP-completeness claim.

read the original abstract

Signed total Roman domination is a variant of the classic Roman domination-problem in graphs. A signed total Roman dominating function (STRD function) on a graph $G=(V,E)$ is a function $f: V \to \{-1,1,2\}$ such that (i) $\sum_{u \in N(v)} f(u) \geq 1$ for all $v \in V$, where $N(v)$ denotes the neighborhood of $v$, and (ii) every vertex $v$ with $f(v) = -1$ is adjacent to a vertex $u$ with $f(u) = 2$. The weight of $f$ is $\sum_{v \in V} f(v)$. The signed total Roman domination number of $G$ is the minimum weight among all its STRD functions. A signed total Roman dominating family (STRD family) on $G$ is a family $\{f_1, \ldots, f_d\}$ of pairwise distinct STRD functions such that $\sum_{i=1}^{d} f_i(v) \leq 1$ for all $v \in V$. The signed total Roman domatic number of $G$ is the maximum size among all its STRD families. In this paper, we relate the signed total Roman domination number of a cubic graph to its open packing number, 2-tuple total domination number, and signed total domination number, allowing us to derive sharp bounds on the first invariant and to establish new $\mathcal{NP}$-completeness results for all four invariants. We demonstrate that having a degree-3 vertex determines a graph's signed total Roman domatic number. Combined with known results this implies that the associated decision problem is easy for graphs with maximum degree at most three and $\mathcal{NP}$-complete otherwise. To contrast these general hardness results, we determine signed total Roman domination and domatic numbers in complete multipartite graphs. Despite their simple structure, this is a non-trivial task.

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

2 major / 2 minor

Summary. The manuscript studies signed total Roman domination and domatic numbers. For cubic graphs it relates the signed total Roman domination number to the open packing number, 2-tuple total domination number and signed total domination number, yielding sharp bounds and new NP-completeness results for all four invariants. It asserts that the presence of a degree-3 vertex determines the signed total Roman domatic number, which together with prior results implies the decision problem is polynomial-time solvable for maximum degree at most 3 and NP-complete otherwise. Exact values are also computed for complete multipartite graphs.

Significance. If the relations and the degree-3 determination hold, the work supplies new sharp bounds, a clean complexity dichotomy for the domatic decision problem, and exact determinations on an important graph family. The NP-completeness results across multiple related invariants would be a solid contribution to the literature on signed domination parameters.

major comments (2)
  1. [Section establishing the domatic-number determination (likely §4)] The central claim that the presence of any degree-3 vertex determines the signed total Roman domatic number (used to obtain the poly-time / NP-complete dichotomy) is load-bearing yet asserted without an explicit argument or lemma in the abstract; the manuscript must supply the complete reasoning, including any necessary conditions on the graph (e.g., no isolated vertices), and verify it holds for all graphs.
  2. [Section on cubic graphs (likely §3)] The claimed relations between the signed total Roman domination number of a cubic graph and its open packing number, 2-tuple total domination number, and signed total domination number must be derived explicitly; any step that relies on post-hoc parameter choices or unstated assumptions would undermine the sharpness of the resulting bounds and the NP-completeness reductions.
minor comments (2)
  1. [Abstract] The abstract states the main results but does not indicate the specific bounds obtained for cubic graphs; adding one or two concrete inequalities would improve readability.
  2. [Definitions and notation] Notation for the STRD family and the weight function should be cross-checked against the definitions of the related invariants (open packing, 2-tuple total domination) to ensure consistent use of symbols throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [Section establishing the domatic-number determination (likely §4)] The central claim that the presence of any degree-3 vertex determines the signed total Roman domatic number (used to obtain the poly-time / NP-complete dichotomy) is load-bearing yet asserted without an explicit argument or lemma in the abstract; the manuscript must supply the complete reasoning, including any necessary conditions on the graph (e.g., no isolated vertices), and verify it holds for all graphs.

    Authors: We agree that the determination of the signed total Roman domatic number by the presence of a degree-3 vertex requires an explicit argument. The manuscript states the result and uses it for the complexity dichotomy, but the full reasoning (including the no-isolated-vertices condition inherent to total-domination-type parameters) is not presented as a standalone lemma. In the revision we will insert a complete proof verifying the claim for all graphs satisfying the necessary conditions. revision: yes

  2. Referee: [Section on cubic graphs (likely §3)] The claimed relations between the signed total Roman domination number of a cubic graph and its open packing number, 2-tuple total domination number, and signed total domination number must be derived explicitly; any step that relies on post-hoc parameter choices or unstated assumptions would undermine the sharpness of the resulting bounds and the NP-completeness reductions.

    Authors: We agree that the relations must be derived with full explicitness. The manuscript contains proofs linking the signed total Roman domination number on cubic graphs to the open packing number, the 2-tuple total domination number, and the signed total domination number, but we will expand these derivations in the revision to eliminate any possibility of implicit steps or unstated assumptions, thereby confirming the sharpness of the bounds and the validity of the NP-completeness reductions. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper defines new invariants (STRD function, signed total Roman domination number, STRD family, signed total Roman domatic number) and claims to prove relations to prior invariants plus a determination result for the domatic number based on presence of a degree-3 vertex. The abstract states these are demonstrated in the paper and combined with known results for complexity conclusions. No equations or text in the provided material show any result reducing by construction to its inputs, fitted parameters called predictions, or load-bearing self-citations whose justification collapses to the present work. The central claims are presented as combinatorial proofs, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard definitions of graphs and neighborhoods plus the newly introduced STRD function and family; no free parameters or invented physical entities appear in the abstract.

axioms (2)
  • standard math Graphs are finite undirected simple graphs with neighborhoods N(v).
    Foundational assumption invoked in the definition of STRD functions.
  • domain assumption The weight and family conditions on functions f: V to {-1,1,2} are well-defined and comparable across graphs.
    Core to defining the domination and domatic numbers.

pith-pipeline@v0.9.1-grok · 5919 in / 1528 out tokens · 80011 ms · 2026-06-26T03:27:54.037386+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

26 extracted references · 23 canonical work pages

  1. [1]

    Signed double Roman domination in graphs

    H. Abdollahzadeh Ahangar, M. Chellali, and S. M. Sheikholeslami. “Signed double Roman domination in graphs”.Discrete Appl. Math.257 (2019), pp. 1–11.doi: 10.1016/j.dam.2018.09.009

    work page doi:10.1016/j.dam.2018.09.009 2019

  2. [2]

    Signed Roman domination in graphs

    H. Abdollahzadeh Ahangar, M. A. Henning, C. Löwenstein, Y. Zhao, and V. Samodi- vkin. “Signed Roman domination in graphs”.J. Comb. Optim.27.2 (2014), pp. 241–

    2014

  3. [3]

    doi: 10.1007/s10878-012-9500-0

    work page doi:10.1007/s10878-012-9500-0

  4. [4]

    Total Roman domination in graphs

    H. Abdollahzadeh Ahangar, M. A. Henning, V. Samodivkin, and I. G. Yero. “Total Roman domination in graphs”.Appl. Anal. Discrete Math.10.2 (2016), pp. 501–517. doi: 10.2298/AADM160802017A

    work page doi:10.2298/aadm160802017a 2016

  5. [5]

    Double Roman domination

    R. A. Beeler, T. W. Haynes, and S. T. Hedetniemi. “Double Roman domination”. Discrete Appl. Math.211 (2016), pp. 23–29.doi: 10.1016/j.dam.2016.03.017

    work page doi:10.1016/j.dam.2016.03.017 2016

  6. [6]

    Discrete Applied Mathematics305, 311–328 (2021) https://doi.org/10.1016/j.dam

    M. Chellali, T. W. Haynes, S. T. Hedetniemi, and A. A. McRae. “Roman {2}- domination”.Discrete Appl. Math.204 (2016), pp. 22–28.doi: 10.1016/j.dam. 2015.11.013

    work page doi:10.1016/j.dam 2016

  7. [7]

    Varieties of Roman domination II

    M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, and L. Volkmann. “Varieties of Roman domination II”.AKCE Int. J. Graphs Comb.17.3 (2020), pp. 966–984.doi: 10.1016/j.akcej.2019.12.001

    work page doi:10.1016/j.akcej.2019.12.001 2020

  8. [9]

    The Roman domatic problem in graphs and digraphs: A survey

    M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, and L. Volkmann. “The Roman domatic problem in graphs and digraphs: A survey”.Discuss. Math. Graph Theory 42.3 (2022), pp. 861–891.doi: 10.7151/dmgt.2313

    work page doi:10.7151/dmgt.2313 2022

  9. [10]

    The Roman domatic problem in graphs and digraphs II: A survey

    M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, and L. Volkmann. “The Roman domatic problem in graphs and digraphs II: A survey”.Discuss. Math. Graph Theory 46.2 (2026), pp. 527–554.doi: 10.7151/dmgt.2616

    work page doi:10.7151/dmgt.2616 2026

  10. [11]

    Sucu and I

    E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi, and S. T. Hedetniemi. “Roman domination in graphs”.Discrete Math.278.1-3 (2004), pp. 11–22.doi: 10.1016/j. disc.2003.06.004

    work page doi:10.1016/j 2004

  11. [12]

    Complexity aspects of the computation of the rank of a graph

    I. da Fonseca Ramos, V. F. dos Santos, and J. L. Szwarcfiter. “Complexity aspects of the computation of the rank of a graph”.Discrete Math. Theor. Comput. Sci. 16.2 (2014), pp. 73–86.doi: 10.46298/dmtcs.2075

    work page doi:10.46298/dmtcs.2075 2014

  12. [13]

    M. R. Garey and D. S. Johnson.Computers and intractability. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, CA, 1979, pp. x+338

    1979

  13. [14]

    Signed total Roman domination and domatic numbers in graphs

    Y. Guo, L. Volkmann, and Y. Wang. “Signed total Roman domination and domatic numbers in graphs”.Appl. Math. Comput. 487 (2025), Paper No. 129074. doi: 10.1016/j.amc.2024.129074

    work page doi:10.1016/j.amc.2024.129074 2025

  14. [15]

    T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, eds.Topics in domination in graphs. Vol. 64. Developments in Mathematics. Springer, Cham, 2020, pp. viii+545. doi: 10.1007/978-3-030-51117-3

    work page doi:10.1007/978-3-030-51117-3 2020

  15. [16]

    T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, eds.Structures of domination in graphs. Vol. 66. Developments in Mathematics. Springer, Cham, 2021, pp. viii+536. doi: 10.1007/978-3-030-58892-2

    work page doi:10.1007/978-3-030-58892-2 2021

  16. [17]

    T. W. Haynes, S. T. Hedetniemi, and M. A. Henning.Domination in graphs: Core concepts. Springer Monographs in Mathematics. Springer, Cham, 2023, pp. xx+644. doi: 10.1007/978-3-031-09496-5

    work page doi:10.1007/978-3-031-09496-5 2023

  17. [18]

    Signed total domination in graphs

    M. A. Henning. “Signed total domination in graphs”.Discrete Math.278.1-3 (2004), pp. 109–125.doi: 10.1016/j.disc.2003.06.002

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

  18. [19]

    Open packing in graphs

    M. A. Henning and P. J. Slater. “Open packing in graphs”.J. Combin. Math. Combin. Comput.29 (1999), pp. 3–16

    1999

  19. [20]

    Strong transversals in hypergraphs and double total domination in graphs

    M. A. Henning and A. Yeo. “Strong transversals in hypergraphs and double total domination in graphs”.SIAM J. Discrete Math.24.4 (2010), pp. 1336–1355.doi: 10.1137/090777001

    work page doi:10.1137/090777001 2010

  20. [21]

    Complexity of signed total k-Roman domination problem in graphs

    S. Kosari, Y. Rao, Z. Shao, J. Amjadi, and R. Khoeilar. “Complexity of signed total k-Roman domination problem in graphs”.AIMS Math.6.1 (2021), pp. 952–961.doi: 10.3934/math.2021057

    work page doi:10.3934/math.2021057 2021

  21. [22]

    Algorithmic aspects ofk-tuple total domination in graphs

    D. Pradhan. “Algorithmic aspects ofk-tuple total domination in graphs”.Inform. Process. Lett.112.21 (2012), pp. 816–822.doi: 10.1016/j.ipl.2012.07.010. 26

    work page doi:10.1016/j.ipl.2012.07.010 2012

  22. [23]

    The Roman domatic number of a graph

    S. M. Sheikholeslami and L. Volkmann. “The Roman domatic number of a graph”. Appl. Math. Lett.23.10 (2010), pp. 1295–1300.doi: 10.1016/j.aml.2010.06.016

    work page doi:10.1016/j.aml.2010.06.016 2010

  23. [24]

    On the signed total Roman domination and domatic numbers of graphs

    L. Volkmann. “On the signed total Roman domination and domatic numbers of graphs”.Discrete Appl. Math.214 (2016), pp. 179–186.doi: 10.1016/j.dam.2016. 06.006

    work page doi:10.1016/j.dam.2016 2016

  24. [25]

    Signed total Roman domination in graphs

    L. Volkmann. “Signed total Roman domination in graphs”.J. Comb. Optim.32.3 (2016), pp. 855–871.doi: 10.1007/s10878-015-9906-6

    work page doi:10.1007/s10878-015-9906-6 2016

  25. [26]

    Efficient total domination and related invariants in torus graphs

    M. Wehrmann and A. M. C. A. Koster. “Efficient total domination and related invariants in torus graphs”.Discrete Appl. Math.389 (2026), pp. 106–118.doi: 10.1016/j.dam.2026.03.047

    work page doi:10.1016/j.dam.2026.03.047 2026

  26. [27]

    Signed Roman (total) domination numbers of complete bipartite graphs and wheels

    Y. Zhao and L. Miao. “Signed Roman (total) domination numbers of complete bipartite graphs and wheels”.Commun. Math. Res.33 (2017), pp. 318–326.doi: 10.13447/j.1674-5647.2017.04.04. 27

    work page doi:10.13447/j.1674-5647.2017.04.04 2017