2019/05/21 by Franklin Kenter, Kenter, Franklin, Daphne Skipper +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1905.08683
openalex publication_date 2019/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a distribution of pebbles to the vertices of a graph, a pebbling move removes two pebbles from a single vertex and places a single pebble on an adjacent vertex. The pebbling number π(G) is the smallest number such that, for any distribution of π(G) pebbles to the vertices of G and choice of root vertex r of G, there exists a sequence of pebbling moves that places a pebble on r. Computing π(G) is provably difficult, and recent methods for bounding π(G) have proved computationally intractable, even for moderately sized graphs. Graham conjectured that π(G ~\square~ H) ≤ π(G) π(H), where G ~\square~ H is the Cartesian product of G and H (1989). While the conjecture has been verified for specific families of graphs, in general it remains open. This study combines the focus of developing a computationally tractable, IP-based method for generating good bounds on π(G ~\square~ H), with the goal of shedding light on Graham's conjecture.We provide computational results for a variety of Cartesian-product graphs, including some that are known to satisfy Graham's conjecture and some that are not. Our approach leads to a sizable improvement on the best known bound for π(L ~\square~ L), where L is the Lemke graph, and L ~\square~ L is among the smallest known potential counterexamples to Graham's conjecture.