圈的中间图pebbling数和Graham猜想  

Pebbling numbers of middle graphs of cycles and Graham's conjecture

作　　者：叶永升[1] 刘芳[1] 翟明清[2] 

机构地区：[1]淮北师范大学数学科学学院,安徽淮北235000 [2]滁州学院数学系,安徽滁州239012

出　　处：《运筹学学报》2013年第3期35-44,共10页Operations Research Transactions

基　　金：国家自然科学基金(No.10971248);安徽省科技厅自然科学基金(No.1208085QF119);安徽省教育厅自然科学基金(Nos.KJ2013Z279;KJ2011B152;KJ2012B166;2011SQRL070)

摘　　要：图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的1个pebble移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的正整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动,把1个pebble移到图G的任意一个顶点上.图G的中间图M(G)就是在G的每一条边上插入一个新点,再把G上相邻边上的新点用一条边连接起来的图.对于任意两个连通图G和H,Graham猜测f(G×H)≤f(G)f(H).首先研究了圈的中间图的pebbling数,然后讨论了一些圈的中间图满足Graham猜想.A pebbling move on a graph G consists of taking two pebbles off one vertex and placing one pebble on an adjacent vertex. The pebbling number of a connected graph G, denoted by f（G）, is the least n such that any distribution of n pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. The middle graph M（G） of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. For any connected graphs G and H, Graham conjectured that f（G × H） ≤ f（G）f（H）. In this paper, we show the pebbling numbers of middle graphs of cycles, and discuss that Graham＇s conjecture holds for middle graphs of some cycles.

关 键 词：GRAHAM猜想 圈 中间图 PEBBLING数 

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