几类二部图的pebbling数

摘要：

Chung定义了图G上的一个pebbling移动是从一个顶点移走两个pebble而把其中的一个移到与其相邻的一个顶点上.连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到G的任意一个顶点上.Graham猜测对于任意的连通图G和日有f(G×H)≤f(G)f(H).作者们验证了三类二部图的2-pebbling性质以及当H为此类二部图,G为一个2-pebbling性质的图时,Graham猜想成立.

关键词：pebbling数、Graham猜想、二部图

所属期刊栏目：25

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金10861006;海南省自然科学基金807026;2009年海南大学科研资助项目hd09xm87

在线出版日期：2010-11-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：365-371