运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2013年
3期
35-44
,共10页
Graham猜想%圈%中间图%pebbling数
Graham猜想%圈%中間圖%pebbling數
Graham시상%권%중간도%pebbling수
Graham's conjecture%cycles%middle graphs%pebbling number
图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猜想.
圖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猜想.
도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시상.
