Pebbling in Split Graphs

Abstract

Graph pebbling is a network optimization model for transporting discrete resourcesthat are consumed in transit: the movement of 2 pebbles across an edge consumes one of thepebbles. The pebbling number of a graph is the fewest number of pebblestso that, from anyinitial configuration oftpebbles on its vertices, one can place a pebble on any given target vertex viasuch pebbling steps. It is known that deciding whether a given configuration on a particular graphcan reach a specified target isNP-complete, even for diameter 2 graphs, and that deciding whetherthe pebbling number has a prescribed upper bound is ΠP2-complete. On the other hand, for manyfamilies of graphs there are formulas or polynomial algorithms for computing pebbling numbers; forexample, complete graphs, products of paths (including cubes), trees, cycles, diameter 2 graphs, andmore. Moreover, graphs having minimum pebbling number are called Class 0, and many authors havestudied which graphs are Class 0 and what graph properties guarantee it, with no characterizationin sight. In this paper we investigate an important family of diameter 3 chordal graphs called splitgraphs; graphs whose vertex set can be partitioned into a clique and an independent set. We provide aformula for the pebbling number of a split graph, along with an algorithm for calculating it that runsinO(nβ) time, whereβ=2ω/(ω+1)∼=1.41 andω∼=2.376 is the exponent of matrix multiplication.Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0.