CAJ | 학술논문

图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-pebb-ling性质的图的乘积来说，Graham猜想是成立的。作为一个推论，当G和H都是多扇图时，Graham猜想成立。
도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-pebb-ling성질적도적승적래설，Graham시상시성립적。작위일개추론，당G화H도시다선도시，Graham시상성립。
The pebbling number of a graph G,f( G) , is the least n, no matter how n pebbles are placed on the vertices of G, a pebble can be moved to any vertex by a sequence of pebbling moves.A pebbling move consists of the removal of two pebbles vertex and the placement of one of those two pebbles on an adjacent vertex.Gra-ham conjectured that for any connected graphs G and H,f(G ×H)≤f(G)f(H) .Multi-fan graph Fn1,n2,?,nm is a joint-graph P1∨(Pn1∪Pn2∪?∪Pnm) with n1 +n2 +?+nm +1 vertices.This paper shows that f(Fn1,n2,?,nm)=n1 +n2 +?+nm +2 and Fn1,n2,?,nm with the 2-pebbling property.Graham’ s conjecture holds of a multi-fan graphs by a graph with the 2-pebbling property.As a corollary, Graham’ s conjecture holds when G and H are multi-fan graphs.