摘要
图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到任意一个顶点上,其中的pebbling移动是从一个顶点上移走两个pebble,而把其中的一个移到与其相邻的一个顶点上。Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H),证明了对于一个星形图和一个满足2-pebbling性质的图的情形下Graham猜想成立,作为推论,出两个星形图乘积的Graham猜想成立。
The pebbling number of a graph G, f (G), is the least n, no matter how n pebbles are placed on the vertices of G, a pebble to any vertex can be moved to any vertex by a sequence of movements, each movement taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f(GxH)<f(G)f(H).This shows that Graham's conjecture holds true of a star graph by a graph with the two-pebbling properly. As a corollary, Graham's conjecture holds true when G and H are star graphs.
出处
《无锡商业职业技术学院学报》
2003年第2期68-70,共3页
Journal of Wuxi Vocational Institute of Commerce
