کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648388 | 1632438 | 2010 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The proof of a conjecture due to Snevily The proof of a conjecture due to Snevily](/preview/png/4648388.png)
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.
Journal: Discrete Mathematics - Volume 310, Issues 10–11, 6 June 2010, Pages 1614–1621