Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648388 | Discrete Mathematics | 2010 | 8 Pages |
Given a distribution of pebbles on the vertices of a connected graph GG, a pebbling move on GG consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number f(G)f(G) is the smallest number mm such that, for every distribution of mm pebbles and every vertex vv, a pebble can be moved to vv. A graph GG is said to have the2-pebbling property if, for any distribution with more than 2f(G)−q2f(G)−q pebbles, where qq is the number of vertices with at least one pebble, it is possible, using pebbling moves, to get two pebbles to any vertex. A graph GG without the 2-pebbling property is called a Lemke graph . Snevily and Foster [H.S. Snevily, J.A. Foster, The 2-pebbling property and a conjecture of Graham’s, Graphs and Combin. 16 (2000), 231–244] defined an infinite family {L1,L2,…}{L1,L2,…} of possible Lemke graphs, and conjectured that LkLk is a Lemke graph for each kk. In this paper, we prove this conjecture.