Abstract
Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move removes two pebbles from some vertex and places one pebble on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. First, we improve on results of Hurlbert, who introduced a linear optimization technique for graph pebbling. In particular, we use a different set of weight functions, based on graphs more general than trees. We apply this new idea to some graphs from Hurlbert’s paper to give improved bounds on their pebbling numbers. Second, we investigate the structure of Class 0 graphs with few edges. We show that every n-vertex Class 0 graph has at least \(\frac{5}{3}n - \frac{11}{3}\) edges. This disproves a conjecture of Blasiak et al. For diameter 2 graphs, we strengthen this lower bound to \(2n - 5\), which is best possible. Further, we characterize the graphs where the bound holds with equality and extend the argument to obtain an identical bound for diameter 2 graphs with no cut-vertex.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Blasiak A, Czygrinow A, Fu A, Herscovici D, Hurlbert G, Schmitt JR (2012) Sparse graphs with small pebbling number. Manuscript
Bukh B (2006) Maximum pebbling number of graphs of diameter three. J Graph Theory 52:353–357
Chung F (1989) Pebbling in hypercubes. SIAM J Discrete Math 2:467–472
Clark B, Milans K (2006) The complexity of graph pebbling. SIAM J Discrete Math 20:769–798
Clarke TA, Hochberg RA, Hurlbert GH (1997) Pebbling in diameter two graphs and products of paths. J Graph Theory 25:119–128
Erdős P, Ginzburg A, Ziv A (1961) A theorem in additive number theory. Bull Res Council Isr 10F:41–43
Feng R, Kim JY (2001) Graham’s pebbling conjecture on product of complete bipartite graphs. Sci China Ser A 44:817–822
Feng R, Kim JY (2002) Pebbling numbers of some graphs. Sci China Ser A 45:470–478
Gross JL, Yellen J, Zhang P (2006) Graph theory and its applications, 2nd edn. Chapman & Hall/CRC, Boca Raton
Herscovici D (2003) Graham’s pebbling conjecture on products of cycles. J Graph Theory 42:141–154
Herscovici DS (2008) Graham’s pebbling conjecture on products of many cycles. Discrete Math 308:6501–6512
Hurlbert G (2011) A linear optimization technique for graph pebbling. Preprint, available at: arXiv:1101.5641
Hurlbert G (1999) A survey of graph pebbling. Congr Numer 139:41–64
Hurlbert G (2005) Recent progress in graph pebbling. Graph Theory Notes New York XLIX:25–37
Lemke P, Kleitman D (1989) An addition theorem on the integers modulo \(n\). J Number Theory 31:335–345
Moews D (1992) Pebbling graphs. J Comb Theory Ser B 55:244–252
Pachter L, Snevily HS, Voxman B (1995) On pebbling graphs. Proccedings of the Twenty-Sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), vol. 107, pp. 65–80
Postle L (2014) Pebbling graphs of fixed diameter. J Graph Theory 75:302–310
Postle L, Streib N, Yerger C (2013) Pebbling graphs of diameter three and four. J Graph Theory 72:398–417
Watson N (2005) The complexity of pebbling and cover pebbling. Preprint, available at: arXiv:math/0503511
Acknowledgments
Daniel W. Cranston was partially supported by NSA Grant H98230-15-1-0013.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cranston, D.W., Postle, L., Xue, C. et al. Modified linear programming and class 0 bounds for graph pebbling. J Comb Optim 34, 114–132 (2017). https://doi.org/10.1007/s10878-016-0060-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0060-6