An improved constant for Vizing's conjecture
Pith reviewed 2026-07-03 20:19 UTC · model grok-4.3
The pith
The Cartesian product of any two graphs has domination number at least 0.5809 times the product of the factors.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For any graphs G and H, γ(G□H) ≥ .5809 γ(G)γ(H), proved by applying well-known results from graph domination theory.
What carries the argument
The numerical factor 0.5809 obtained by combining standard domination bounds on products and related graph parameters.
If this is right
- The inequality holds unconditionally for all finite undirected graphs.
- It supplies a uniform numerical improvement over any earlier constant strictly less than 0.5809.
- The bound applies directly to grids, hypercubes, and other Cartesian products that arise in applications.
- Any future strengthening of the constant must still respect this 0.5809 floor.
Where Pith is reading between the lines
- The same combination technique might be reusable on other graph products such as the strong or lexicographic product.
- If the constant can be pushed higher by incorporating more recent domination theorems, the gap to Vizing's conjecture would shrink.
- The result suggests that the worst-case ratio may be achieved by graphs with particular domination structures that can be enumerated for small orders.
Load-bearing premise
The known domination results can be assembled into a single inequality that yields precisely the constant 0.5809 for every pair of graphs.
What would settle it
Two explicit graphs G and H where the domination number of G□H falls below 0.5809 times γ(G) times γ(H).
read the original abstract
For any graph $G = (V,E)$, a subset $S {\subseteq} V$ dominates $G$ if $N[S] = V$. The minimum cardinality over all such $S$ is called the domination number, written ${\gamma}(G)$. The classical conjecture of V.G. Vizing states that ${\gamma}(G{\square} H) {\ge} {\gamma}(G){\gamma}(H)$ where ${\square}$ stands for the Cartesian product of graphs. In this paper, we apply well-known results to prove the Vizing-type inequality ${\gamma}(G{\square} H) {\ge} .5809 {\gamma}(G){\gamma}(H)$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to prove the inequality γ(G□H) ≥ 0.5809 γ(G)γ(H) for the domination numbers of the Cartesian product of arbitrary graphs G and H, by applying well-known results from graph domination theory and thereby improving the constant factor toward Vizing's conjecture γ(G□H) ≥ γ(G)γ(H).
Significance. If the claimed combination of standard results indeed yields a valid constant of 0.5809 without additional restrictions, the result would supply a modest numerical improvement on existing lower bounds for Vizing's conjecture, a long-standing problem in graph theory.
major comments (1)
- [Abstract] Abstract: the manuscript consists solely of the abstract, which asserts that well-known results combine to produce exactly the factor 0.5809 but supplies neither the list of theorems invoked, the derivation steps, nor any verification that the numerical constant is obtained without hidden conditions or rounding artifacts.
Simulated Author's Rebuttal
We thank the referee for their review and comments on the manuscript. We address the major comment below.
read point-by-point responses
-
Referee: [Abstract] Abstract: the manuscript consists solely of the abstract, which asserts that well-known results combine to produce exactly the factor 0.5809 but supplies neither the list of theorems invoked, the derivation steps, nor any verification that the numerical constant is obtained without hidden conditions or rounding artifacts.
Authors: We agree that the manuscript consists only of the abstract and does not list the specific theorems, provide derivation steps, or verify the constant. The abstract states that the inequality follows from applying well-known results in domination theory, but no further details are supplied in the available text. revision: no
- The list of theorems invoked, the derivation steps, and verification of the numerical constant 0.5809, since these are not present in the manuscript.
Circularity Check
No significant circularity
full rationale
The paper's abstract states that it applies well-known results from graph domination theory to establish the inequality γ(G□H) ≥ .5809 γ(G)γ(H). No self-definitional steps, fitted inputs presented as predictions, self-citation load-bearing arguments, uniqueness theorems imported from the authors' prior work, ansatzes smuggled via citation, or renamings of known results are present or indicated. The central claim rests on external, independent results rather than reducing to the paper's own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Well-known results from graph domination theory apply directly to the Cartesian product setting
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.