Pebbling Number

Author

Eric W. Weisstein
January 7, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/PebblingNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PebblingNumber.html.

©2021 Wolfram Research, Inc. except for portions noted otherwise

Parametrized families table

GraphDataCountTable["PebblingNumber",{"Complete"->000027,"Cycle"->135318,"Path"->000079,"Hypercube"->000079}]

Parametrized families

Complete

Entity["Graph",{"Complete",n}]["PebblingNumber"]

Table[GraphData[{"Complete",n},"PebblingNumber"],{n,20}]

CompleteBipartite (Subscript[K, 2,n])

Entity["Graph",{"CompleteBipartite",{2,n}}]["PebblingNumber"]

Table[GraphData[{"CompleteBipartite",Sort[{2,n}]},"PebblingNumber"],{n,20}]

Cycle

A135318

Entity["Graph",{"Cycle",n}]["PebblingNumber"]

Table[GraphData[{"Cycle",n},"PebblingNumber"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["PebblingNumber"]

Table[GraphData[{"Path",n},"PebblingNumber"],{n,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["PebblingNumber"]

Table[GraphData[{"Hypercube",n},"PebblingNumber"],{n,0,10}]

Inequalities

Breadth lower bound: π(G) ≥ N(G)

DeleteCases[{#,#2,#3,#2≥#3}&@@@(GraphData[#,{"#","PebblingNumber","VertexCount"}]&/@GraphData["PebblingNumber","Defined"]),{__,True}]

Cut Lower Bound: π(G) > N(G) if G contains a cut vertex

Select[GraphData["PebblingNumber","Defined"],GraphData[#,"ArticulationVertexCount"]>0&]

DeleteCases[{#,#2,#3,#2>#3}&@@@(GraphData[#,{"#","PebblingNumber","VertexCount"}]&/@Select[GraphData["PebblingNumber","Defined"],GraphData[#,"ArticulationVertexCount"]>0&]),{__,True}]

Depth lower bound: π(G) ≥ (2^d)

DeleteCases[{#,#2,#3,#2>=#3}&@@@(GraphData[#,{"#","PebblingNumber","Diameter"}]&/@GraphData["PebblingNumber","Defined"]),{__,True}]

Pigeonhole Upper Bound: π(G)≤(N(G) - 1)((2^d)-1)+1

DeleteCases[{#,#2,#3,#4,#2≤(#3-1)(2^#4-1)+1}&@@@(GraphData[#,{"#","PebblingNumber","VertexCount","Diameter"}]&/@GraphData["PebblingNumber","Defined"]),{__,True}]

Sharper Upper Bounds #1: π(G)≤(n-d)((2^d)-1)+1

DeleteCases[{#,#2,#3,#4,#2≤(#3-#4)(2^#4-1)+1}&@@@(GraphData[#,{"#","PebblingNumber","VertexCount","Diameter"}]&/@GraphData["PebblingNumber","Defined"]),{__,True}]

Sharper Upper Bounds #2: π(G)≤(n+Floor[n-1/d]-1)(2^(d-1))-n+2

DeleteCases[{#,#2,#3,#4,#2≤(#3+Floor[#3-1/#4]-1)(2^#4-1)-#3+2}&@@@(GraphData[#,{"#","PebblingNumber","VertexCount","Diameter"}]&/@GraphData["PebblingNumber","Defined"]),{__,True}]

Sharper Upper Bounds #3: π(G)≤(n+2γ(G))(2^(d-1))-γ(G)+1

DeleteCases[{#,#2,#3,#4,#2≤(#3+2#4)(2^#4-1)-#5+1}&@@@(GraphData[#,{"#","PebblingNumber","VertexCount","Diameter","DominationNumber"}]&/@Intersection@@(GraphData[#,"Defined"]&/@{"PebblingNumber","DominationNumber"})),{__,True}]