A Note on Inequalities for Three Domination Parameters

Dickson Y. B. Annor

REVIEW 4 major objections 4 minor 10 references

A Note on Inequalities for Three Domination Parameters

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

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

Pith's one-line read The paper proves linear upper and lower bounds relating the total domination number to the domination and connected domination numbers, and conjectures a sharp lower bound that is verified in several families and best possible if true.

desk verdict A short, correct set of easy inequalities plus a plausible new conjecture; the conjecture's supporting computations for cycles and grids are sloppy and need fixing. read the letter →

arxiv 2506.03646 v3 pith:HRHEEL7Q submitted 2025-06-04 math.CO

Dickson Y. B. Annor This is my paper · ORCID

classification math.CO MSC 05C69

keywords dominationnumbertotalconnectedgraphinequalitiesconjecturecyclesgridgraphs

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

This note studies three standard domination parameters of a connected graph with no isolated vertices: the domination number $\gamma$, the total domination number $\gamma_t$, and the connected domination number $\gamma_c$. It proves three upper bounds: $\gamma_t\le\gamma+\frac12\gamma_c$ when $\gamma>1$, $\gamma_t\le 5\gamma-\gamma_c-2$, and the sharp bound $\gamma_t\le\lceil 2(\gamma+\gamma_c)/3\rceil$. On the lower side it proves $\gamma_t\ge 2\gamma-\gamma_c$ and the unconditional inequality $\gamma_t\ge\lfloor(3\gamma+\gamma_c)/6\rfloor$. The main open claim, Conjecture 7, is the stronger lower bound $\gamma_t\ge\lfloor(3\gamma+2\gamma_c)/6\rfloor$, which the paper verifies when $\gamma_t=\gamma_c$, when $\gamma_t=\gamma_c-1$, when $\gamma=2$, for all cycles, and for two grid families, and shows to be best possible when true.

What carries the argument

The argument is built from two classical sandwich inequalities quoted in the paper: $\gamma(G)\le\gamma_t(G)\le 2\gamma(G)$ and $\gamma(G)\le\gamma_c(G)\le 3\gamma(G)-2$, together with the observation $\gamma(G)\le\gamma_t(G)\le\gamma_c(G)$ when $\gamma(G)>1$. The bounds are obtained by adding, rescaling, and regrouping these inequalities to isolate $\gamma_t$, producing the coefficients $\tfrac12$, $5$, $tfrac23$, $2$, and the floor combinations in the lower bounds. For the conjecture's supporting cases, exact parameter formulas for cycles and for the grid graphs $P_3\square P_n$ and $P_4\square P_n$ are quoted and combined into floor computations.

What would settle it

Compute the three parameters for every connected isolate-free graph with at most ten vertices and check whether $6\gamma_t(G)<3\gamma(G)+2\gamma_c(G)$ for any of them; one such graph would refute Conjecture 7, and none would strengthen it in that range. A quicker check on a quoted ingredient is to verify $\gamma_c(C_n)=n-2$ directly from the definition for a few small $n$.

Watch

Extended reading notes

Core claim

The central claim is that among connected isolate-free graphs the three parameters obey a coefficient-level sandwich. The paper's strongest proved statement is the upper bound $\gamma_t(G)\le\lceil 2(\gamma(G)+\gamma_c(G))/3\rceil$, which is tight. The paper's central open claim is that the lower inequality $\gamma_t(G)\ge\lfloor(3\gamma(G)+2\gamma_c(G))/6\rfloor$ holds for every such graph; if true it is best possible, with equality on the tree $T$ of Figure 3, where $\gamma=\gamma_t=6$ and $\gamma_c=10$. Supporting evidence proves the conjecture when $\gamma_t=\gamma_c$ or $\gamma_t=\gamma_c-1$, when $\gamma=2$, for cycles $C_n$, and for $P_3\square P_n$ and $P_4\square P_n$; a weaker lower bound with $\gamma_c$ in place of $2\gamma_c$ is proved in full generality.

Load-bearing premise

The partial verification of Conjecture 7 depends on quoted formulas for the domination parameters of cycles and grid graphs (for example $\gamma_c(C_n)=n-2$) that the paper does not re-derive; if any of those formulas is wrong, the supporting evidence in those families loses its foundation.

Editorial extensions

If this is right

The total domination number of any connected isolate-free graph is at most $\lceil 2(\gamma+\gamma_c)/3\rceil$, and this cannot be improved in general.
The unconditional lower bound $\gamma_t\ge\lfloor(3\gamma+\gamma_c)/6\rfloor$ holds for every connected isolate-free graph, giving a universally valid albeit weaker version of the conjecture.
If Conjecture 7 is true, then $\gamma_t$ is constrained between the conjectured floor bound and the sharp ceiling bound, pinning the total domination number to a narrow linear window.
The conjecture is verified for graphs with $\gamma=2$, all cycles, $P_3\square P_n$, and $P_4\square P_n$; the equality example in Figure 3 shows that no stronger bound of the same linear form can hold universally.
The upper bounds in Theorems 3, 4, and 5 are each tight, so the coefficient patterns they exhibit cannot be improved without adding further hypotheses.

Reading between the lines

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

The paper's add-and-rescale proof style suggests a template for inequalities among any triple of domination-type parameters that satisfy the two sandwich inequalities used here; testing this template on other parameter triples would be a direct extension.
A computer search over all connected isolate-free graphs through ten vertices for a violation of $6\gamma_t<3\gamma+2\gamma_c$ would either confirm Conjecture 7 in that range or produce the first concrete counterexample; the paper does not report such a search.
The 3-to-2 weighting of $\gamma$ and $\gamma_c$ in the conjecture hints that the lower bound becomes most restrictive when $\gamma_c$ is large relative to $\gamma$, as in trees with many leaves; random-tree computations could test whether the bound is tight beyond the single example in Figure 3.

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

Quick take: the paper's proved inequalities are correct but easy, and the conjecture is plausibly new and sharp. What it does not supply is a trustworthy verification of that conjecture for cycles and grids. I'd send it to review, but the author needs to fix the algebra or cut those families.

What's actually new: Conjecture 7 is new as far as I know, and it's a nice target—if true it is tight on the tree in Figure 3. Theorems 3–5 and Proposition 6 are immediate algebraic consequences of the Bollobás–Cockayne theorem and Sampathkumar–Walikar, but they are stated cleanly and the tightness examples check out. Theorem 17, the weakened lower bound, is also correctly proved. There is no circularity; everything rests on cited external results, and the citation pattern is normal.

The soft spots are in the evidence for the conjecture. Proposition 12's cycle verification has algebraic errors: in the n≡0 mod 4 case it replaces 3⌈n/3⌉ by n, which is not an equality, and the later case split is tangled; the n=4k+2 line misstates γ_t(C_{4k+2}) as (4k+c+1)/2 instead of (n+2)/2. Proposition 16(b) is worse: the negation step leads to an inequality that, when multiplied out, says n+3 < −10⌊n/3⌋, which is impossible, so the printed 'contradiction' cannot be derived that way. Lemma 9's proof claims γt=γc=3 for a distance-2 pair on a four-vertex path, which is false for C4, though the lemma's conclusion may be salvageable. Theorem 8(b) is advertised but its proof is omitted entirely.

None of this shows the conjecture is false—my own back-of-envelope checks suggest the cycle and grid inequalities still go through—but it means the current manuscript does not provide reliable derivations of the evidence it claims. The external quoted formulas for cycles and grids are likely correct, but the paper doesn't re-derive them, so the verification is doubly fragile.

Who should read this: people working on domination inequalities. It is a narrow but real contribution, and the conjecture is worth stating. I'd accept it for peer review with major revision: fix the computations, fill Theorem 8(b), and either repair Lemma 9 or remove it. The proved bounds alone are not enough for a standalone paper, but with the conjecture properly supported it could be a fine short note.

Referee Report

4 major / 4 minor

Summary. The paper proves several inequalities relating the domination number γ, the total domination number γ_t, and the connected domination number γ_c of a connected isolate-free graph: upper bounds γ_t ≤ γ + γ_c/2 (Theorem 3), γ_t ≤ 5γ − γ_c − 2 (Theorem 4), γ_t ≤ ⌈2(γ+γ_c)/3⌉ (Theorem 5), a lower bound γ_t ≥ 2γ − γ_c (Proposition 6), and a weaker lower bound γ_t ≥ ⌊(3γ+γ_c)/6⌋ (Theorem 17). The central open claim is Conjecture 7, which asserts γ_t ≥ ⌊(3γ+2γ_c)/6⌋, with a sharpness example in Figure 3. As evidence, the paper proves the conjecture when γ_t = γ_c (Theorem 8(a)), claims it when γ_t = γ_c − 1 (Theorem 8(b), proof omitted), proves it for graphs with γ = 2 (Proposition 10), and attempts to verify it for cycles (Proposition 12) and grids (Proposition 16). The main theorems appear correct, but the verification of the conjecture contains several algebraic and logical errors.

Significance. If Conjecture 7 is true, it is a sharp inequality among three standard domination parameters, with equality attained by the tree in Figure 3. The proved inequalities (Theorems 3–5, Proposition 6, Theorem 17) are correct and tight where claimed, making a modest but solid contribution. The conjecture itself remains open, and the manuscript's supporting evidence is currently unreliable because of the errors in Proposition 12 and Proposition 16. The paper's stated aim—establishing relations between γ, γ_t, and γ_c—is only partially achieved, but the correct parts are a reasonable foundation for a revision.

major comments (4)

[Proposition 12] The proof of Conjecture 7 for cycles is not sound. In the n ≡ 0 (mod 4) case, the equality ⌊(3γ(G)+2γ_c(G))/6⌋ = ⌊(n+2(n−2))/6⌋ replaces 3⌈n/3⌉ by n, which is false in general (for n=8, 3⌈8/3⌉=9≠8). The subsequent case split is also inconsistent: after assuming n not≡ 0 (mod 4), the proof then considers 'If 4 divides n'. Finally, for n=4k+2 with c=2, the displayed bound is written as (4k+c+1)/2 = 2k+3/2, which is non-integer and not equal to γ_t(C_{4k+2}) = (n+2)/2 = 2k+2 given by Proposition 11. The intended inequality may still hold, but the proof as written does not establish it.
[Proposition 16(b)] The contradiction in the proof for P4□Pn grids is algebraically false. From the displayed inequality (6n+8)/5 − 1 ≤ ⌊(6n+8)/5⌋ < ⌊(3(n+1)+2(2n−⌊n/3⌋))/6⌋ ≤ (7n+3−2⌊n/3⌋)/6, multiplying by 30 yields n+3 < −10⌊n/3⌋, which is immediately impossible. The text instead claims '(1/30)n < 9/10 − (1/3)⌊n/3⌋ ≤ 7/30', which does not follow from the displayed inequality. As printed, the proof does not derive the asserted contradiction, so the verification for the grid family is unsupported.
[Theorem 8(b)] The abstract states that Conjecture 7 holds when γ_t(G)=γ_c(G)−1, but the proof is omitted with the sentence 'the proof is similar to that of assertion (a), so we omit it.' This is an explicit proof gap for an advertised result. If the argument is genuinely analogous, it should be written out; otherwise the claim is unverified. The omission is load-bearing because Theorem 8 is presented as the main evidence for the conjecture.
[Lemma 9] The proof of Lemma 9 is incorrect for dominating pairs at distance 2. The proof claims that if the shortest path between the two dominating vertices has three vertices, then γ_t(G)=γ_c(G)=3. This is false: in C4, take two opposite vertices as the dominating pair; the shortest path has three vertices, yet γ_t(C4)=γ_c(C4)=2. The 'otherwise' case is also not justified: a vertex outside the pair that is adjacent to only one of them can prevent the claimed total dominating set. Since Proposition 10 relies on Lemma 9, the proof of the γ=2 case is incomplete, although the lemma's statement may be salvageable.

minor comments (4)

[Theorem 5 proof] The expression '⌈ 2×2 / 3 ⌉ = 2' in the γ(G)=1 case is ambiguous; it should be ⌈2(γ(G)+γ_c(G))/3⌉ = ⌈4/3⌉ = 2.
[Proposition 12] The case organization should be revised: the branch 'If 4 divides n' appears after the assumption n not≡ 0 (mod 4), which is logically confusing.
[Proposition 16(b)] The exceptional cases n=4,5,6 are dismissed as 'easy verification' and left to the reader; since these are part of the claimed verification of the conjecture, they should be listed explicitly.
[General] The proofs of Propositions 13–15 are not re-derived; the grid evidence depends entirely on those quoted formulas. Adding a sentence repeating the standard values for γ(P4□Pn), γ_t(P4□Pn), and γ_c(P4□Pn) would make the verification more self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all results derive from externally cited theorems, with no fitted inputs or self-citation chains.

full rationale

This paper derives inequalities relating gamma, gamma_t, and gamma_c by combining three external cited results: Bollobás–Cockayne's bound gamma <= gamma_t <= 2gamma, Sampathkumar–Walikar's bound gamma_c <= 3gamma - 2, and Henning's Fact 1 that gamma_t <= gamma_c when gamma > 1. Theorems 3, 4, 5, and 6 (Proposition 6) are immediate arithmetic consequences of these external theorems. Conjecture 7 is explicitly proposed, not derived, and the supporting evidence for it uses external published formulas for cycle and grid domination parameters (Propositions 11–15). There are no steps in which a claimed prediction is equivalent to an input, no fitted parameters are renamed as predictions, and no load-bearing self-citations: the author cites work by others, not their own prior results. The omitted proof of Theorem 8(b) and algebraic slips in Proposition 12 are correctness issues in the manuscript's verification, not circularity. The derivation chain is self-contained relative to its stated external sources, so no circular step exists.

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

No free parameters are fitted; the derivations rely entirely on previously published domination bounds and simple integer arithmetic. The only 'inputs' are the external theorems for paths, cycles, and grids quoted in Propositions 11, 13, 14, and 15.

assumptions (5)

domain assumption Bollobas-Cockayne: If G is isolate-free, then gamma(G) <= gamma_t(G) <= 2gamma(G).
Quoted as Theorem 1 from [1] and used in Theorems 3, 4, 5, 8, and 17.
domain assumption Sampathkumar-Walikar: If G is connected, then gamma(G) <= gamma_c(G) <= 3gamma(G)-2.
Quoted as Theorem 2 from [10] and used in Theorem 4, Proposition 6, and Theorem 17.
domain assumption Fact 1 from [7]: If G is connected isolate-free and gamma(G)>1, then gamma(G) <= gamma_t(G) <= gamma_c(G).
Used to prove Theorems 3 and 5; specifically for the upper bound gamma_t <= gamma_c.
domain assumption For a graph with gamma(G)=1 (a universal vertex), gamma_t(G)=2.
Asserted in Theorem 5 proof; true but not proved in the note.
domain assumption Quoted formulas for gamma_t(C_n), gamma(P4 square Pn), gamma_t(P4 square Pn), gamma_c(P4 square Pn) from [6], [8], [2], and [9].
Used in Propositions 12 and 16 to verify Conjecture 7 for cycles and grid graphs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Note on Inequalities for Three Domination Parameters." pith.science (2026). https://pith.science/paper/HRHEEL7Q

@misc{pith2026250603646,
  author       = {Pith},
  title        = {Pith review of: A Note on Inequalities for Three Domination Parameters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HRHEEL7Q}},
  note         = {Machine review of arXiv:2506.03646}
}

abstract

In this short paper, we establish relations between the domination number $\gamma$, the total domination number $\gamma_t$, and the connected domination number $\gamma_c$ of a graph. In particular, we prove upper and lower bounds for $\gamma_t$ in terms of $\gamma$ and $\gamma_c$.

Figures

Figures reproduced from arXiv: 2506.03646 by the authors.

**Figure 1.** Graph H. Theorem 3. If G is a connected isolated-free graph and γ(G) > 1, then γt(G) ⩽ γ(G) + 1 2 γc(G). Moreover, this bound is tight. Proof. Let G be a connected isolated-free graph with γ(G) > 1. From Theorem 1 and Fact 1, we have γt(G) ⩽ 2γ(G) and γt(G) ⩽ γc(G), respectively. By adding these two inequalities, we get 2γt(G) ⩽ 2γ(G) + γc(G) and the result follows immediately. In [PITH_FULL_IMAGE:figures/full_fig_… view at source ↗

**Figure 2.** Graph G′ . Remark 1. Equality is achieved for the graph G′ in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** So, Conjecture 7, if true, is best possible [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Graph-theoretic parameters concerning domination, independence, and irredundance.Journal of Graph Theory, 3(3):241– 249, 1979

Béla Bollobás and Ernest J Cockayne. Graph-theoretic parameters concerning domination, independence, and irredundance.Journal of Graph Theory, 3(3):241– 249, 1979

work page 1979
[2]

Total domination number of grid graphs.Discrete Applied Mathematics, 121(1-3):119–128, 2002

Sylvain Gravier. Total domination number of grid graphs.Discrete Applied Mathematics, 121(1-3):119–128, 2002

work page 2002
[3]

CRC press, 2013

Teresa W Haynes, Stephen Hedetniemi, and Peter Slater.Fundamentals of domi- nation in graphs. CRC press, 2013

work page 2013
[4]

Springer, 2020

Teresa W Haynes, Stephen T Hedetniemi, and Michael A Henning.Topics in domination in graphs, volume 64. Springer, 2020

work page 2020
[5]

Springer, 2023

Teresa W Haynes, Stephen T Hedetniemi, and Michael A Henning.Domination in graphs: Core concepts. Springer, 2023

work page 2023
[6]

Graphs with large total domination number.Journal of Graph Theory, 35(1):21–45, 2000

Michael A Henning. Graphs with large total domination number.Journal of Graph Theory, 35(1):21–45, 2000

work page 2000
[7]

Bounds on domination parameters in graphs: a brief survey

Michael A Henning. Bounds on domination parameters in graphs: a brief survey. Discussiones Mathematicae Graph Theory, 42(3):665–708, 2022

work page 2022
[8]

On the domination of the products of graphs ii: trees.Journal of graph theory, 10(1):97–106, 1986

Michael S Jacobson and Lael F Kinch. On the domination of the products of graphs ii: trees.Journal of graph theory, 10(1):97–106, 1986. 7

work page 1986

Show all 10 references

[9]

Maximum leaf spanning tree problem for grid graphs

PC Li and Michel Toulouse. Maximum leaf spanning tree problem for grid graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 73:181, 2010

2010
[10]

The connected domination number of a graph

E Sampathkumar and HB Walikar. The connected domination number of a graph. J. Math. Phys, 13(6), 1979. 8

1979

Pith tools

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

[1] [1]

Graph-theoretic parameters concerning domination, independence, and irredundance.Journal of Graph Theory, 3(3):241– 249, 1979

Béla Bollobás and Ernest J Cockayne. Graph-theoretic parameters concerning domination, independence, and irredundance.Journal of Graph Theory, 3(3):241– 249, 1979

work page 1979

[2] [2]

Total domination number of grid graphs.Discrete Applied Mathematics, 121(1-3):119–128, 2002

Sylvain Gravier. Total domination number of grid graphs.Discrete Applied Mathematics, 121(1-3):119–128, 2002

work page 2002

[3] [3]

CRC press, 2013

Teresa W Haynes, Stephen Hedetniemi, and Peter Slater.Fundamentals of domi- nation in graphs. CRC press, 2013

work page 2013

[4] [4]

Springer, 2020

Teresa W Haynes, Stephen T Hedetniemi, and Michael A Henning.Topics in domination in graphs, volume 64. Springer, 2020

work page 2020

[5] [5]

Springer, 2023

Teresa W Haynes, Stephen T Hedetniemi, and Michael A Henning.Domination in graphs: Core concepts. Springer, 2023

work page 2023

[6] [6]

Graphs with large total domination number.Journal of Graph Theory, 35(1):21–45, 2000

Michael A Henning. Graphs with large total domination number.Journal of Graph Theory, 35(1):21–45, 2000

work page 2000

[7] [7]

Bounds on domination parameters in graphs: a brief survey

Michael A Henning. Bounds on domination parameters in graphs: a brief survey. Discussiones Mathematicae Graph Theory, 42(3):665–708, 2022

work page 2022

[8] [8]

On the domination of the products of graphs ii: trees.Journal of graph theory, 10(1):97–106, 1986

Michael S Jacobson and Lael F Kinch. On the domination of the products of graphs ii: trees.Journal of graph theory, 10(1):97–106, 1986. 7

work page 1986