Domination in direct products of complete graphs

Harish Vemuri

REVIEW 2 major objections 4 minor 22 references

Domination in direct products of complete graphs

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

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

Pith's one-line read The paper proves that for infinitely many $n$ with arbitrarily many prime factors, the total domination number of the unitary Cayley graph $X_n$ is at least 16 less than Jacobsthal's function $g(n)$.

desk verdict The classification and the single-n gap-16 example are real; the asymptotic claims and the amplification theorem are not currently proven. read the letter →

arxiv 1908.02445 v1 pith:TVQ5VSK4 submitted 2019-08-07 math.CO

Harish Vemuri This is my paper · ORCID

classification math.CO MSC 05C6905C76

keywords dominationnumbertotaldirectproductofcompletegraphsunitaryCayleygraphJacobsthal'sfunctionprimefactorsasymptoticboundsclassification

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 total domination number $\gamma_t(X_n)$ of the unitary Cayley graph of $\mathbb{Z}/n\mathbb{Z}$ and compares it with Jacobsthal's function $g(n)$, the smallest $m$ such that every block of $m$ consecutive integers contains a number coprime to $n$. It establishes that the gap between the two can be as large as 16: there exist integers $n$ with arbitrarily many prime factors for which $\gamma_t(X_n) \le g(n)-16$, answering the question of [4] affirmatively. The proof rests on a monotonicity comparison that turns the domination problem into a comparison of two values of Jacobsthal's function, plus an amplification step that makes the number of prime factors arbitrarily large. The paper also proves new lower bounds on domination numbers of direct products of complete graphs and completely classifies the graphs $G=\prod_{i=1}^t K_{n_i}$ with $\gamma(G)=t+2$.

What carries the argument

The central machinery is the comparison lemma (Lemma 4.3): if $n_i \le m_i$ for every $i$, then $\gamma_t(\prod K_{n_i}) \ge \gamma_t(\prod K_{m_i})$. This lets the paper replace the graph parameter by arithmetic data, because $X_n$ is, by the Chinese remainder theorem, a direct product of complete graphs indexed by the prime-power factors of $n$. A second load-bearing device is the amplification theorem (Theorem 1.9), which takes any $s$ witnessing a gap of size $j$ and constructs a new squarefree $n = s \prod r_i$, with the $r_i$ chosen larger than $ks+g(s)$, whose total dominating set has size at most $ks + \gamma_t(X_s)$ while $g(n) \ge ks + g(s)$; this preserves the gap and adds arbitrarily many prime factors. The numerical input is the pair $H(41)=566$, $h(41)=550$, where $H(k)$ is the maximum of $g$ over integers with $k$ distinct prime factors and $h(k)$ is $g$ evaluated on the product of the first $k$ primes.

What would settle it

Independently recompute $H(41)$ and $h(41)$: find whether some squarefree $k$ with 41 distinct prime factors satisfies $g(k)>566$, or whether $g(p_1\cdots p_{41})\ne 550$; either mismatch would remove the input to Lemma 4.4 and invalidate the proof of Theorem 1.10 as presented.

Watch

Extended reading notes

Core claim

The central discovery is that the inequality $\gamma_t(X_n) \le g(n)$ is not just sometimes strict but can be strict by 16, and that strictness is an amplification phenomenon: a single witness $s$ with $\gamma_t(X_s) \le g(s)-j$ generates witnesses $n$ with arbitrarily many prime factors and the same gap. The reduction is provided by the isomorphism $X_n \cong \prod K_{q_i^{\alpha_i}}$ and by the monotonicity lemma that coordinatewise larger complete graphs have no larger total domination number. Feeding in the computed values $H(41)=566$ and $h(41)=550$ gives a concrete squarefree $Q$ with $\gamma_t(X_Q) \le g(Q)-16$; the amplification theorem then spreads this gap to arbitrarily many prime factors. Separately, the paper resolves the classification question for $\gamma(G)=t+2$ by showing it occurs exactly in three listed configurations.

Load-bearing premise

The 16-gap construction rests entirely on the external computation, attributed to [22], that the largest value of Jacobsthal's function among integers with 41 distinct prime factors is 566 while its value on the product of the first 41 primes is 550; if that computation is wrong, the seed integer $Q$ need not exist.

Editorial extensions

If this is right

For any gap value $j$ for which a single witness exists, the family of $n$ with $\gamma_t(X_n) \le g(n)-j$ contains integers with arbitrarily many prime factors; in particular this is now known for $j=16$.
For squarefree $n=q_1\cdots q_t$, the domination number satisfies $\gamma(X_n) \ge (1-\epsilon)t \prod_{i=1}^t \frac{q_i}{q_i-1}$ asymptotically, improving the earlier lower bound of [5].
For primorial $n=p_1\cdots p_t$, the estimates become $C_1 t\log t \le \gamma(X_n) \le C_2 t\log^2 t$ for absolute constants $C_1,C_2>0$.
The paper completely determines when $\gamma(\prod_{i=1}^t K_{n_i}) = t+2$, settling the classification problem raised in [5].

Reading between the lines

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

If $H(k)-h(k)$ is unbounded as $k$ grows, then the paper's Conjecture 1.11 follows immediately; thus the computational study of Jacobsthal's function is the natural test bed for the full conjecture.
The monotonicity lemma suggests a broader principle: for squarefree $n$, the total domination number of $X_n$ is controlled by the minimal Jacobsthal value among integers with the same number of prime factors, so any improvement in the comparison between $H$ and $h$ translates directly into stronger domination gaps.
The explicit dominating-set constructions in the classification theorem are concrete enough to be checked by computer search on small $t$ and $n_i$; an exception would indicate an error in the proof, while agreement would provide independent verification of that theorem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

The paper has one solid half and two broken halves. The classification of γ(G)=t+2 (Theorem 1.5) looks correct, and the proof of Theorem 3.4 is a genuine piece of casework. Lemma 4.4 also works: combining Ziller's computation with the monotonicity lemma gives a single n with γ_t(X_n) ≤ g(n) − 16, which answers Burcroff's question.

But the other main results have load-bearing gaps. In Theorem 1.4, the map f is defined from permutations into F_{v1}(1), but x_σ is never shown to be in D. It is just a vertex whose first coordinate is v1. The pigeonhole argument that needs |F_{v1}(1)| is therefore invalid, and the asymptotic lower bounds in Corollaries 2.2 and 2.4 fall with it.

The stress-test note is right about Theorem 1.9. The CRT condition h ≡ −z_i (mod r_i) makes h+j ≡ −x (mod r_i) when j = z_i − x, not 0. Since r_i > x, the constructed interval can contain integers coprime to n. The fix would be h ≡ x − z_i (mod r_i), but as written the amplification step is unproved. Theorem 1.10's claim of arbitrarily many prime factors therefore does not follow. This is not a minor typo; it is the core of the construction.

Two smaller points: Theorem 1.9's proof says "n is in M16" where it should say M_j, and the paper leans on Ziller's computational values without independent verification. That reliance is acceptable if stated clearly, but it does make the single-n example conditional on an external computation.

Net assessment: the t+2 classification is a solid contribution and alone justifies referee attention. The single-n gap-16 example is also worth reporting. But the marquee result—arbitrarily many prime factors with gap 16—is not established, and the new lower bounds are not established. The flaws are likely repairable, but they are real. I would send this to peer review and tell the referee to focus on the two broken proofs. If those cannot be fixed, the paper should be cut down to the classification plus the single-n observation.

Referee Report

2 major / 4 minor

Summary. The paper studies domination and total domination numbers of direct products of complete graphs, with applications to unitary Cayley graphs X_n of Z/nZ. Its main results are: (i) a lower bound for γ(∏_{i=1}^t K_{n_i}) in Theorem 1.4, leading to asymptotic lower bounds for γ(X_n) for squarefree n; (ii) a complete classification of products with γ(G)=t+2 in Theorem 1.5, answering a question of Defant and Iyer; and (iii) an amplification theorem, Theorem 1.9, stating that a single example with γ_t(X_s)≤g(s)−j yields examples with arbitrarily many prime factors satisfying the same gap, which combined with Ziller's computation H(41)=566, h(41)=550 gives n with γ_t(X_n)≤g(n)−16 in Theorem 1.10. The classification proof appears self-contained and convincing. The lower-bound proof and the amplification proof each contain a load-bearing gap, as detailed below.

Significance. If the proofs are repaired, the paper would make substantial progress: Theorem 1.5 would completely resolve the Defant–Iyer classification question, and Theorem 1.10 would answer Burcroff's question affirmatively with a much larger gap than the previously known value of 2. The monotonicity lemma and the reduction of the problem to Jacobsthal-function computations are elegant, and the paper is careful to identify the external computational input from Ziller rather than hiding it. The claimed asymptotic lower bounds for γ(X_n) would also be a genuine strengthening over the results of Mekiš and of Defant and Iyer. However, as written, the two central proof gaps mean that the main new claims are not yet established.

major comments (2)

[Section 4, proof of Theorem 1.9] The CRT step that is supposed to produce a run of length ks+g(s)−1 with no integer coprime to n has the wrong congruence. The author sets h ≡ −z_i (mod r_i) for each z_i ∈ R. For j = z_i − x, the integer h+j satisfies h+j ≡ −x (mod r_i), which is nonzero because r_i > ks+g(s) ≥ s ≥ x; it is also coprime to s because h+j ≡ z_i (mod s). The proof gives no reason why h+j is divisible by any other r_l, and in general it is not. Thus the claimed lower bound g(n) ≥ ks+g(s) is unsupported. Replacing the congruence by h ≡ x−z_i (mod r_i) would make h+j divisible by r_i for every later-block element, so this appears to be a local fix; as written, however, Theorem 1.9 and consequently the 'arbitrarily many prime factors' conclusion of Theorem 1.10 are not established.
[Section 2, proof of Theorem 1.4] The map f : S_{t−1}(k) → F_{v1}(1) is not well-defined. The vertex x_σ is formed by mixing coordinates of the selected vertices d_1,...,d_{t−1}, and while its first coordinate is v_1, nothing in the construction places x_σ in the dominating set D. Since F_{v1}(1) is defined as the set of vertices of D with first coordinate v_1, the cardinality bound |S_{t−1}(k)|/|F_{v1}(1)| > 4 does not imply the existence of four distinct σ with x_σ equal. This invalidates the subsequent use of Lemma 2.1 on the sets {d_{σ_j(q)}} and hence the lower bound in Theorem 1.4, together with Corollaries 2.2 and 2.4.

minor comments (4)

[Section 4, proof of Theorem 1.9] Near the end of the proof, 'we claim that n = s · ∏ r_i is in M16' should read 'is in M_j', since the argument is for a general j and the set M_16 is only one instance.
[Section 3, proof of Theorem 3.4] The line 'there must be two distinct vertices x5, x6 ∈ K_t such that |F_{x5}(3)| = |F_{x5}(3)| = 2' should have |F_{x6}(3)| = 2 on the right-hand side.
[Section 2, Theorem 1.4] The notation 'log2e(t)' in the statement and proof of Theorem 1.4 is ambiguous and should be defined explicitly.
[Section 2, proof of Theorem 1.4] In the application of Lemma 2.1, the sets E_j are initially formed by subtracting previous F's so that they are disjoint, but the notation subsequently refers to E_j = F_{v_j}(j); the presentation should make the disjoint versions explicit throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: every load-bearing input is either an external theorem, an external computational value, or a new proof whose hypotheses do not contain its conclusion.

full rationale

The paper's derivation chain does not reduce to its inputs by construction. Theorem 1.4 is a new lower-bound argument built on Defant and Iyer's Lemma 2.1 plus a counting/pigeonhole analysis; it does not assume the bound it proves. Theorem 1.5 is a classification whose proof combines external results from Defant and Iyer with a genuinely new case analysis for the remaining case n1 = n2 = n3 = t; the graph case is settled by an explicit dominating-set construction and a contradiction argument, not by importing the classification. Lemma 4.4 uses Ziller's computational values H(41) = 566 and h(41) = 550 as external, testable inputs, then applies the monotonicity Lemma 4.3 and the known inequality gamma_t(X_n) <= g(n); the resulting gap of 16 is not obtained by fitting any parameter to gamma_t or g. Theorem 1.9 is an amplification statement: it assumes the existence of one seed s with gamma_t(X_s) <= g(s) - j and constructs n with additional prime factors and the same gap using elementary CRT and union-bound counting. No quantity in the proof is defined in terms of the target inequality, and no fitted value is renamed as a prediction. The citations to prior work are to Defant and Iyer, Burcroff, Hajdu and Saradha, and Ziller, and none of these is invoked as a substitute for the paper's own central argument; in particular, no author self-citation carries the load. Even if the CRT congruence in the proof of Theorem 1.9 is incorrect, as a skeptical reviewer might argue, that is a correctness risk rather than circularity, because the conclusion is not logically identical to the hypotheses. The paper is therefore self-contained with respect to the circularity criteria, and the appropriate score is 0.

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

The paper's main new results (Theorems 1.5, 1.9, 1.10) are proved from cited theorems and a computational result. No free parameters are fit. The only non-self-contained input is Ziller's computation of H(41) and h(41), which is essential to Theorem 1.10.

assumptions (6)

standard math Theorem 1.1 (Mekis) lower bounds on domination numbers of direct products of complete graphs.
Used in Section 1 to set baseline lower bounds and in Section 3 for the t+2 classification.
standard math Theorem 1.2 and Lemma 2.1 (Defant and Iyer) lower bounds and structural lemma for direct products.
Lemma 2.1 is the engine for the proof of Theorem 1.4; Theorem 1.2 is used for the lower bound in Theorem 3.4.
standard math Lemma 3.3 (Defant and Iyer) restricts fibers of size 2 in dominating sets of size t+2.
Essential in the converse direction of Theorem 3.4.
standard math Proposition 4.5 (Defant and Iyer) gives γ_t(X_n) ≥ γ_t(X_m) when m is the radical of n.
Used in Corollary 4.6 to restrict to squarefree integers in the proof of Theorem 1.9.
domain assumption Ziller's computational result: H(41)=566 and h(41)=550 (Theorem 4.2).
The seed for M16 in Lemma 4.4 directly uses these values; if they are wrong, Theorem 1.10 has no starting point.
standard math Maheswari and Manjuri's fact that the interval {0,...,g(n)-1} is a total dominating set of X_n.
Gives the upper bound γ_t(X_n) ≤ g(n) used throughout Section 4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Domination in direct products of complete graphs." pith.science (2026). https://pith.science/paper/TVQ5VSK4

@misc{pith2026190802445,
  author       = {Pith},
  title        = {Pith review of: Domination in direct products of complete graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TVQ5VSK4}},
  note         = {Machine review of arXiv:1908.02445}
}

abstract

Let $X_{n}$ denote the unitary Cayley graph of $\mathbb{Z}/n\mathbb{Z}$. We continue the study of cases in which the inequality $\gamma_t(X_n) \le g(n)$ is strict, where $\gamma_t$ denotes the total domination number, and $g$ is the arithmetic function known as Jacobsthal's function. The best that is currently known in this direction is a construction of Burcroff which gives a family of $n$ with arbitrarily many prime factors that satisfy $\gamma_t(X_n) \le g(n)-2$. We present a new interpretation of the problem which allows us to use recent results on the computation of Jacobsthal's function to construct $n$ with arbitrarily many prime factors that satisfy $\gamma_t(X_n) \le g(n)-16$. We also present new lower bounds on the domination numbers of direct products of complete graphs, which in turn allow us to derive new asymptotic lower bounds on $\gamma(X_n)$, where $\gamma$ denotes the domination number. Finally, resolving a question of Defant and Iyer, we completely classify all graphs $G = \prod_{i=1}^t K_{n_i}$ satisfying $\gamma(G) = t+2$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

Akhtar, M

R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jimenez , R. Karpman, A. Kinzel, and D. Pritkin, On the unitary Cayley graph of a ﬁnite ring . Electronic Journal of Combinatorics 16 (2009), #R117

work page 2009
[2]

Alon and J

N. Alon and J. Spencer, The Probabilistic Method, John Wiley & Sons, 2004

work page 2004
[3]

Bresar, S

B. Bresar, S. Klav ˘zar, and D. Rall, Dominating direct products of graphs . Discrete Mathematics 307 (2007), 1636-1642

work page 2007
[4]

Domination Parameters of the Unitary Cayley Graph of $\mathbb{Z}/n\mathbb{Z}$

A. Burcroff, Domination parameters of the unitary Cayley graph of Z/n Z. preprint arXiv:1809.04769 (2018)

work page Pith review arXiv 2018
[5]

Defant and S

C. Defant and S. Iyer, Domination and upper domination of direct product graphs , Discrete Mathe- matics 341 (2018), 2742-2752

work page 2018
[6]

Erd ˝os, On the integers relatively prime to n and a number-theoretic function considered by Jacob- sthal, Math

P . Erd ˝os, On the integers relatively prime to n and a number-theoretic function considered by Jacob- sthal, Math. Scand. 10 (1962), 163-170. DOMINA TION IN DIRECT PRODUCTS OF COMPLETE GRAPHS 15

work page 1962
[7]

Fuchs, Longest induced cycles in circulant graphs, Electronic Journal of Combinatorics 12 (2005), #R52

E. Fuchs, Longest induced cycles in circulant graphs, Electronic Journal of Combinatorics 12 (2005), #R52

work page 2005
[8]

J. A. Gallian, A dynamic survey of graph labeling , Electronic Journal of Combinatorics 16 (2018), #DS6

work page 2018

Show all 22 references

[9]

Georges, J

J. Georges, J. Lin, and D. Mauro, The domination number of K 3 n, Discussiones Mathematicae Graph Theory 34 (2014), 629-632

2014
[10]

Gorodezky, Dominating sets in Kneser graphs, MA thesis

I. Gorodezky, Dominating sets in Kneser graphs, MA thesis. Waterloo, Ontario, Canada, University of Waterloo, 2007

2007
[11]

Gravier and M

S. Gravier and M. Mollard, On domination numbers of Cartesian product of paths, Discrete Applied Mathematics 80 (1997), 247-250

1997
[12]

Hajdu and N

L. Hajdu and N. Saradha, Disproof of a conjecture of Jacobsthal , Mathematics of Computation 81 (2012), no. 280, 2461-2471

2012
[13]

S. T. Hedetniemi and R. C. Laskar, Bibliography on domination in graphs and some basic deﬁniti ons of domination parameters, Discrete Mathematics 86 (1990), 257-277

1990
[14]

Iwaniec, On the problem of Jacobsthal , Demonstratio Mathematica 11 (1978), 225-231

H. Iwaniec, On the problem of Jacobsthal , Demonstratio Mathematica 11 (1978), 225-231

1978
[15]

Iwaniec, E

H. Iwaniec, E. Kowalski, Analytic number theory , AMS Colloquium Publ., V ol. 53
[16]

Klav ˘zar and N

S. Klav ˘zar and N. Seifter, Dominating Cartesian products of cycles . Discrete Applied Mathematics 59 (1995), 129-136

1995
[17]

Klotz and T

W . Klotz and T. Sander, Some properties of unitary Cayley graphs , Electronic Journal of Combina- torics 14 (2007), #R45

2007
[18]

Maheswari and M

B. Maheswari and M. Manjuri, Strong dominating sets of some arithmetic graphs , Int. J. Computer Applications 83 (2013), 36-40

2013
[19]

Maier and C

H. Maier and C. Pomerance, Unusually large gaps between consecutive primes, Trans. Amer. Math. Soc. 322 (1990), 201-237

1990
[20]

Meki ˘s, Lower bounds for the domination number and total domination number of direct product graphs, Discrete Mathematics 310 (2010), 3310-3317

G. Meki ˘s, Lower bounds for the domination number and total domination number of direct product graphs, Discrete Mathematics 310 (2010), 3310-3317

2010
[21]

Pintz, V ery large gaps between consecutive primes, J

J. Pintz, V ery large gaps between consecutive primes, J. Number Theory 63 (1997), 286-301

1997
[22]

Ziller, New computational results on a conjecture of Jacobsthal

M. Ziller, New computational results on a conjecture of Jacobsthal . preprint arXiv:1903.11973 (2019) DEPARTMENT OF MATHEMATICS , YALE UNIVERSITY , N EW HAVEN, CT 06520 E-mail address: harish.vemuri@yale.edu

2019 arXiv

Pith tools

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

[1] [1]

Akhtar, M

R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jimenez , R. Karpman, A. Kinzel, and D. Pritkin, On the unitary Cayley graph of a ﬁnite ring . Electronic Journal of Combinatorics 16 (2009), #R117

work page 2009

[2] [2]

Alon and J

N. Alon and J. Spencer, The Probabilistic Method, John Wiley & Sons, 2004

work page 2004

[3] [3]

Bresar, S

B. Bresar, S. Klav ˘zar, and D. Rall, Dominating direct products of graphs . Discrete Mathematics 307 (2007), 1636-1642

work page 2007

[4] [4]

Domination Parameters of the Unitary Cayley Graph of $\mathbb{Z}/n\mathbb{Z}$

A. Burcroff, Domination parameters of the unitary Cayley graph of Z/n Z. preprint arXiv:1809.04769 (2018)

work page Pith review arXiv 2018

[5] [5]

Defant and S

C. Defant and S. Iyer, Domination and upper domination of direct product graphs , Discrete Mathe- matics 341 (2018), 2742-2752

work page 2018

[6] [6]

Erd ˝os, On the integers relatively prime to n and a number-theoretic function considered by Jacob- sthal, Math

P . Erd ˝os, On the integers relatively prime to n and a number-theoretic function considered by Jacob- sthal, Math. Scand. 10 (1962), 163-170. DOMINA TION IN DIRECT PRODUCTS OF COMPLETE GRAPHS 15

work page 1962

[7] [7]

Fuchs, Longest induced cycles in circulant graphs, Electronic Journal of Combinatorics 12 (2005), #R52

E. Fuchs, Longest induced cycles in circulant graphs, Electronic Journal of Combinatorics 12 (2005), #R52

work page 2005

[8] [8]

J. A. Gallian, A dynamic survey of graph labeling , Electronic Journal of Combinatorics 16 (2018), #DS6

work page 2018