t-pebbling and extensions

DOI10.1007/S00373-012-1152-4zbMATH Open1268.05129arXiv0905.3949OpenAlexW2133314113MaRDI QIDQ354409FDOQ354409

David S. Herscovici, Glenn H. Hurlbert, Benjamin D. Hester

Publication date: 19 July 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t >= 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis, et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.

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

Recommendations

• \(t\)-pebbling the graphs of diameter two
• \(t\)-pebbling number in graphs
• Optimally \(t\)-pebbling graphs
• Optimal pebbling of graphs
• Pebbling graphs of diameter three and four

zbMATH Keywords

algorithmupper boundpebbling numberdiameter-two graphfractional pebblinggraph pebblinginitial distributionoptimal pebblingpebbling movestarget distribution

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Graph theory (05C99)

Cites Work

• Title not available (Why is that?)
• Pebbling in Hypercubes
• Optimally pebbling hypercubes and powers
• Title not available (Why is that?)
• Pebbling and optimal pebbling in graphs
• Pebbling in diameter two graphs and products of paths
• Title not available (Why is that?)
• The weight function lemma for graph pebbling
• Pebbling graphs of diameter three and four
• On Pebbling Graphs by Their Blocks
• Pebbling Algorithms in Diameter Two Graphs
• Graham's pebbling conjecture on products of cycles
• Maximum pebbling number of graphs of diameter three

Cited In (12)

• Pebbling on Graph Products and other Binary Graph Constructions
• The weight function lemma for graph pebbling
• Optimal pebbling on grids
• On the \(t\)-pebbling number and the \(2t\)-pebbling property of graphs
• On the target pebbling conjecture
• Pebbling in 2-paths
• Graph pebbling algorithms and Lemke graphs
• Optimal t-rubbling on complete graphs and paths
• Pebbling in powers of paths
• Optimal pebbling number of the square grid
• Pebbling in semi-2-trees
• The complexity of pebbling reachability and solvability in planar and outerplanar graphs

This page was built for publication: \(t\)-pebbling and extensions

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