Optimal pebbling and rubbling of graphs with given diameter

DOI10.1016/J.DAM.2018.06.014MaRDI QIDQ2026352zbMATH OpenOpenAlexWikidataFDO

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)

Full work available at URL https://arxiv.org/abs/1708.09177, http://real.mtak.hu/89787/1/1708.09177

zbMATH Keywords

diameterrubblinggraph pebblingdistance domination

Mathematics Subject Classification ID

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

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$.

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

Cites work

• scientific article; zbMATH DE number 1145909 (Why is no real title available?)
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Optimal pebbling in products of graphs
• Optimal pebbling of graphs
• Pebbling and optimal pebbling in graphs
• Pebbling in Hypercubes
• Rubbling and optimal rubbling of graphs
• The Complexity of Graph Pebbling
• The optimal pebbling number of staircase graphs
• The optimal pebbling number of the caterpillar
• The optimal pebbling number of the complete \(m\)-ary tree
• The optimal rubbling number of ladders, prisms and Möbius-ladders

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
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Optimal t-rubbling on complete graphs and paths
• 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)