Variations, generalizations, and structural analysis of graph pebbling.

摘要

Graph pebbling is essentially a game that can be played on any connected graph. It has the potential to be used as a model for the distribution and transportation of consumable resources. The underlying pebbling moves are well-defined and the subject as a whole contains rich theoretical underpinnings. Although it was created in 1989 to solve a problem from number theory, graph pebbling has gained in popularity over the years and become an interesting field in its own right.;The optimal pebbling number of a given graph can be determined by solving an instance of a particular integer optimization problem. This fact suggests the existence of a graph invariant which is dual to the optimal pebbling number. In this dissertation, a combinatorial description of this graph invariant is presented. Furthermore, the integer constraints of the optimization problem for optimal pebbling are relaxed and the traditional notions of pebbling configurations and pebbling moves are generalized. This fractionalized version of pebbling gives rise to a new pebbling invariant, the optimal fractional pebbling number of a graph. Optimal fractional pebbling numbers of various graphs such as cliques, cubes, cycles, paths, and complete bipartite graphs are calculated. In addition, every graph is shown to have an optimal fractional configuration that is uniform on its orbits.;Many fundamental pebbling results address how structural properties of a graph affect pebbling numbers. In fact, some of the earliest bounds on the pebbling number of a graph depend on its diameter. In this dissertation, it is shown that the pebbling number of a graph with blocks of small diameter is equal to the pebbling number of a suitably chosen spanning tree. In addition, a construction is presented which builds graphs with large pebbling numbers and provides asymptotic bounds on the pebbling numbers of all graphs of a given order and diameter. Finally, free pebbling is introduced as a variation of standard pebbling and basic lower bounds and exact values for the resulting graph invariants are obtained.