完全r部图乘积上的Graham猜想  

GRAHAM'S CONJECTURE ON COMPLETE r-PARTITE GRAPHS

作　　者：董会英[1] 

机构地区：[1]唐山师范学院数学系,唐山063000

出　　处：《系统科学与数学》2004年第1期125-128,共4页Journal of Systems Science and Mathematical Sciences

摘　　要：图G的Pebbling数f(G)是最小的正整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到任意一点上,其中Pebbling移动是从一个顶点处移走两个Pebble而把其中一个移到与其相邻的一个顶点上。Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H)。本文证明对于一个完全r部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立。作为一个推论,当G和H均为完全r部图时,Graham猜想成立。The pebbling number of a graph G,f(G), is the least n such that, however n pebbles are placed on the vertices of G, a pebble can be moved to any vertex by a sequence of pebbling moves, each pebbling move taking two pebbles from one vertex and placing one on an adjacent vertex. Ronald Graham conjectured that for all contected graphs G and H, f(G×H)<f(G)f(H). In this paper we prove that the conjecture holds when G is a complete r-partite graph and H satifies the 2 - pebbling property. As a conclusion, it is obtained that Graham's conjecture holds if G and H are complete multipartite graphs.

关 键 词：PEBBLING数 GRAHAM猜想 完全r部图 Pebbling移动 连通图 

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