New lower bounds on domination--packing ratios in connected subcubic and cubic graphs

Abstract

For a graph \(G\), let \(γ(G)\) and \(ρ(G)\) denote its domination number and packing number, respectively. Let \(c_{\mathrm{sub}}\) and \(c_{\mathrm{cub}}\) denote the respective limsups of \(γ(G)/ρ(G)\) over connected subcubic and connected cubic graphs as \(ρ(G)\to\infty\). We prove \[ c_{\mathrm{sub}}\geq\frac{13}{6}, \qquad c_{\mathrm{cub}}\geq\frac{17}{8}, \] by constructing two explicit binary branching families. The connected noncubic subcubic graphs \(\widehat B_t^\star\) satisfy \[ |V(\widehat B_t^\star)|=76\cdot2^t-12,\qquad γ(\widehat B_t^\star)=26\cdot2^t-4,\qquad ρ(\widehat B_t^\star)=12\cdot2^t-2, \] whereas the connected cubic graphs \(\widehat B_t^\bullet\) satisfy \[ |V(\widehat B_t^\bullet)|=108\cdot2^t-14,\qquad γ(\widehat B_t^\bullet)=34\cdot2^t-4,\qquad ρ(\widehat B_t^\bullet)=16\cdot2^t-2. \] The constructions use the same binary connector composition and closing lemma, with different connectors and initial assemblies. As a consequence, both families give unbounded additive violations of \(γ(G)\leq2ρ(G)+1\), disproving the proposed inequality even for connected cubic graphs.

Disclosure

“is cubic, then 8γ(G) ≤ 17ρ(G) + 7. (3) In general, 6γ(G) ≤ 13ρ(G) + 5. Acknowledgments This project originated when the second author, an undergraduate, used OpenAI Codex, primarily with the GPT-5.6 Sol model, to identify an open conjecture and explore possible solutions. This preliminary AI-assisted exploration led to Conjecture 1.1 and suggested a candidate counterexample based on path-like assemblies of copies of the graph now deno”

PDF page 15

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-23T05:16:58.650361Z

Structural counts