作者：王艳秋 叶永升运筹学pebbling数graham猜想pebbling移动多扇图
摘要：图G的pebbling数f（G）是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f（G×H）≤f（G）f（H）。多扇图Fn1,n2,…,nm是指阶为n1＋n2＋…＋nm＋1的联图P1∨（Pn1∪Pn2∪…∪Pnm）。本文首先给出了多扇图的pebbling数,然后证明了多扇图Fn1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
