论文部分内容阅读
图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猜想成立。