×

Graph pebbling algorithms and Lemke graphs. (English) Zbl 1411.05246

Summary: Given a simple, connected graph, a pebbling configuration (or just configuration) is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex \(r\) is said to be reachable from a configuration if there exists a sequence of pebbling moves that places at least one pebble on \(r\). A configuration is solvable if every vertex is reachable. The pebbling number\(\pi (G)\) of a graph \(G\) is the minimum integer such that every configuration of size \(\pi(G)\) on \(G\) is solvable. A graph \(G\) is said to satisfy the two-pebbling property if for any configuration with more than \(2 \pi (G)-q\) pebbles, where \(q\) is the number of vertices with pebbles, two pebbles can be moved to any vertex of \(G\). A Lemke graph is a graph that does not satisfy the two-pebbling property. In this paper we present a new algorithm to determine if a vertex is reachable with a given configuration and if a configuration on a graph is solvable. We also discuss straightforward algorithms to compute the pebbling number and to determine whether or not a graph has the two-pebbling property. Finally, we use these algorithms to determine all Lemke graphs on at most 9 vertices, finding many previously unknown Lemke graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C40 Connectivity
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C57 Games on graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] L. Alcón, M. Gutierrez, G. Hurlbert, Pebbling in Split Graphs, ArXiv e-prints, 2012.; L. Alcón, M. Gutierrez, G. Hurlbert, Pebbling in Split Graphs, ArXiv e-prints, 2012.
[2] Alcón, L.; Gutierrez, M.; Hurlbert, G., Pebbling in 2-paths, Electron. Notes Discrete Math., 50, 145-150 (2015), LAGOS’15 VIII Latin-American Algorithms, Graphs and Optimization Symposium · Zbl 1347.05120
[3] Alcón, L.; Gutierrez, M.; Hurlbert, G., Pebbling in semi-2-trees, Discrete Math., 340, 7, 1467-1480 (2017) · Zbl 1361.05122
[4] Bekmetjev, A.; Cusack, C. A., Pebbling algorithms in diameter two graphs, SIAM J. Discret. Math., 23, 2, 634-646 (2009) · Zbl 1191.05083
[5] Blasiak, A.; Schmitt, J., Degree sum conditions in graph pebbling, Australas. J. Combin., 42, 83-90 (2008) · Zbl 1153.05066
[6] Bunde, D. P.; Chambers, E. W.; Cranston, D.; Milans, K.; West, D. B., Pebbling and optimal pebbling in graphs, J. Graph Theory, 57, 3, 215-238 (2008) · Zbl 1142.05046
[7] Chung, F. R., Pebbling in hypercubes, SIAM J. Discrete Math., 2, 4, 467-472 (1989) · Zbl 0727.05043
[8] Clarke, T. A.; Hochberg, R. A.; Hurlbert, G. H., Pebbling in diameter two graphs and products of graphs, J. Graph Theory, 25, 119-128 (1997) · Zbl 0881.05109
[9] Crull, B.; Cundiff, T.; Feltman, P.; Hurlbert, G. H.; Pudwell, L.; Szaniszlo, Z.; Tuza, Z., The cover pebbling number of graphs, Discrete Math., 296, 1, 15-23 (2005) · Zbl 1066.05140
[10] C.A. Cusack, A. Green, A. Bekmetjev, M. Powers, [dataset] http://algoraph.hope.edu/?page=data; C.A. Cusack, A. Green, A. Bekmetjev, M. Powers, [dataset] http://algoraph.hope.edu/?page=data
[11] Cusack, C. A.; Lewis, T.; Simpson, D.; Taggart, S., The complexity of pebbling in diameter two graphs, SIAM J. Discrete Math., 26, 3, 919-928 (2012) · Zbl 1258.68066
[12] Gao, Z.-T.; Yin, J.-H., The proof of a conjecture due to Snevily, Discrete Math., 310, 10, 1614-1621 (2010) · Zbl 1225.05181
[13] Gao, Z.-T.; Yin, J.-H., Lemke graphs and Graham’s pebbling conjecture, Discrete Math., 340, 2318-2332 (2017) · Zbl 1365.05196
[14] Herscovici, D.; Hester, B.; Hurlbert, G., T-pebbling and extensions, Graphs Combin., 29, 4, 955-975 (2013) · Zbl 1268.05129
[15] Hurlbert, G., The weight function lemma for graph pebbling, J. Comb. Optim., 34, 2, 343-361 (2017) · Zbl 1383.90042
[16] G. Hurlbert, H. Kierstead, On the Complexity of Graph Pebbling, unpublished, 2005.; G. Hurlbert, H. Kierstead, On the Complexity of Graph Pebbling, unpublished, 2005.
[17] Lewis, T.; Cusack, C. A.; Dion, L., The complexity of pebbling reachability and solvability in planar and outerplanar graphs, Discrete Appl. Math., 172, 62-74 (2014) · Zbl 1288.05225
[18] B. McKay, http://users.cecs.anu.edu.au/ bdm/data; B. McKay, http://users.cecs.anu.edu.au/ bdm/data
[19] Milans, K.; Clark, B., The complexity of graph pebbling, SIAM J. Discret. Math., 20, 3, 769-798 (2006) · Zbl 1123.05088
[20] Moews, D., Pebbling graphs, J. Combin. Theory Ser. B, 55, 2, 244-252 (1992) · Zbl 0772.05093
[21] Pachter, L.; Snevily, H. S.; Voxman, B., On pebbling graphs, Congr. Numer., 107, 65-80 (1995) · Zbl 0895.05063
[22] Sieben, N., A graph pebbling algorithm on weighted graphs, J. Graph Algortihms Appl., 14, 2, 221-244 (2010) · Zbl 1213.05253
[23] Snevily, H. S.; Foster, J. A., The 2-pebbling property and a conjecture of Graham’s, Graphs Combin., 16, 2, 231-244 (2000) · Zbl 0971.05063
[24] Wang, S. S., Pebbling and Graham’s conjecture, Discrete Math., 226, 1, 431-438 (2001) · Zbl 0982.05100
[25] N.G. Watson, The Complexity of Pebbling and Cover Pebbling, ArXiv Mathematics e-prints, 2005.; N.G. Watson, The Complexity of Pebbling and Cover Pebbling, ArXiv Mathematics e-prints, 2005.
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.