CaltechAUTHORS
  A Caltech Library Service

On pebbling graphs

Pachter, Lior and Snevily, Hunter S. and Voxman, Bill (1995) On pebbling graphs. In: Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium. No.107. Utilitas Mathematica Publishing , Winnipeg, MB, pp. 65-80. http://resolver.caltech.edu/CaltechAUTHORS:20170309-150137723

Full text is not posted in this repository.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170309-150137723

Abstract

The pebbling number of a graph G, f(G), is the least m such that, however m pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. We give another proof that f(Q^n) = 2^n (Chung) and show that for most graphs f(G) = |V(G)| or |V(G)| + 1. We also find explicitly for certain classes of graphs (i.e. for odd cycles and squares of paths). characterize efficient graphs, show that most graphs have the 2-pebbling property, and obtain some results on optimal pebbling.


Item Type:Book Section
Additional Information:© 1995 Utilitas Mathematica Publishing.
Record Number:CaltechAUTHORS:20170309-150137723
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170309-150137723
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:75005
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:13 Mar 2017 16:13
Last Modified:13 Mar 2017 16:13

Repository Staff Only: item control page