Pebbling in 2-Paths

Graph pebbling is a network model for transporting discrete resources that are consumed in transit. Deciding whether a given configuration on a particular graph can reach a specified target is NP-complete, even for diameter two graphs, and deciding whether the pebbling number has a prescribed upper bound is -complete. Recently we proved that the pebbling number of a split graph can be computed in polynomial time. This paper continues the program of finding other polynomial classes, moving away from the large tree width, small diameter case (such as split graphs) to small tree width, large diameter, beginning an investigation on the important subfamily of chordal graphs called k-trees. In particular, we provide a formula for the pebbling number of any 2-path.