The proof of a conjecture due to Snevily
The proof of a conjecture due to Snevily
复制标题
Snevilly猜想的证明
DOI：
10.1016/j.disc.2010.02.008
复制
发表时间：
2010-06
影响因子：
0.8
通讯作者：
高泽图
中科院分区：
文献类型：
--
作者：
尹建华;高泽图
给定连通图G的顶点上的鹅卵石分布，G上的鹅卵石移动包括从一个顶点上取下两个鹅卵石，并将一个鹅卵石放置在相邻的顶点上。卵石数f（G）是最小的数m，使得对于每一个m个卵石的分布和每一个顶点v，一个卵石可以移动到v。一个图G被称为具有2-卵石性质，如果对于任何有超过2f（G）−q个卵石的分布，其中q是至少有一个卵石的顶点的数目，使用卵石移动，可以使两个卵石移动到任何顶点。没有2-pebbling性质的图称为Lemke图。Snevily and Foster（英语：Snevily and Foster）Snevily，J.A. Foster，The 2-pebbling property and a consumption of Graham's，Graphs and Combin. 16（2000），231-244]定义了一个可能的Lemke图的无限族{L1，L2，.}，并证明了对于每个k，Lk是Lemke图.本文证明了这一猜想。
Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling numberf(G) is the smallest number m such that, for every distribution of m pebbles and every vertex v, a pebble can be moved to v. A graph G is said to have the2-pebbling property if, for any distribution with more than 2f(G)−q pebbles, where q 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 G 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,…} of possible Lemke graphs, and conjectured that Lkis a Lemke graph for each k. In this paper, we prove this conjecture.
登录
查看更多内容
影响因子：
0.9
作者：
David P. Bunde;E. Chambers;D. Cranston;K. Milans;D. West
通讯作者：
David P. Bunde;E. Chambers;D. Cranston;K. Milans;D. West
DOI：
10.1016/s0012-365x(00)00177-1
发表时间：
2001
期刊：
Discret. Math.
影响因子：
--
作者：
Stephen S. Wang
通讯作者：
Stephen S. Wang
影响因子：
0.8
作者：
F. Chung
通讯作者：
F. Chung
DOI：
--
发表时间：
2005-09
期刊：
arXiv: Combinatorics
影响因子：
--
作者：
G. Hurlbert
通讯作者：
G. Hurlbert
DOI：
10.1016/s0012-365x(97)00229-x
发表时间：
1998-06
期刊：
Discret. Math.
影响因子：
--
作者：
D. S. Herscovici;Aparna W. Higgins
通讯作者：
D. S. Herscovici;Aparna W. Higgins