The 2-Pebbling Property and a Conjecture of Graham's |
| |
Authors: | Hunter S Snevily James A Foster |
| |
Institution: | Department of Mathematics and Statistics, University of Idaho, Moscow, ID 83844-0101, USA. e-mail: snevily@uidaho.edu, US Department of Computer Science, University of Idaho, Moscow, ID 83844-0101, USA e-mail: foster@cs.uidaho.edu, US
|
| |
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. It is conjectured that for all graphs G and H, f(G 2H)hf(G)f(H).¶Let Cm and Cn be cycles. We prove that f(Cm 2Cn)hf(Cm) f(Cn) for all but a finite number of possible cases. We also prove that f(G2T)hf(G) f(T) when G has the 2-pebbling property and T is any tree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|