Domination in cubic graphs

Domination in cubic graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph and write $n=|V|$. For a vertex $v$, its closed neighbourhood is $N[v]=\{v\}\cup\{u:uv\in E\}$. A set $D\subseteq V$ is dominating if every vertex belongs to the closed neighbourhood of some vertex of $D$, or equivalently \[ \bigcup_{v\in D}N[v]=V. \] The domination number $\gamma(G)$ is the minimum size of such a set. Vertices in $D$ dominate themselves; there is no requirement that they have another member of $D$ as a neighbour.

The graph is cubic if every vertex has degree three. It is $3$-connected if $n\geq4$ and deleting any set of at most two vertices leaves a connected graph. The proposed inequality is \[ \gamma(G)\leq\left\lceil\frac n3\right\rceil \qquad\text{for every $3$-connected cubic graph }G. \] Thus one asks for a set of at most the stated rounded-up size meeting the closed neighbourhood of every vertex.

No independence or connectedness condition is imposed on $D$. The graph need not be planar, bipartite, or have large girth. Vertex connectivity is part of the hypothesis, so the problem is not the assertion for arbitrary cubic graphs. The ceiling has its ordinary integer meaning and matters at orders not divisible by three. The quantification includes every admissible finite order, rather than only an asymptotic estimate with an unspecified additive error.

Short English statement

Can every 3-connected cubic graph be dominated by at most one third of its vertices, rounded up?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and attack plan.

Kelmans [R1] gives counterexamples of connectivity two to the older assertion for all cubic graphs. Those counterexamples do not satisfy the present three-connectivity hypothesis. This distinction is essential: one cannot strengthen the induction hypothesis to arbitrary cubic components after cutting a graph apart. We prove the desired inequality for graphs with a suitable spanning cycle structure, retaining the exact rounding cost, then examine why an arbitrary collection of cycles does not suffice.

A direct construction from a Hamilton cycle.

Suppose $G$ has a spanning cycle $v_0v_1\cdots v_{n-1}v_0$. Take \[ D=\{v_0,v_3,v_6,\ldots,v_{3\lfloor(n-1)/3\rfloor}\}. \] This set has $\lceil n/3\rceil$ vertices. Consecutive chosen vertices around the cycle are separated by at most three cycle edges, including the final gap returning to $v_0$. In a gap of length three, its two interior vertices are each adjacent to an endpoint; in shorter gaps the same conclusion holds. Thus $D$ dominates the whole cycle, and therefore all of $G$. Additional edges cannot destroy domination. This proves the required upper bound for every Hamiltonian instance, without needing regularity or three-connectivity in this restricted proof.

Keeping exact track of a spanning $2$-factor.

More generally, suppose $F$ is a spanning union of vertex-disjoint cycles of lengths $\ell_1,\ldots,\ell_s$. Apply the preceding choice separately on each cycle and take the union. If $c_j$ counts cycles with length congruent to $j$ modulo three for $j=1,2$, then \[ \gamma(G)\le\sum_{i=1}^s\left\lceil\frac{\ell_i}{3}\right\rceil =\frac n3+\frac{2c_1+c_2}{3}. \] This is a proved upper bound for each specific factor. In particular, if $2c_1+c_2\le2$, its right side is $\lceil n/3\rceil$. Indeed, it is an integer at least $n/3$ and strictly below $n/3+1$. Thus a factor all of whose cycles have lengths divisible by three works, as does one with only a single exceptional cycle, or with two exceptional cycles both of length two modulo three.

The exact defect $2c_1+c_2$ matters. Bounding the number of cycles without controlling their residues produces an additive loss, which cannot be silently absorbed by the single ceiling in the question. To prove the full target by this route one would need either a suitable factor for every input graph, or a way to exploit edges between cycles to save enough of these independently selected dominators.

Why a poor factor does not refute the target.

In the cube graph $Q_3$, choose the two disjoint square faces obtained by fixing one coordinate. They form a spanning $2$-factor with $c_1=2$. The independent cycle construction gives four dominators, whereas $\lceil8/3\rceil=3$. But in fact two opposite vertices, $000$ and $111$, dominate the cube: every binary triple differs in at most one coordinate from one of them. The edges joining the two squares supply exactly the interactions discarded by treating the cycles separately. Therefore a bad residue count for one factor is an obstruction to this argument, not a counterexample to the conjecture.

There is also a universal elementary lower bound. In a cubic graph, each closed neighbourhood has four vertices, so any dominating set satisfies $4|D|\ge n$. Thus $\gamma(G)\ge\lceil n/4\rceil$. The cube meets this bound. These inequalities are compatible with the conjecture, but the counting lower bound gives no selection mechanism at the upper threshold.

Verification.

The script scripts/check_attempt_batch02_algebra_2026_10_01.py constructs $K_4$, $K_{3,3}$, the triangular prism, the cube and the Petersen graph. It checks that each is cubic and remains connected after deletion of any set of at most two vertices. Exhaustive enumeration of vertex subsets gives domination numbers $1,2,2,2,3$, respectively. It also verifies the cyclic placement construction for cycle lengths three through one hundred. These checks exercise both rounding classes and the closed-neighbourhood convention. They do not enumerate all three-connected cubic graphs of any unbounded order.

Final status and first remaining gap.

UNRESOLVED. The Hamiltonian and stated $2$-factor subcases satisfy the exact inequality. The missing step is a global choice or exchange argument controlling the residue losses for every graph in the hypothesis. Three-connectivity has not yet been converted into such an argument, and lower-connectivity counterexamples cannot be used to skip that requirement.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3155 (OPG-37038), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Domination in cubic graphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/domination_in_cubic_graphs.

• R1 Alexander Kelmans, Counterexamples to the Cubic Graph Domination Conjecture, 2006. Primary abstract checked 1 October 2026; its counterexamples of connectivity two are distinguished from the present three-connected question. https://arxiv.org/abs/math/0607512.