gpt 6 astra ultra attempt on Math-623

Vizing’s Cartesian-Product Domination Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A dominating set meets the closed neighbourhood of every vertex, and $\gamma(G)$ is its minimum size. In $G\square H$, vertices are pairs $(g,h)$, with adjacency when one coordinate agrees and the other is an edge of the corresponding factor. The conjecture is $\gamma(G\square H)\geq\gamma(G)\gamma(H)$ for finite graphs. [S1] [S2]

Statement recorded in the supplied source.

For the Cartesian product of graphs $G \square H$, is the domination number at least $\gamma(G) \cdot \gamma(H)$? [S1]

Short English statement

Must dominating a Cartesian product require at least the product of the minimum dominating-set sizes of its two factors?

Research attempt

Target and selected packing route.

The domination number uses closed neighbourhoods and the product is Cartesian. The recent primary records [E1,E2] discuss constant-factor progress; their titles and bounds do not give the full coefficient one for all graphs. This attempt proves a packing bound that implies the conjecture for a substantial subclass, then isolates the overlap that prevents the same count from handling arbitrary factors.

Projection supplies only the individual lower bounds.

Let $D$ dominate $G\square H$. Its first-coordinate projection dominates $G$: otherwise there is a vertex $g$ with no projected coordinate in $N_G[g]$, and no $(g,h)$ could be dominated in the product. Thus $|D|\ge\gamma(G)$, and symmetrically \[ \gamma(G\square H)\ge\max\{\gamma(G),\gamma(H)\}. \] The two projections come from the same elements of $D$. Multiplying their separate lower bounds is invalid; a set of ordered pairs may have large projections without containing their Cartesian product. This identifies why the simplest projection argument stops short.

Disjoint closed neighbourhoods give a stronger theorem.

Let $g_1,\ldots,g_r$ have pairwise disjoint closed neighbourhoods in $G$. Such a set is often called a distance-two packing, because its distinct centres have distance at least three whenever connected. For each $i$ define \[ D_i=D\cap(N_G[g_i]\times V(H)). \] The second-coordinate projection of $D_i$ dominates $H$. Indeed, to dominate $(g_i,h)$ a member of $D$ must either have first coordinate $g_i$ and second coordinate in $N_H[h]$, or have first coordinate adjacent to $g_i$ and second coordinate exactly $h$. In either case it belongs to $D_i$ and its second coordinate lies in $N_H[h]$. Hence $|D_i|\ge\gamma(H)$.

The neighbourhoods are disjoint, so the $D_i$ are disjoint subsets of $D$. Summing gives \[ |D|\ge r\gamma(H). \] If $\rho(G)$ denotes the largest size of such a packing, we obtain \[ \gamma(G\square H)\ge\rho(G)\gamma(H), \qquad \gamma(G\square H)\ge\gamma(G)\rho(H). \] Also $\rho(G)\le\gamma(G)$: a dominating set must meet every $N_G[g_i]$, and those sets are disjoint. Thus the bound proves the desired conjecture whenever one factor satisfies $\rho=\gamma$.

Efficient domination gives a complete subclass.

Suppose some centres $g_1,\ldots,g_r$ have closed neighbourhoods partitioning $V(G)$. They form a dominating set, so $\gamma(G)\le r$; they also form a packing, so $\gamma(G)\ge\rho(G)\ge r$. Consequently $\rho(G)=\gamma(G)=r$, and the preceding theorem establishes Vizing's inequality for this $G$ and every finite graph $H$. This argument requires no additional properties of $H$.

For the path $P_n$ with vertices $1,\ldots,n$, explicit such centres are as follows. If $n=3k$, use $2,5,\ldots,3k-1$. If $n=3k+1$, use $1,4,\ldots,3k+1$. If $n=3k+2$, use $2,5,\ldots,3k+2$. The end neighbourhoods are truncated at the endpoints and the interior ones are consecutive three-vertex intervals. They are disjoint and cover the path in each case, including $n=1,2$. Therefore \[ \gamma(P_n)=\lceil n/3\rceil, \qquad \gamma(P_n\square H)\ge\lceil n/3\rceil\gamma(H). \] Likewise in $C_{3k}$, $k\ge1$, centres $1,4,\ldots,3k-2$ have disjoint three-vertex closed neighbourhoods covering the cycle. Thus $\gamma(C_{3k})=k$ and the product conjecture holds with such a cycle as one factor. For a disjoint union of efficiently dominated components, taking all their centres preserves the same property.

A precise obstruction to the unrestricted counting argument.

For $C_4$, the domination number is two: no closed neighbourhood has all four vertices, while two opposite vertices dominate. However any two vertices of $C_4$ are at distance at most two, so $\rho(C_4)=1$. Thus the packing bound gives only $\gamma(H)$ when the desired bound is $2\gamma(H)$. The gap is already present in a four-vertex factor.

Starting with a minimum dominating set rather than a packing does not fix the sum. Its closed neighbourhoods may overlap, causing a single element of $D$ to be counted in several sets $D_i$. Dividing by a maximum overlap multiplicity gives a weaker bound, and no argument here makes that multiplicity one. To reach the conjecture for general factors one needs a more careful allocation or charging scheme that preserves a full $\gamma(H)$ contribution per dominating centre. The elementary packing proof supplies no such allocation.

Executed finite tests.

The script enumerates vertex subsets in increasing cardinality until a dominating set is found, using exact closed-neighbourhood bit masks. Testing every smaller subset certifies minimality for each graph. For $P_2\square P_3$, $P_4\square P_4$, and $C_4\square C_4$ it finds domination numbers $2,4,4$, respectively. The corresponding products of the factor domination numbers are $1,4,4$. Thus the inequality can be strict and can also attain equality; the $C_4$ example succeeds despite the weakness of the packing bound. Witness sets are saved with the vertex encoding used by the script.

These computations are in checks_graphs.py and results_graphs.json under _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. They are checks of three finite products, not an enumeration of all finite graphs or a replication of the recent constant-factor papers.

Remaining gap and outcome.

The packing theorem proves the full inequality whenever one factor has equal packing and domination numbers, including all paths and cycles of order divisible by three. Overlapping neighbourhoods in a general minimum dominating set prevent the same proof from extending. No general allocation theorem or counterexample is obtained. Outcome: UNRESOLVED.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1428 (GRAPH-041), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Stephen Suen and Jennifer Tarr, An improved inequality related to Vizing's conjecture, Electronic Journal of Combinatorics 19 $2012$, #P8. https://doi.org/10.37236/15. Bibliographic information from the supplied record.

• S3 Raphael Steiner, A constant-factor step towards Vizing's conjecture, arXiv:2606.14414 $2026$. https://arxiv.org/abs/2606.14414. Bibliographic information from the supplied record.

• S4 Mohsen Aliabadi and Elliot Krop, An improved constant for Vizing's conjecture, arXiv:2607.01109 $2026$. https://arxiv.org/abs/2607.01109. Bibliographic information from the supplied record.

• E1 Raphael Steiner, A constant-factor step towards Vizing's conjecture, arXiv:2606.14414. https://arxiv.org/abs/2606.14414. Primary record inspected 1 October 2026; background only, not a premise of the packing proof.
• E2 Mohsen Aliabadi and Elliot Krop, A $2/3$ Bound for Vizing's Conjecture, arXiv:2607.01109. https://arxiv.org/abs/2607.01109. Primary title and record inspected 1 October 2026. This current title differs from the imported bibliographic wording in [S4]; a coefficient below one is not the full inequality recorded in this problem.