| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649858 | Discrete Mathematics | 2009 | 5 Pages |
The pebbling number of a graph GG, f(G)f(G), is the least nn such that, no matter how nn pebbles are placed on the vertices of GG, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p1,p2,…,pnp1,p2,…,pn be positive integers and GG be such a graph, V(G)=nV(G)=n. The thorn graph of the graph GG, with parameters p1,p2,…,pnp1,p2,…,pn, is obtained by attaching pipi new vertices of degree 1 to the vertex uiui of the graph GG, i=1,2,…,ni=1,2,…,n. Graham conjectured that for any connected graphs GG and HH, f(G×H)≤f(G)f(H)f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every pi>1(i=1,2,…,n) by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when GG and HH are the thorn graphs of the complete graphs with every pi>1(i=1,2,…,n).
