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

Graham's pebbling conjecture on the product of generalized friendship graphs

作　　者：高泽图[1] 尹建华[1] 李文雅[1] 

机构地区：[1]海南大学信息科学技术学院应用数学系,海南海口570228

出　　处：《高校应用数学学报（A辑）》2008年第4期487-491,共5页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(10401010;10861006);海南省自然科学基金(807026)

摘　　要：连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立.The pebbling number of a connected graph G is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves.Graham conjectured that for any connected graphs G and H,f(G×H)≤f(G)f(H).In this paper,Graham s conjecture when H is a friendship graph or a generalized friendship graph and G is a graph with the two-pebbling property is proved.As a corollary, Graham s conjecture holds when G and H are friend...

关 键 词：PEBBLING GRAHAM猜想 友谊图 广义友谊图 

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