Improved Upper Bounds on the Pebbling Numbers of the Blanuša Snarks

Abstract

The two Blanuša snarks $B_1$ and $B_2$ are 3-regular graphs on 18 vertices. Dantas, Lordelo, Niedermaier and Nogueira (Discrete Appl. Math. 361, 2025, pp. 336-346) established the first systematic bounds $23\le \pi (B_i)\le 34$ for $i=1,2$. Bridi, Marquezino and Figueiredo (arXiv:2505.16050, 2025) then sharpened the upper side to $\pi (B_1)\le 31$ and $\pi (B_2)\le 30$ via a Weight Function Lemma heuristic. We push the upper bounds further to $\pi (B_1)\le 28$ and $\pi (B_2)\le 29$. The route is again Hurlbert's Weight Function Lemma, but applied one automorphism orbit at a time, with optimal weight functions coming from a linear program over a corpus of roughly $30,000$ rooted-subtree strategies per target. For the lower bound $\pi (B_i)\ge 23$ we re-derive the witnesses of Dantas et al. and re-verify them with two independent oracles: an exhaustive forward state-space search, and a sound-and-complete MILP encoding whose acyclicity constraint is motivated by the Milans-Clark No-Cycle Lemma. The interval for $B_1$ shrinks from $[23,31]$ to $[23,28]$, and for $B_2$ from $[23,30]$ to $[23,29]$.

arXiv commentv3: add missing citation to Bridi-Marquezino-Figueiredo (arXiv:2505.16050, 2025) and correct the framing: their Weight Function Lemma heuristic had already pushed the Blanusa upper bounds from 34 to 31 (B1) and 30 (B2); this paper's improvements 28 (B1) and 29 (B2) are over their bounds, not Dantas et al.'s