Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.07014 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909042824183808 |
|---|---|
| author | Niu, Tong |
| author_facet | Niu, Tong |
| contents | 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 π(B_i) \le 34$ for $i=1,2$. Bridi, Marquezino and Figueiredo (arXiv:2505.16050, 2025) then sharpened the upper side to $π(B_1) \le 31$ and $π(B_2) \le 30$ via a Weight Function Lemma heuristic. We push the upper bounds further to $π(B_1) \le 28$ and $π(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 $π(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]$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07014 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Upper Bounds on the Pebbling Numbers of the Blanuša Snarks Niu, Tong Combinatorics 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 π(B_i) \le 34$ for $i=1,2$. Bridi, Marquezino and Figueiredo (arXiv:2505.16050, 2025) then sharpened the upper side to $π(B_1) \le 31$ and $π(B_2) \le 30$ via a Weight Function Lemma heuristic. We push the upper bounds further to $π(B_1) \le 28$ and $π(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 $π(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]$. |
| title | Improved Upper Bounds on the Pebbling Numbers of the Blanuša Snarks |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.07014 |