图的Rubbling问题及其相关问题

Let G be a simple graph，a distribution on G is a distribution of pebbles on the vertices of G. A pebbling move consists of removing two pebbles from one vertex, throwing one away, and putting the other pebble on an adjacent vertex. The pebbling number f(G) of G is the smallest positive integer such that from every distribution of f(G) pebbles on G, one pebble can be moved to any specified target vertex of G by a sequence of pebbling moves. The optimal pebbling number f*(G) of G is the smallest positive integer such that for some distribution of f*(G) pebbles on G, one pebble can be moved to any vertex of G by a sequence of pebbling moves.Graham conjectured that f(G×H)≤f(G) f(H) for any connected graphs G and H. Let u,v,w be the vertices of G,u and v are distinct vertices, w are adjacent to both u and v. A strict rubbling move removes one pebble each at u and v, and adds one pebble at w. A rubbling move is either a pebbling move or a strict rubbling move. The rubbling number r(G) of G is the smallest positive integer such that from every distribution of r(G) pebbles on G, one pebble can be moved to any specified target vertex of G by a sequence of rubbling moves. The optimal rubbling number r*(G) of G is the smallest positive integer such that for some distribution of r*(G) pebbles on G, one pebble can be moved to any vertex of G by a sequence of rubbling moves. The main contents of this study: discuss the rubbling number and the optimal rubbling number of graphs; discuss the pebbling number and the optimal pebbling number of some classes of graphs; discuss the Hurlbert's problem and its extensions; discuss the Graham's conjecture and its extensions. The meaning of this study is further improving the system theory of the rubbling number and the pebbling number.

图G的Pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个pebble移到G的任意一个目标顶点上,其中一个Pebbling移动是从一个顶点移走2个pebble而把其中的1个移到与其相邻的一个顶点上。Graham猜测：对于任意的连通图G和H，有f(G×H)≤f(G) f(H)。图G 的Rubbling数r(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的Rubbling移动把1个pebble移到G的任意一个顶点上。本项目的研究内容：研究图的Rubbling数和最优Rubbling数；研究图的最优Pebbling 数；研究图的Pebbling 数和Hurlbert问题及相关问题，探索Graham猜想。本研究的目的是进一步完善图的Rublling数和Pebbling数的理论。

图的Rubbling和Pebbling是当今国际图论界关注的一个前沿课题。图的Rubbling和Pebbling问题是运输消耗资源的网络优化模型。Pebbling问题是由Chung于1989年，通过计算图的Cartesian乘积的Pebbling数，解决了Kleitman 和 Lemke提出的数论问题而发展起来的。图的Rubbling问题是Pebbling问题的一个推广.本项目致力于图的Rubbling和Pebbling的研究，其主要研究内容包括：1）研究了Graham Pebbling猜想及其推广，提出了弱2-pebbling 性质的概念，研究了Lemke图，探讨了解决Graham Pebbling猜想的新的方法;2）研究了 稠密二部图的rubbling数和最优rubbling数;3）研究了Spindle图的Pebbling数和最优Pebbling数;4）证明了Lourdusamy关于两个圈的Cartesian乘积的t-pebbling数的一个猜想。图的Rubbling和Pebbling问题对图论和理论计算机科学具有重要理论意义和应用背景，二十多年来这方面的研究得到迅猛发展，成为图论研究的一个新方向，因此，对它的进一步研究和探讨不仅具有科学意义，而且也具有实际应用价值。