几类图的pebbling数  

作　　者：冯荣权[1] 金珠英 

机构地区：[1]北京大学数学科学学院,北京100871 [2]大邱天主教大学数学科

出　　处：《中国科学（A辑）》2002年第3期197-204,共8页Science in China(Series A)

基　　金：国家自然科学基金(批准号:10001005);教育部高等学校博士点专项科研基金资助项目

摘　　要：金芳蓉定义了图G上的一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到G的任一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).计算了两个扇图的积和两个轮图的积的pebbling数,作为推论,当G和H同时是扇图或轮图时,Graham猜想成立.

关 键 词：pebbling移动 GRAHAM猜想 Descartes积 扇图 轮图 连通图 魔图 PEBBLING数 

分 类 号：O157.5[理学—数学]