2018/01/23 by Asplund, John, Hurlbert, Glenn, Kenter, Franklin
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1801.07808
Pebbling on graphs is a two-player game which involves repeatedly moving a pebble from one vertex to another by removing another pebble from the first vertex. The pebbling number π(G) is the least number of pebbles required so that, regardless of the initial configuration of pebbles, a pebble can reach any vertex. Graham conjectured that the pebbling number for the cartesian product, G \hspace1mm\square\hspace1mm H, is bounded above by π(G) π(H). We show that π(G\hspace1mm\square\hspace1mm H) ≤ 2π(G) π(H) and, more sharply, that π(G \hspace1mm\square\hspace1mm H) ≤ (π(G)+|G|) π(H). Furthermore, we provide similar results for other graph products and graph operations.