×

Modified linear programming and class 0 bounds for graph pebbling. (English) Zbl 1384.90112

Summary: 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.

MSC:

90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Blasiak A, Czygrinow A, Fu A, Herscovici D, Hurlbert G, Schmitt JR (2012) Sparse graphs with small pebbling number. Manuscript
[2] Bukh B (2006) Maximum pebbling number of graphs of diameter three. J Graph Theory 52:353-357 · Zbl 1099.05076 · doi:10.1002/jgt.20187
[3] Chung F (1989) Pebbling in hypercubes. SIAM J Discrete Math 2:467-472 · Zbl 0727.05043 · doi:10.1137/0402041
[4] Clark B, Milans K (2006) The complexity of graph pebbling. SIAM J Discrete Math 20:769-798 · Zbl 1123.05088 · doi:10.1137/050636218
[5] Clarke TA, Hochberg RA, Hurlbert GH (1997) Pebbling in diameter two graphs and products of paths. J Graph Theory 25:119-128 · Zbl 0881.05109 · doi:10.1002/(SICI)1097-0118(199706)25:2<119::AID-JGT3>3.0.CO;2-P
[6] Erdős P, Ginzburg A, Ziv A (1961) A theorem in additive number theory. Bull Res Council Isr 10F:41-43 · Zbl 0063.00009
[7] Feng R, Kim JY (2001) Graham’s pebbling conjecture on product of complete bipartite graphs. Sci China Ser A 44:817-822 · Zbl 0999.05096 · doi:10.1007/BF02880130
[8] Feng R, Kim JY (2002) Pebbling numbers of some graphs. Sci China Ser A 45:470-478 · Zbl 1100.05507 · doi:10.1007/BF02872335
[9] Gross JL, Yellen J, Zhang P (2006) Graph theory and its applications, 2nd edn. Chapman & Hall/CRC, Boca Raton · Zbl 1082.05001
[10] Herscovici D (2003) Graham’s pebbling conjecture on products of cycles. J Graph Theory 42:141-154 · Zbl 1008.05144 · doi:10.1002/jgt.10080
[11] Herscovici DS (2008) Graham’s pebbling conjecture on products of many cycles. Discrete Math 308:6501-6512 · Zbl 1186.05105 · doi:10.1016/j.disc.2007.12.045
[12] Hurlbert G (2011) A linear optimization technique for graph pebbling. Preprint, available at: arXiv:1101.5641 · Zbl 0672.10038
[13] Hurlbert G (1999) A survey of graph pebbling. Congr Numer 139:41-64 · Zbl 0961.05067
[14] Hurlbert G (2005) Recent progress in graph pebbling. Graph Theory Notes New York XLIX:25-37
[15] Lemke P, Kleitman D (1989) An addition theorem on the integers modulo \[n\] n. J Number Theory 31:335-345 · Zbl 0672.10038 · doi:10.1016/0022-314X(89)90077-2
[16] Moews D (1992) Pebbling graphs. J Comb Theory Ser B 55:244-252 · Zbl 0772.05093 · doi:10.1016/0095-8956(92)90043-W
[17] 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 · Zbl 0895.05063
[18] Postle L (2014) Pebbling graphs of fixed diameter. J Graph Theory 75:302-310 · Zbl 1292.05210 · doi:10.1002/jgt.21736
[19] Postle L, Streib N, Yerger C (2013) Pebbling graphs of diameter three and four. J Graph Theory 72:398-417 · Zbl 1262.05042 · doi:10.1002/jgt.21648
[20] Watson N (2005) The complexity of pebbling and cover pebbling. Preprint, available at: arXiv:math/0503511
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.