圈的中间图pebbling数和Graham猜想

图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\times H)\leq f(G)f(H). 首先研究了圈的中间图的pebbling 数, 然后讨论了一些圈的中间图满足Graham猜想.

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

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\times H)\leq 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.