Optimal pebbling and rubbling of graphs with given diameter

DOI10.1016/J.DAM.2018.06.014zbMATH Open1464.05265arXiv1708.09177OpenAlexW2963423189WikidataQ129599310 ScholiaQ129599310MaRDI QIDQ2026352FDOQ2026352

Authors: Gyula Y. Katona, László F. Papp, Ervin Győri 

Publication date: 19 May 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number $p{i}_{opt}$ is the smallest number $m$ needed to guarantee a pebble distribution of $m$ pebbles from which any vertex is reachable. A rubbling move is similar to a pebbling move, but it can remove the two pebbles from two different vertex. The optimal rubbling number $h{o}_{opt}$ is defined analogously to the optimal pebbling number. In this paper we give lower bounds on both the optimal pebbling and rubbling numbers by the distance $k$ domination number. With this bound we prove that for each $k$ there is a graph $G$ with diameter $k$ such that $h{o}_{opt}(G)=p{i}_{opt}(G)=2^k$.

Full work available at URL: https://arxiv.org/abs/1708.09177

Recommendations

• Bounds on the rubbling and optimal rubbling numbers of graphs
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Optimal pebbling of graphs
• Rubbling and optimal rubbling of graphs
• The optimal rubbling number of ladders, prisms and Möbius-ladders

zbMATH Keywords

diameterrubblinggraph pebblingdistance domination

Mathematics Subject Classification ID

Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Pebbling in Hypercubes
• Rubbling and optimal rubbling of graphs
• Bounds on the rubbling and optimal rubbling numbers of graphs
• The optimal rubbling number of ladders, prisms and Möbius-ladders
• Title not available (Why is that?)
• Pebbling and optimal pebbling in graphs
• The Complexity of Graph Pebbling
• The optimal pebbling number of the complete \(m\)-ary tree
• Optimal pebbling in products of graphs
• The optimal pebbling number of the caterpillar
• Optimal pebbling of graphs
• The optimal pebbling number of staircase graphs

Cited In (13)

• Pebbling graphs of fixed diameter
• A note on optimal pebbling of hypercubes
• The optimal pebbling of spindle graphs
• Capacity restricted optimal pebbling in graphs
• Optimal pebbling of graphs
• Pebbling and optimal pebbling in graphs
• Pebbling Algorithms in Diameter Two Graphs
• Rubbling and optimal rubbling of graphs
• Optimal t-rubbling on complete graphs and paths
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Strict optimal rubbling of graphs
• Optimal pebbling number of graphs with given minimum degree
• 1-restricted optimal rubbling on graphs

This page was built for publication: Optimal pebbling and rubbling of graphs with given diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2026352)