Skip to content
DraconiticResearch
Search Sources API
194,161 studies31 sourcesUpdated 15 min ago
PreprintarXiv licencearXiv

Pebbling Numbers and Generator Reinforcement of Cayley Graphs

  • Yuan Yang
  • Bocheng Li
  • Qingzhong Ji
Open at sourcePDFDOICite

Abstract

We study inverse-closed generator additions of minimum size that make the optimal pebbling number of a finite Cayley graph at most three while preserving its specified regular action. A weighted vertex-cover formulation on inverse orbits yields an O(|Γ|2) algorithm for abelian groups in the explicit multiplication-table model. We derive formulas for central involutions and cubelike graphs, with an inverse-closure correction determined by square roots in the uncovered set. The exact thresholds are 2d−1−d for hypercubes (d≥1), and $3$ for standard Keller graphs when d=2 and 2d−1 when d≥3. Every admissible augmentation of either family has ordinary pebbling number equal to its order.

Related

  1. Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers
    Guantao Chen, Shengze Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Odd-ordered Cayley graphs satisfy Erdős--Gyárfás
    Michael C. Burkhart
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. COLORING SEMIMINIMAL CAYLEY GRAPHS
    Ignacio Garc Ía-Marco, Kolja Knauer, Giuliamaria Menara
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL
  5. On Edge-Primitive $2$-Arc-Transitive (Bi-)Cayley Graphs
    Hao Nan Chen, Jing Jian Li, Ji Cheng Ma +1
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref

Cite

BibTeXRIS
BibTeX
@misc{yang2026pebbling,
  title = {{Pebbling Numbers and Generator Reinforcement of Cayley Graphs}},
  author = {Yuan Yang and Bocheng Li and Qingzhong Ji},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41306},
  eprint = {2610.41306},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41306},
}
RIS
TY  - UNPB
TI  - Pebbling Numbers and Generator Reinforcement of Cayley Graphs
AU  - Yuan Yang
AU  - Bocheng Li
AU  - Qingzhong Ji
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41306
UR  - https://arxiv.org/abs/2610.41306
AB  - We study inverse-closed generator additions of minimum size that make the optimal pebbling number of a finite Cayley graph at most three while preserving its specified regular action. A weighted vertex-cover formulation on inverse orbits yields an O(|Γ|^2) algorithm for abelian groups in the explicit multiplication-table model. We derive formulas for central involutions and cubelike graphs, with an inverse-closure correction determined by square roots in the uncovered set. The exact thresholds are 2^d−1−d for hypercubes (d≥1), and $3$ for standard Keller graphs when d=2 and 2^d−1 when d≥3. Every admissible augmentation of either family has ordinary pebbling number equal to its order.
ER  -