Pebbling in powers of paths

The t -fold pebbling number, pi t(G), of a graph G is defined to be the minimum number m so that, from any given configuration of m pebbles on the vertices of G, it is possible to place at least t pebbles on any specified vertex via pebbling moves. It has been conjectured that the pebbling numbers of pyramid-free chordal graphs can be calculated in polynomial time.The kth power G(k) of the graph G is obtained from G by adding an edge between any two vertices of distance at most k from each other. The kth power of the path Pn on n vertices is an important class of pyramid-free chordal graphs, and is a stepping stone to the more general class of k-paths and the still more general class of interval graphs. Pachter, Snevily, and Voxman (1995) calculated pi(Pn(2)), Kim (2004) calculated pi (P(3) n ), and Kim and Kim (2010) calculated pi(Pn(4)). In this paper we calculate pi t(Pn(k)) for all n, k, and t.For a function D : V (G)-> N, the D -pebbling number, pi (G, D), of a graph G is defined to be the minimum number m so that, from any given configuration of m pebbles on the vertices of G, it is possible to place at least D(v) pebbles on each vertex v via pebbling moves. It has been conjectured that pi (G, D) <= pi|D|(G) for all G and D. We make the stronger conjecture that every G and D satisfies pi (G, D) <= pi|D|(G) - (s(D) - 1), where s(D) counts the number of vertices v with D(v) > 0. We prove that trees and Pn(k), for all n and k, satisfy the stronger conjecture.The pebbling exponent e pi (G) of a graph G was defined by Pachter et al., to be the minimum k for which pi(G(k)) = n(G(k)). Of course, e pi (G) <= diam(G), and Czygrinow, Hurlbert, Kierstead, and Trotter (2002) proved that almost all graphs G have e pi (G) =1. Lourdusamy and Mathivanan (2015) proved several results on pi t(Cn2), and Hurlbert (2017) proved an asymptotically tight formula for e pi(Cn). Our formula for pi t(Pn(k)) allows us to compute e pi (Pn) within additively narrow bounds.(c) 2023 Elsevier B.V. All rights reserved.