圈的中间图pebbling数和Graham猜想

Pebbling numbers of middle graphs of cycles and Graham's conjecture

图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的1个pebble移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的正整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动,把1个pebble移到图G的任意一个顶点上.图G的中间图M(G)就是在G的每一条边上插入一个新点,再把G上相邻边上的新点用一条边连接起来的图.对于任意两个连通图G和H,Graham猜测f(G×H)≤f(G)f(H).首先研究了圈的中间图的pebbling数,然后讨论了一些圈的中间图满足Graham猜想.

A pebbling move on a graph G consists of taking two pebbles off one vertex and placing one pebble on an adjacent vertex. The pebbling number of a connected graph G, denoted by f（G）, is the least n such that any distribution of n pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. The middle graph M（G） of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. For any connected graphs G and H, Graham conjectured that f（G × H） ≤ f（G）f（H）. In this paper, we show the pebbling numbers of middle graphs of cycles, and discuss that Graham＇s conjecture holds for middle graphs of some cycles.