On Pebbling Graphs

Pebbles are nonnegative integer weights on the vertices of a graph. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex.In this thesis, we develop some necessary terminology and preliminaries to understand graph pebbling in Section1.The (traditional) pebbling number of a graph G, denoted by f(G), is the minimum integer n, so that from any distribution with n pebbles, one pebble can be moved to any given vertex. In Section2we give a construction of Class0graph, and also give the pebbling number of Jahangir graph Jn,m for n is even, m≥8, which gives a different proof to develop the result of A. Lourdusamy etc[44].Assume that G1and G2are two undirected graphs, the Cartesian product of G1and G2is denoted by G1×G2, where V(G1×G2)=V(G1)×V(G2), two distinct vertices x1x2and y1y2are adjacent if and only if (x1=y1, x2y2∈E(G2)), or (x2=y2, x1y1∈E(Gi)). The middle graph of G, denoted by M(G), is a graph obtained from G by inserting a new vertex on every edge of G, and connecting a new edge between the new vertices if the edges they inserted are connected in G. Graham’s Conjecture says that the pebbling number of the Cartesian product is no more then the product of the pebbling number, that is f(G×H)≤f(G)f(H). This conjecture is still open. In Section3we show that it holds for hypercubes, some odd cycles and the middle graph of cycles, and we show that the Lemke graph satisfies the path property.The optimal t-pebbling number of a graph G, denoted by ft1(G), is the small-est number n, so that there exist a distribution with n pebbles, t pebbles can be moved to any given vertex. In Section4, we give the optimal pebbling number of some certain graphs. The t-arbitrary pebbling number, denoted by f(G, t), is the smallest number n, such that from any distribution with n pebbles, one can reach any distribution with t pebbles, David S. Herscovici [31] conjectured that f(G,t)=ft(G), in Section5, we show some connection of The t-arbitrary pebbling number and the traditional pebbling number.The t-free pebbling number,Φt(G), is the smallest number n, so that from any distribution with n pebbles, we can allow at most t moves do not loss any pebbles, then one pebble can be moved to any given vertex. In Section5, we give the t-free pebbling number of paths and cycles.