72:
For example, on a graph with 2 vertices and 1 edge connecting them, the pebbling number is 2. No matter how the two pebbles are placed on the vertices of the graph it is always possible to arrive at the desired result of the chosen vertex having a pebble; if the initial configuration is the
146: − 1 pebbles to put on the graph, then we could put one pebble on each vertex except the target. As no vertex has two or more pebbles, no moves are possible, so it is impossible to place a pebble on the target. Thus, the pebbling number must be greater than
154:
pebbles, there are two possible cases. If each vertex has one pebble, no moves are required. If any vertex is bare, at least one other vertex must have two pebbles on it, and one pebbling move allows a pebble to be added to any target vertex in the complete graph.
45:. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to an adjacent vertex (the second removed pebble is discarded from play). π(
498:
According to the stacking theorem, the initial configuration of pebbles that requires the most pebbles to be cover solved happens when all pebbles are placed on a single vertex. Based on this observation, define
582:
486:), is the minimum number of pebbles needed so that from any initial arrangement of the pebbles, after a series of pebbling moves, the graph is covered: there is at least one pebble on
779:
73:
configuration with one pebble per vertex, then the objective is trivially accomplished with zero pebbling moves. One of the central questions of graph pebbling is the value of π(
863:
691:
302:
68:
pebbles on the graph, it is possible, after a possibly-empty series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.
381:
210:
890:
806:
718:
408:
329:
237:
84:
Other topics in pebbling include cover pebbling, optimal pebbling, domination cover pebbling, bounds, and thresholds for pebbling numbers, as well as deep graphs.
437:
1011:
Pleanmani, Nopparat (2019). "Graham's pebbling conjecture holds for the product of a graph and a sufficiently large complete bipartite graph".
1303:
Proceedings of the Twenty-Sixth
Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995)
1276:
Proceedings of the
Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999)
1295:
1054:
Crull, Betsy; Cundiff, Tammy; Feltman, Paul; Hurlbert, Glenn H.; Pudwell, Lara; Szaniszlo, Zsuzsanna; Tuza, Zsolt (2005),
112:
38:
505:
455:
1175:
Watson, Nathaniel G.; Yerger, Carl R. (2006). "Cover pebbling numbers and bounds for certain families of graphs".
1335:
434:
Is the pebbling number of a
Cartesian product of graphs at most the product of the pebbling number of the graphs?
729:
608:
1113:
Vuong, Annalies; Wyckoff, M. Ian (October 18, 2004). "Conditions for
Weighted Cover Pebbling of Graphs".
817:
645:
252:
42:
1055:
458:
is at most equal to the product of the pebbling numbers of the factors. This has come to be known as
88:
344:
173:
1268:
1135:
1255:
1229:
1184:
1114:
1096:
1070:
1036:
17:
34:
1239:
1147:
1080:
1020:
972:
490:
vertex. A result called the stacking theorem finds the cover pebbling number for any graph.
1310:
1283:
1251:
1198:
1161:
1092:
1032:
984:
868:
784:
696:
386:
307:
215:
1306:
1279:
1247:
1194:
1157:
1088:
1028:
980:
1314:
911:
240:
131:
54:
1329:
1040:
447:
116:
1291:
1259:
1100:
92:
1217:
906:
411:
64:
Given any target or 'root' vertex in the graph and any initial configuration of
1243:
1084:
478:
introduced the concept of cover pebbling. The cover pebbling number of a graph
1024:
451:
332:
960:
123:
introduced the concept in the literature and defined the pebbling number, π(
120:
639:
The cover pebbling number is known for the following families of graphs:
108:
426:
1234:
1189:
1119:
1075:
976:
932:
167:
The pebbling number is known for the following families of graphs:
1152:
87:
One application of pebbling games is in the security analysis of
1177:
Bulletin of the
Institute of Combinatorics and Its Applications
1305:. Congressus Numerantium. Vol. 107. pp. 65–80.
1278:. Congressus Numerantium. Vol. 139. pp. 41–64.
934:
High
Parallel Complexity Graphs and Memory-Hard Functions
462:. It remains unsolved, although special cases are known.
1220:; Godbole, Anant P. (2008). "Improved pebbling bounds".
871:
820:
787:
732:
699:
648:
508:
389:
347:
310:
255:
218:
176:
884:
857:
800:
773:
712:
685:
576:
402:
375:
323:
296:
231:
204:
1013:Discrete Mathematics, Algorithms and Applications
619:. Then the cover pebbling number is the largest
577:{\displaystyle s(v)=\sum _{u\in V(G)}2^{d(u,v)}}
115:, as a tool for solving a particular problem in
470:) — the cover pebbling number of a graph
8:
107:The game of pebbling was first suggested by
1294:; Snevily, Hunter S.; Voxman, Bill (1995).
931:Alwen, Joël; Serbinenko, Vladimir (2014),
60:that satisfies the following condition:
1233:
1188:
1151:
1118:
1074:
876:
870:
831:
819:
792:
786:
759:
743:
731:
704:
698:
659:
647:
553:
528:
507:
394:
388:
358:
346:
315:
309:
282:
266:
254:
223:
217:
187:
175:
41:with zero or more pebbles on each of its
103:) — the pebbling number of a graph
955:
953:
951:
949:
923:
438:(more unsolved problems in mathematics)
774:{\displaystyle \gamma (P_{n})=2^{n}-1}
1056:"The cover pebbling number of graphs"
998:
443:
7:
965:SIAM Journal on Discrete Mathematics
1140:Electronic Journal of Combinatorics
858:{\displaystyle \gamma (W_{n})=4n-9}
686:{\displaystyle \gamma (K_{n})=2n-1}
422:
297:{\displaystyle \pi (P_{n})=2^{n-1}}
27:Mathematical game played on a graph
963:(1989). "Pebbling in hypercubes".
138:vertices is easily verified to be
49:), the pebbling number of a graph
25:
18:Graham's pebbling conjecture
429:Unsolved problem in mathematics
837:
824:
749:
736:
665:
652:
569:
557:
544:
538:
518:
512:
454:that the pebbling number of a
364:
351:
272:
259:
193:
180:
1:
376:{\displaystyle \pi (W_{n})=n}
205:{\displaystyle \pi (K_{n})=n}
1269:"A survey of graph pebbling"
1136:"The cover pebbling theorem"
460:Graham's pebbling conjecture
423:Graham's pebbling conjecture
1267:Hurlbert, Glenn H. (1999).
456:Cartesian product of graphs
1352:
1244:10.1016/j.disc.2006.06.032
1085:10.1016/j.disc.2005.03.009
130:The pebbling number for a
1134:Sjöstrand, Jonas (2005).
1025:10.1142/s179383091950068x
635:) for families of graphs
163:) for families of graphs
1001:, question 3, page 472.
720:is a complete graph on
150: − 1. Given
886:
859:
802:
775:
714:
687:
578:
404:
377:
325:
298:
233:
206:
70:
887:
885:{\displaystyle W_{n}}
860:
803:
801:{\displaystyle P_{n}}
776:
715:
713:{\displaystyle K_{n}}
688:
579:
405:
403:{\displaystyle W_{n}}
378:
326:
324:{\displaystyle P_{n}}
299:
234:
232:{\displaystyle K_{n}}
207:
89:memory-hard functions
62:
1296:"On pebbling graphs"
1222:Discrete Mathematics
1063:Discrete Mathematics
892:is a wheel graph on
869:
818:
785:
730:
697:
646:
506:
494:The stacking theorem
387:
345:
308:
253:
216:
174:
77:) for a given graph
808:is a path graph on
882:
855:
798:
771:
710:
683:
574:
548:
400:
373:
321:
294:
229:
202:
1228:(11): 2301–2306.
1019:(6): 1950068, 7.
587:for every vertex
524:
35:mathematical game
16:(Redirected from
1343:
1336:Graph invariants
1321:
1319:
1313:. Archived from
1300:
1287:
1273:
1263:
1237:
1203:
1202:
1192:
1172:
1166:
1165:
1155:
1131:
1125:
1124:
1122:
1110:
1104:
1103:
1078:
1060:
1051:
1045:
1044:
1008:
1002:
995:
989:
988:
961:Chung, Fan R. K.
957:
944:
943:
942:
941:
928:
891:
889:
888:
883:
881:
880:
864:
862:
861:
856:
836:
835:
807:
805:
804:
799:
797:
796:
780:
778:
777:
772:
764:
763:
748:
747:
719:
717:
716:
711:
709:
708:
692:
690:
689:
684:
664:
663:
627:) that results.
583:
581:
580:
575:
573:
572:
547:
430:
409:
407:
406:
401:
399:
398:
382:
380:
379:
374:
363:
362:
330:
328:
327:
322:
320:
319:
303:
301:
300:
295:
293:
292:
271:
270:
238:
236:
235:
230:
228:
227:
211:
209:
208:
203:
192:
191:
53:, is the lowest
21:
1351:
1350:
1346:
1345:
1344:
1342:
1341:
1340:
1326:
1325:
1324:
1317:
1298:
1290:
1271:
1266:
1216:
1212:
1210:Further reading
1207:
1206:
1174:
1173:
1169:
1133:
1132:
1128:
1112:
1111:
1107:
1058:
1053:
1052:
1048:
1010:
1009:
1005:
996:
992:
977:10.1137/0402041
959:
958:
947:
939:
937:
930:
929:
925:
920:
903:
872:
867:
866:
827:
816:
815:
788:
783:
782:
755:
739:
728:
727:
700:
695:
694:
655:
644:
643:
637:
549:
504:
503:
496:
472:
441:
440:
435:
432:
428:
425:
390:
385:
384:
354:
343:
342:
311:
306:
305:
278:
262:
251:
250:
219:
214:
213:
183:
172:
171:
165:
105:
28:
23:
22:
15:
12:
11:
5:
1349:
1347:
1339:
1338:
1328:
1327:
1323:
1322:
1320:on 2015-11-25.
1288:
1264:
1213:
1211:
1208:
1205:
1204:
1167:
1126:
1105:
1046:
1003:
990:
971:(4): 467–472.
945:
922:
921:
919:
916:
915:
914:
912:Proof of space
909:
902:
899:
898:
897:
879:
875:
854:
851:
848:
845:
842:
839:
834:
830:
826:
823:
813:
795:
791:
770:
767:
762:
758:
754:
751:
746:
742:
738:
735:
725:
707:
703:
682:
679:
676:
673:
670:
667:
662:
658:
654:
651:
636:
629:
607:) denotes the
585:
584:
571:
568:
565:
562:
559:
556:
552:
546:
543:
540:
537:
534:
531:
527:
523:
520:
517:
514:
511:
495:
492:
471:
464:
436:
433:
427:
424:
421:
420:
419:
397:
393:
372:
369:
366:
361:
357:
353:
350:
340:
318:
314:
291:
288:
285:
281:
277:
274:
269:
265:
261:
258:
248:
241:complete graph
226:
222:
201:
198:
195:
190:
186:
182:
179:
164:
157:
132:complete graph
104:
97:
55:natural number
31:Graph pebbling
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1348:
1337:
1334:
1333:
1331:
1316:
1312:
1308:
1304:
1297:
1293:
1292:Pachter, Lior
1289:
1285:
1281:
1277:
1270:
1265:
1261:
1257:
1253:
1249:
1245:
1241:
1236:
1231:
1227:
1223:
1219:
1215:
1214:
1209:
1200:
1196:
1191:
1186:
1182:
1178:
1171:
1168:
1163:
1159:
1154:
1153:10.37236/1989
1149:
1145:
1141:
1137:
1130:
1127:
1121:
1116:
1109:
1106:
1102:
1098:
1094:
1090:
1086:
1082:
1077:
1072:
1068:
1064:
1057:
1050:
1047:
1042:
1038:
1034:
1030:
1026:
1022:
1018:
1014:
1007:
1004:
1000:
994:
991:
986:
982:
978:
974:
970:
966:
962:
956:
954:
952:
950:
946:
936:
935:
927:
924:
917:
913:
910:
908:
905:
904:
900:
895:
877:
873:
852:
849:
846:
843:
840:
832:
828:
821:
814:
811:
793:
789:
768:
765:
760:
756:
752:
744:
740:
733:
726:
723:
705:
701:
680:
677:
674:
671:
668:
660:
656:
649:
642:
641:
640:
634:
630:
628:
626:
622:
618:
614:
610:
606:
602:
598:
594:
590:
566:
563:
560:
554:
550:
541:
535:
532:
529:
525:
521:
515:
509:
502:
501:
500:
493:
491:
489:
485:
481:
477:
469:
465:
463:
461:
457:
453:
449:
448:Ronald Graham
445:
439:
417:
413:
395:
391:
370:
367:
359:
355:
348:
341:
338:
334:
316:
312:
289:
286:
283:
279:
275:
267:
263:
256:
249:
246:
242:
224:
220:
199:
196:
188:
184:
177:
170:
169:
168:
162:
158:
156:
153:
149:
145:
141:
137:
133:
128:
126:
122:
118:
117:number theory
114:
110:
102:
98:
96:
94:
90:
85:
82:
80:
76:
69:
67:
61:
59:
56:
52:
48:
44:
40:
36:
32:
19:
1315:the original
1302:
1275:
1235:math/0510045
1225:
1221:
1218:Chan, Melody
1190:math/0409321
1180:
1176:
1170:
1143:
1139:
1129:
1120:math/0410410
1108:
1076:math/0406206
1069:(1): 15–23,
1066:
1062:
1049:
1016:
1012:
1006:
999:Chung (1989)
993:
968:
964:
938:, retrieved
933:
926:
893:
809:
721:
638:
632:
624:
620:
616:
612:
604:
600:
596:
592:
588:
586:
497:
487:
483:
479:
475:
473:
467:
459:
444:Chung (1989)
442:
415:
336:
244:
166:
160:
151:
147:
143:
142:: If we had
139:
135:
129:
124:
121:F.R.K. Chung
106:
100:
93:cryptography
86:
83:
78:
74:
71:
65:
63:
57:
50:
46:
37:played on a
30:
29:
1146:: Note 22.
907:Pebble game
412:wheel graph
940:2024-01-15
918:References
452:conjecture
333:path graph
119:. In 1989
1183:: 53–62.
1041:204207428
896:vertices.
850:−
822:γ
812:vertices.
766:−
734:γ
724:vertices.
678:−
650:γ
533:∈
526:∑
450:with the
446:credited
418:vertices.
349:π
339:vertices.
287:−
257:π
247:vertices.
178:π
1330:Category
901:See also
865:, where
781:, where
693:, where
609:distance
595:, where
383:, where
304:, where
212:, where
109:Lagarias
43:vertices
1311:1369255
1284:1744229
1260:5501949
1252:2404560
1199:2259702
1162:2180807
1101:5109099
1093:2148478
1033:4044549
985:1018531
1309:
1282:
1258:
1250:
1197:
1160:
1099:
1091:
1039:
1031:
983:
476:et al.
474:Crull
1318:(PDF)
1299:(PDF)
1272:(PDF)
1256:S2CID
1230:arXiv
1185:arXiv
1115:arXiv
1097:S2CID
1071:arXiv
1059:(PDF)
1037:S2CID
611:from
488:every
410:is a
331:is a
239:is a
39:graph
33:is a
997:See
482:, γ(
113:Saks
111:and
1240:doi
1226:308
1148:doi
1081:doi
1067:296
1021:doi
973:doi
615:to
591:in
414:on
335:on
243:on
134:on
127:).
91:in
1332::
1307:MR
1301:.
1280:MR
1274:.
1254:.
1248:MR
1246:.
1238:.
1224:.
1195:MR
1193:.
1181:48
1179:.
1158:MR
1156:.
1144:12
1142:.
1138:.
1095:,
1089:MR
1087:,
1079:,
1065:,
1061:,
1035:.
1029:MR
1027:.
1017:11
1015:.
981:MR
979:.
967:.
948:^
631:γ(
466:γ(
159:π(
99:π(
95:.
81:.
1286:.
1262:.
1242::
1232::
1201:.
1187::
1164:.
1150::
1123:.
1117::
1083::
1073::
1043:.
1023::
987:.
975::
969:2
894:n
878:n
874:W
853:9
847:n
844:4
841:=
838:)
833:n
829:W
825:(
810:n
794:n
790:P
769:1
761:n
757:2
753:=
750:)
745:n
741:P
737:(
722:n
706:n
702:K
681:1
675:n
672:2
669:=
666:)
661:n
657:K
653:(
633:G
625:v
623:(
621:s
617:v
613:u
605:v
603:,
601:u
599:(
597:d
593:G
589:v
570:)
567:v
564:,
561:u
558:(
555:d
551:2
545:)
542:G
539:(
536:V
530:u
522:=
519:)
516:v
513:(
510:s
484:G
480:G
468:G
431::
416:n
396:n
392:W
371:n
368:=
365:)
360:n
356:W
352:(
337:n
317:n
313:P
290:1
284:n
280:2
276:=
273:)
268:n
264:P
260:(
245:n
225:n
221:K
200:n
197:=
194:)
189:n
185:K
181:(
161:G
152:n
148:n
144:n
140:n
136:n
125:G
101:G
79:G
75:G
66:n
58:n
51:G
47:G
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.