广义友谊图乘积上的Graham pebbling猜想

摘要：

连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和日有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立.

关键词：pebbling、Graham猜想、友谊图、广义友谊图

所属期刊栏目：23

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

资助基金：国家自然科学基金10401010,10861006;海南省自然科学基金807026

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

页数：共5页

页码：487-491