摘要
Chung定义了图G上的一个pebbling移动是从一个顶点移走两个pebble而把其中的一个移到与其相邻的一个顶点上.连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).作者们验证了三类二部图的2-pebbling性质以及当H为此类二部图,G为一个2-pebbling性质的图时,Graham猜想成立.
Chung defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and then the addition of one pebble to some adjacent vertex. The pebbling number of a connected graph G is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G × H) ≤ f(G)f(H). In this paper, the authors show that three bipartite graphs have the two-pebbling property. Moreover, they also prove that Graham's conjecture hold when H is one of the above three bipartite graphs and G is a graph with the two-pebbling property.
出处
《高校应用数学学报(A辑)》
CSCD
北大核心
2010年第3期365-371,共7页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
基金
国家自然科学基金(10861006)
海南省自然科学基金(807026)
2009年海南大学科研资助项目(hd09xm87)