Small domination-type invariants in random graphs
Pith reviewed 2026-05-25 14:44 UTC · model grok-4.3
The pith
The c-self domination number unifies three domination invariants and is analyzed asymptotically in random graphs for small c.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
A function f : V(G) → {0,1,c} is c-self dominating if every vertex u satisfies f(u) ≥ c or max{f(v) : v adjacent to u} ≥ 1; its minimum weight is the c-self domination number. This parameter simultaneously generalizes domination, total domination and Roman domination, and the paper studies its value in random graphs when c is small.
What carries the argument
The c-self dominating function (values in {0,1,c} with the coverage condition) whose minimum weight recovers the three classical invariants for suitable choices of c.
If this is right
- The three classical domination numbers become special cases of a single parameter.
- Any asymptotic formula derived for small c applies simultaneously to the three invariants.
- Concentration or threshold results for the c-self domination number follow directly in the Erdős–Rényi model.
Where Pith is reading between the lines
- A single proof technique might now cover asymptotic statements that previously required separate arguments for each of the three invariants.
- The same definition could be used to compare the three parameters on other graph classes or random models without re-deriving the function each time.
- Numerical checks on moderate-sized random graphs could test whether the predicted small-c regime begins at the values of c suggested by the analysis.
Load-bearing premise
The c-self domination number admits a non-trivial asymptotic description that does not collapse to a constant in the chosen random-graph model when c is small.
What would settle it
Explicit computation showing that the c-self domination number equals a fixed integer independent of n for all sufficiently large n in G(n,1/2) when c = 0.5 would falsify the claim of non-trivial behavior.
read the original abstract
For $c\in \mathbb{R}^{+}\cup \{\infty \}$ and a graph $G$, a function $f:V(G)\rightarrow \{0,1,c\}$ is called a $c$-self dominating function of $G$ if for every vertex $u\in V(G)$, $f(u)\geq c$ or $\max\{f(v):v\in N_{G}(u)\}\geq 1$ where $N_{G}(u)$ is the neighborhood of $u$ in $G$. The minimum weight $w(f)=\sum _{u\in V(G)}f(u)$ of a $c$-self dominating function $f$ of $G$ is called the $c$-self domination number of $G$. The $c$-self domination concept is a common generalization of three domination-type invariants; (original) domination, total domination and Roman domination. In this paper, we study a behavior of the $c$-self domination number in random graphs for small $c$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines a c-self dominating function f:V(G)→{0,1,c} (for c>0 or ∞) requiring that every vertex u either has f(u)≥c or has a neighbor v with f(v)≥1, and studies the minimum weight γ_c(G) of such an f. It positions this as a common generalization of ordinary domination, total domination, and Roman domination. The central results establish the asymptotic order of γ_c(G(n,p)) for small fixed c in the Erdős–Rényi model G(n,p), showing that an optimal mixture of 0’s and 1’s yields a strictly smaller leading term than the trivial cn bound, with explicit constants and concentration derived via the probabilistic method for stated ranges of c and p.
Significance. If the stated theorems hold, the work supplies a unified probabilistic analysis of three classical domination parameters inside a single parameterized family, with the key technical contribution being the derivation of a c- and p-dependent leading constant that is provably smaller than cn. The use of the probabilistic method to obtain both the asymptotic value and concentration is a clear strength; the results are falsifiable and do not reduce to the ordinary domination number.
minor comments (3)
- [§2] §2, Definition 2.1: the case c=∞ is introduced but the subsequent theorems appear to treat only finite c; a brief remark clarifying whether the ∞ case is subsumed or handled separately would improve readability.
- [Theorem 4.3] Theorem 4.3: the statement gives the leading term but does not explicitly record the error term or the probability of the concentration event; adding the precise failure probability (even if 1-o(1)) would make the result easier to cite.
- [References] The bibliography omits several recent papers on Roman domination in random graphs (e.g., works post-2015); adding two or three key references would strengthen the positioning of the generalization.
Simulated Author's Rebuttal
We thank the referee for the careful reading and the positive assessment of the manuscript. The recommendation of minor revision is appreciated. No specific major comments were provided in the report, so we interpret the minor revision as addressing any small editorial or presentational issues that may arise during the revision process.
Circularity Check
No significant circularity; derivation self-contained
full rationale
The paper introduces the c-self domination number via an explicit definition that generalizes three standard domination parameters without defining any quantity in terms of itself. Asymptotic results for this parameter in G(n,p) are obtained via the probabilistic method, with explicit thresholds and concentration statements derived from first-principles counting arguments rather than from fitted parameters or self-citations. No load-bearing step reduces a claimed prediction to a prior fit, a self-citation chain, or a renaming of a known result; the central claims remain independent of the inputs they analyze.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
S. Bermudo, H. Fernau and J.M. Sigarreta, The differential and t he roman domination number of a graph, Appl. Anal. Discrete Math. 8 (2014) 155–171
work page 2014
-
[2]
A. Bonato and C. Wang, A note on domination parameters in rando m graphs, Discuss. Math. Graph Theory 28 (2008) 335–343
work page 2008
-
[3]
E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetnie mi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22
work page 2004
-
[4]
Furuya, A continuous generalization of domination-like invarian ts, preprint
M. Furuya, A continuous generalization of domination-like invarian ts, preprint
-
[5]
T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Do mination in Graphs, Marcel Dekker, Inc. New York (1998)
work page 1998
-
[6]
T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination inn Graph s: Advanced Topics, Marcel Dekker, Inc. New York (1998)
work page 1998
-
[7]
M.A. Henning and A. Yeo, Total domination in graphs, Springer Mon ographs in Mathematics. Springer, New York, (2013)
work page 2013
-
[8]
Stewart, Defend the Roman Empire!, Sci
I. Stewart, Defend the Roman Empire!, Sci. Am. 281 (1999) 136–139
work page 1999
-
[9]
B. Wieland and A.P. Godbole, On the domination number of a random g raph, Electron. J. Combin. 8 (2001) #R37. 9
work page 2001
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.